题解：P9999 [Ynoi2000] tmostnrq2
_GIGjqw12_ · · 题解
用数据结构维护操作的修改，对于一个询问在
维护和其他题解思路一致，重链剖分，然后把要用到的节点信息全部转成
一次操作可以看作中心点到根路径上的点往中心点移，其他点往根节点移。
定义当前状态的势能为所有位置不同的点到根节点的路径经过的重链数量和，初始势能为
对每条重链开一颗平衡树（我用
使用一个可以插入删除求极值的堆（我用
操作流程：
插入询问，要先在堆中删除该重链，最后再加入。 执行操作，先处理往下跳的情况，并且在堆中删除遍历到的重链。 利用堆处理往上跳的情况，同样操作前要把涉及的两条重链在堆中删除，最后再加入。 将中心点到根路径上的重链加入堆。 取出询问，记得把标记下传才能得到正确的答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T>inline void Min(T &a,const T &b){if(a>b) a=b;}
template<class T>inline void Max(T &a,const T &b){if(a<b) a=b;}
mt19937 rng(time(0));
const int N=1e6;
int siz[N+5],ds[N+5],a[N+5],qx[N+5];
int n,n0,m,fa[N+5],top[N+5];
int dfnCnt,dfn[N+5],dfs[N+5];
vector<int> g[N+5];
void dfs1(int u){//重链剖分
siz[u]=1;
for(int v:g[u]){
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[ds[u]]) ds[u]=v;
}
}
void dfs2(int u,int Top){
dfs[dfn[u]=++dfnCnt]=u,top[u]=Top;
if(ds[u]){
dfs2(ds[u],Top);
for(int v:g[u]) if(v!=ds[u]) dfs2(v,v);
}
}
vector<int> q1[N+5],q2[N+5];
struct node{
bool die;//是否被合并
int w,x,ta;//随机权值 节点编号 懒标记
node *fa,*ls,*rs;//如果被合并，往*fa跳
}t[N*5],*tp=t,*rt[N+5],*qit[N+5];
void pushdn(node *p){
int &t=p->ta;
if(t) p->x+=t,p->ls->ta+=t,p->rs->ta+=t,t=0;
}
void split(node *p,int x,node *&pl,node *&pr){
if(p==t){pl=pr=t;return;}
pushdn(p);
if(p->x<=x){
split(p->rs,x,p->rs,pr);
pl=p;
}else{
split(p->ls,x,pl,p->ls);
pr=p;
}
p->fa=t,p->ls->fa=p->rs->fa=p;
return;
}
node* merge(node *pl,node *pr){
if(pl==t) return pr;
if(pr==t) return pl;
pushdn(pl),pushdn(pr);
node *p;
if(pl->w>pr->w){
pl->rs=merge(pl->rs,pr);
p=pl;
}else{
pr->ls=merge(pl,pr->ls);
p=pr;
}
p->fa=t,p->ls->fa=p->rs->fa=p;
return p;
}
node* getl(node *p){//获取最小节点
pushdn(p);
while(p->ls!=t) p=p->ls,pushdn(p);
return p;
}
node* getr(node *p){//获取最小节点
pushdn(p);
while(p->rs!=t) p=p->rs,pushdn(p);
return p;
}
node* fmerge(node *pl,node *pr){//考虑相同元素的合并
if(pl==t) return pr;
if(pr==t) return pl;
node *sl=getr(pl),*sr=getl(pr);
if(sl->x==sr->x){
split(pl,sl->x-1,pl,sl);
sl->die=1,sl->fa=sr;
}
return merge(pl,pr);
}
node* insert(node *&p,int x){
*(++tp)={0,rng(),x,0,t,t,t};
node *p1,*p2;
split(p,x,p1,p2);
p=merge(fmerge(p1,tp),p2);
return tp;
}
node* find(node *p){//找到代表元素
return p->die?p->fa=find(p->fa):p;
}
set<pii> qj;//维护向上跳的堆
int las[N+5],TIME;
void erase(int u){//删除重链
if(las[u]) qj.erase({las[u],u}),las[u]=0;
}
void updata(int u){//加入重链
if(rt[u]!=t){
las[u]=getl(rt[u])->x-u+1;
qj.insert({las[u],u});
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>n0>>m;
for(int i=1;i<=n;++i) rt[i]=t;
for(int i=2;i<=n;++i) cin>>fa[i],g[fa[i]].push_back(i);
for(int i=1;i<=n0;++i) cin>>a[i];
for(int i=1,l,r,x;i<=m;++i){
cin>>l>>r>>qx[i];
q1[l].push_back(i),q2[r].push_back(i);
}
dfs1(1);
dfs2(1,1);
for(int i=1;i<=n0;++i) a[i]=dfn[a[i]];//将信息转化为dfn的信息
auto exchange=[&](int a[]){
static int b[N+5];
for(int i=1;i<=n;++i) b[i]=dfn[a[i]];
for(int i=1;i<=n;++i) a[dfn[i]]=b[i];
};
exchange(fa),exchange(top);//同上
for(TIME=0;TIME<n0;){
for(int id:q1[TIME+1]){//插入询问
qx[id]=dfn[qx[id]];//将信息转化为dfn的信息
int u=top[qx[id]];
erase(u);//删除
qit[id]=insert(rt[u],qx[id]+TIME);
updata(u);//插入
}
int u=a[TIME+1],fr=u;
while(u){
erase(top[u]);//删除
node *&p=rt[top[u]],*p1,*p2;
split(p,u+TIME,p1,p);
split(p1,u+TIME-1,p1,p2);//分成三段 分别是 向下移 跳到别的重链 向上移
p1->ta+=2;
if(p2!=t){
p2->ta=0,p2->x=fr+(TIME+1);
rt[top[fr]]=fmerge(p2,rt[top[fr]]);//跳到别的重链
}
p=fmerge(p1,p);//可能有重合
u=fa[fr=top[u]];
}
++TIME;//时间流逝
while(qj.size()&&qj.begin()->first==TIME){
int u=qj.begin()->second,v=top[fa[u]];
erase(u),erase(v);//删除
node *px,*pl,*pr;
split(rt[u],TIME+u-1,px,rt[u]);
px->ta=0,px->x=fa[u]+TIME;
split(rt[v],fa[u]+TIME,pl,pr);
rt[v]=merge(fmerge(pl,px),pr);
updata(u),updata(v);//加入
}
u=a[TIME];
while(u) updata(top[u]),u=fa[top[u]];//加入路径上的重量
for(int id:q2[TIME]){
vector<node*> v;
node *p=find(qit[id]);
for(node *u=p;u!=t;u=u->fa) v.push_back(u);
while(v.size()) pushdn(v.back()),v.pop_back();//下传懒标记
qx[id]=dfs[p->x-TIME];
}
}
for(int i=1;i<=m;++i) cout<<qx[i]<<'\n';
}