专栏文章

题解:P9999 [Ynoi2000] tmostnrq2

P9999题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio6kep7
此快照首次捕获于
2025/12/02 14:11
3 个月前
此快照最后确认于
2025/12/02 14:11
3 个月前
查看原文
用数据结构维护操作的修改,对于一个询问在ll操作前插入,在 rr 操作后查询位置,可以不删除吃力不讨好。
维护和其他题解思路一致,重链剖分,然后把要用到的节点信息全部转成 dfndfn 序下的信息,方便维护,只有在最后转换成原编号。
一次操作可以看作中心点到根路径上的点往中心点移,其他点往根节点移。
定义当前状态的势能为所有位置不同的点到根节点的路径经过的重链数量和,初始势能为0 0。那么插入一个节点最多使势能增加logn logn,一次中心点到根路径上的点往中心点移的操作最多使势能增加logn logn,一个节点往根节点跳到另一条重链时使势能减少1 1。一个节点往根节点跳到另一条重链的次数小于势能增加总量。而上述三种操作的时间复杂度均为O(logn) O(logn),所以总时间复杂度为O(nlog2n) O(nlog 2 n)。
对每条重链开一颗平衡树(我用 fhqfhq)维护节点,两个节点重合是要使用并查集合并保证时间复杂度。 整体向上移动可看作对所有点减去一个时间的偏移量。
使用一个可以插入删除求极值的堆(我用 setset)维护每条重链下一次有节点往上跳到其他重链的时刻。

操作流程:

插入询问,要先在堆中删除该重链,最后再加入。 执行操作,先处理往下跳的情况,并且在堆中删除遍历到的重链。 利用堆处理往上跳的情况,同样操作前要把涉及的两条重链在堆中删除,最后再加入。 将中心点到根路径上的重链加入堆。 取出询问,记得把标记下传才能得到正确的答案。
CPP
#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';
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...