题解 P7172【[COCI2020-2021#3] Specijacija】
tommymio
·
·
题解
我们注意到这题有一个重要性质：第 $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}$ 一遍就过了，诶，非常开心~
```cpp
#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;
}
```