自动搬运

查看原文

来自洛谷，原作者为

	tommymio Cruel world

搬运于2025-08-24 22:27:19，当前版本为作者最后更新于2021-03-03 22:48:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\text{Subtask 1}$ 可以直接构造树。$\text{Subtask 2}$ 可以直接向上跳。这两个 $\text{Subtask}$ 都非常简单，似乎并没有什么指导意义（

我们注意到这题有一个重要性质：第 $i$ 层只有一个节点具有两个儿子，也就是说，树的形态中会包含很多长链。如下图，被红色圆圈圈出的是一些长链：

如果我们将这些长链缩成点，并保留连通性，得到一棵新树，会怎么样呢？我们惊奇的发现新树的点数为 $O(n)$。证明如下，假设每个叶子节点都是一条长链，那么初始有 $n+1$ 条长链。每个具有两个儿子的点都会使得长链个数 $+1$。故长链个数不超过 $2n+1$，即长链个数是 $O(n)$ 级别的。

假设我们已经建出了这棵新树，那么我们就可以直接在新树上查询 $\text{lca}$ ，从而得到原树上 $x,y$ 的 $\text{lca}$ 所在的长链的编号。现在需要解决两个问题：如何建出新树以及如何查询任意一个点所在的长链编号。

显然有一个性质，新树上的边只会是那些 $a_i$ 与其儿子相连的边。可以想到，自底向下考虑每个 $a_i$。这样的话，从第 $i$ 层到第 $i-1$ 层，某个 $a_i$ 具有两个儿子对第 $i-1$ 层节点的影响，可以看作第 $i$ 层的节点删去右节点得到。而如果从第 $i-1$ 层到第 $i$ 层，则 $a_{i-1}+i$ 之后的点都向后移了一位。

像这种动态删除，并查询实际第 $k$ 个位置，可以使用线段树实现，对每层开一个线段树，叶子上保存当前节点所在的长链编号。并且发现每层除了与 $a_i$ 相关的点，其他点信息都没有改变，所以可以使用可持久化线段树不至于 $\text{MLE}$。建树的时候随便记录一下原树上当前长链深度最大的节点，就可以在查询到 $\text{lca}$ 所在长链编号后直接得到 $\text{lca}$ 了。

$\color{green}\text{tommy}$ 一遍就过了，诶，非常开心~

#include<cstdio>
#include<cmath>
#include<functional>
typedef long long ll;
int n,cnt=0,tot=0;
int rt[400015];
struct node {int id,size,lson,rson;} t[20000005];
ll a[200005],minn[400015];
int skip[400015][25],dep[400015];
int h[400015],to[800035],ver[800035];
inline ll read() {
	ll x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void swap(int &x,int &y) {int tmp=x;x=y;y=tmp;}
inline ll min(const ll &x,const ll &y) {return x<y? x:y;}
inline void add(int x,int y) {to[++cnt]=y;ver[cnt]=h[x];h[x]=cnt;}
inline void assign(int x,int y) {
	t[x].size=t[y].size; t[x].id=t[y].id;
	t[x].lson=t[y].lson; t[x].rson=t[y].rson;
}
inline void change(int &p,int lst,int l,int r,int x,int val) {
	p=++tot; assign(p,lst);
	if(l==r) {t[p].size=(val>0); t[p].id=val; return;}
	int mid=l+r>>1; 
	if(x<=mid) change(t[p].lson,t[lst].lson,l,mid,x,val);
	else change(t[p].rson,t[lst].rson,mid+1,r,x,val);
	t[p].size=t[t[p].lson].size+t[t[p].rson].size;
}
inline std::pair<int,int> ask(int p,int l,int r,int rk) {
	if(l==r) return std::make_pair(l,t[p].id);
	int mid=l+r>>1;
	if(t[t[p].lson].size>=rk) return ask(t[p].lson,l,mid,rk);
	return ask(t[p].rson,mid+1,r,rk-t[t[p].lson].size);
}
inline void prework(int x) {
	for(register int i=1;i<=20;++i) skip[x][i]=skip[skip[x][i-1]][i-1]; 
	for(register int i=h[x];i;i=ver[i]) {int y=to[i]; skip[y][0]=x; dep[y]=dep[x]+1; prework(y);}
}
inline int LCA(int x,int y) {
	if(dep[x]>dep[y]) swap(x,y); //dep[x]<=dep[y]
	for(register int i=20;i>=0;--i) {if(dep[x]<=dep[skip[y][i]]) y=skip[y][i];}
	if(x==y) return x;
	for(register int i=20;i>=0;--i) {if(skip[x][i]!=skip[y][i]) x=skip[x][i],y=skip[y][i];}
	return skip[x][0];
}
inline ll solve(ll x,ll y) {
	ll levX=sqrt(2ll*x),levY=sqrt(2ll*y);
	if(levX*1ll*(levX+1)/2<x) ++levX;
	if(levY*1ll*(levY+1)/2<y) ++levY;
	int lca=LCA(ask(rt[levX],1,n+1,x-levX*1ll*(levX-1)/2).second,ask(rt[levY],1,n+1,y-levY*1ll*(levY-1)/2).second);
	return min(minn[lca],min(x,y));
}
int main() {
	n=read(); int Q=read(),type=read();
	for(register int i=1;i<=n;++i) a[i]=read();
	for(register int i=1;i<=n+1;++i) {
		minn[i]=n*1ll*(n+1)/2+i;
		change(rt[n+1],rt[n+1],1,n+1,i,i);
	}
	int num=n+1;
	for(register int i=n;i;--i) {
		int ind=a[i]-i*1ll*(i-1)/2;
		std::pair<int,int> tmp1=ask(rt[i+1],1,n+1,ind);
		std::pair<int,int> tmp2=ask(rt[i+1],1,n+1,ind+1);
		minn[++num]=a[i]; add(num,tmp1.second); add(num,tmp2.second);
		change(rt[i],rt[i+1],1,n+1,tmp1.first,num);
		change(rt[i],rt[i],1,n+1,tmp2.first,0);
	}
	dep[num]=1; prework(num);
	ll ans=0; 
	while(Q--) {
		ll x=read(),y=read();
		x=(x-1+type*ans)%((n+1)*1ll*(n+2)/2)+1;
		y=(y-1+type*ans)%((n+1)*1ll*(n+2)/2)+1;
		printf("%lld\n",ans=solve(x,y)); 
	}
	return 0;
}