自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:36:24，当前版本为作者最后更新于2023-12-12 23:00:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

感觉难点在于如何想到三分。

很明显，如果我们确定了最小值的位置（显然，必须确定最小值的位置，然后找到其具体值），就可以往左右两端拓展，用 $n-1$ 次 get 操作即可确定整个数列。

一个自然的想法是用二分，每次看最小值在左区间内还是在右区间内。但是我们很容易察觉到，我们找不到判断最小值在哪个区间内的方法。

于是考虑三分。我们取区间 $[l,r]$ 的两个三等分点 $p_1$ 和 $p_2$，这个区间被分成了 $[l,p_1]$，$[p_1+1,p_2-1]$，$[p_2,r]$ 三个区间。

然后又有一个我感觉想不到的操作。考虑 $\text{query}(l,p_2-1)-\text{query}(l,p_1)$ 和 $\text{query}(p_1+1,r)-\text{query}(p_2,r)$。

很明显，他们的 $\sum$ 项最终结果都是相同的，为 $\sum_{i=p_1+1}^{p_2-1} a_i$。因此如果我们比较两个值的相对关系，我们只需要比较 $\min_{i=l}^{p_2-1} a_i-\min_{i=l}^{p_1} a_i$ 和 $\min_{i=p_1+1}^{r} a_i - \min_{i=p_2}^{r} a_i$。

由于所有数互不相同，我们取三个区间的最小值分别是 $x$，$y$，$z$。他们之间的相对值无非六种情况，作为新时代的 OIer 应该具有坚实的分类讨论基础。于是我们要比较 $\min\{x,y\}-x$ 和 $\min\{y,z\} - z$。

• $x < y < z$，前者为 $0$，后者为 $y-z < 0$。
• $x < z < y$，前者为 $0$，后者为 $0 = 0$。
• $y < x < z$，前者为 $y-x$，后者为 $y-z < y-x$。
• $y < z < x$，前者为 $y-x$，后者为 $y-z > y-x$。
• $z < x < y$，前者为 $0$，后者为 $0 = 0$。
• $z < y < x$，前者为 $y-x$，后者为 $0 > y-x$。

所以考虑最小值在三个区间内的所有情况：

• 在最左边的区间中，必有前者不大于后者。
• 在中间的区间中，必有前者不等于后者。
• 在最右边的区间中，必有前者不小于后者。

然后你发现有一个很头疼的问题：如果我们找到的两个值并不相同，那么我们很容易舍掉最左边或者最右边的一个区间。

但是如果两个值相同，我们如何舍去最中间那个区间呢？

答曰：直接把他们删掉。因为最小值一定不在这里面，所以我们可以忽略不计，把左右区间拼起来即可。

实现的时候考虑搞一个双向链表，然后暴力找三等分点。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
uint64_t query(int l, int r);
uint32_t get(int x);
const int MAXN=1e6+10;
uint32_t nxt[MAXN],pre[MAXN],hd,tl,len;
void del(uint32_t pos) {
	len--;
	uint32_t u=pre[pos],v=nxt[pos];
	nxt[u]=v,pre[v]=u;
	return ;
}
uint32_t get_kth(uint32_t k) {
	uint32_t ans=0;
	ffor(i,1,k) ans=nxt[ans];
	return ans;	
}
void dele(uint32_t l,uint32_t r) {
	vector<uint32_t> aim;
	uint32_t ans=0;
	while(ans<l) ans=nxt[ans];
	while(ans<=r) aim.push_back(ans),ans=nxt[ans];
	for(auto id:aim) del(id);
	return ;	
}

std::vector<uint32_t> recover(int n) {
	vector<uint32_t> ans(n);
	hd=0,tl=n+1,len=n;
	ffor(i,1,n) nxt[i]=i+1,pre[i]=i-1;
	nxt[0]=1,pre[n+1]=n;
	while(len>2) {
		uint32_t l=nxt[hd],r=pre[tl],p1=get_kth(len/3),p2=get_kth(len-len/3+1);
		uint64_t val1=query(l,p2-1)-query(l,p1),val2=query(p1+1,r)-query(p2,r);
		if(val1<val2) dele(p2,r);
		else if(val1>val2) dele(l,p1);
		else dele(nxt[p1],pre[p2]);
	}
	uint32_t mnpos;
	if(len==1) mnpos=nxt[hd],ans[mnpos-1]=get(mnpos);
	else {
		uint32_t pos1=nxt[hd],pos2=pre[tl],val1=get(pos1),val2=get(pos2);
		if(val1<val2) mnpos=pos1,ans[mnpos-1]=val1;	
		else mnpos=pos2,ans[mnpos-1]=val2;
	}
	uint64_t lst=ans[mnpos-1];
	ffor(i,mnpos+1,n) {
		uint64_t val=query(mnpos,i)+ans[mnpos-1];
		ans[i-1]=val-lst,lst=val;	
	}
	lst=ans[mnpos-1];
	roff(i,mnpos-1,1) {
		uint64_t val=query(i,mnpos)+ans[mnpos-1];
		ans[i-1]=val-lst,lst=val;	
	}
	return ans;
}

不得不说，交互题属实有点。