1 条题解

  • 0
    @ 2025-8-24 22:11:43

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar jerry3128
    Astill System

    搬运于2025-08-24 22:11:43，当前版本为作者最后更新于2021-07-09 16:40:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

    以下是正文

    【Ynoi2012】 梦断 SCOI2017

    题目大意：

    • 有一颗静态树，一共有 30 种颜色，每次会单点或者同色块修改颜色。
    • 询问：
      • 某个节点的颜色。
      • 这个节点的同色块的大小。
      • 这个节点同色块的深度最大值和最小值。

    题解：splay & 括号序。

    • 我们考虑对于每一个节点维护每一种不同于自己颜色的儿子的 ETT ，如果一个节点的颜色与父亲相同，那么这个节点应与父亲在同一颗 ETT 当中。即我们用 ETT 森林维护每一个同色连通块。如果两个连通块有相同的颜色和父亲并且颜色不同于父亲，那么显然他们可以简单地收尾相接将二者合并。并维护出链接异色节点的父子边，把标记打在父亲上。
    • 那么找到一个块的信息就是在 ETT 上直接 splay 后得到的信息。异色块的信息都被专门维护的异色边隔离开。一个 ETT 上的根就是一个同色连通块的根。
    • 考虑操作一，如果对单点颜色进行修改。那么我们考虑信息变更的部分：
      • 它与父亲的关系：可能从父亲的 ETT 中被挖出来，也可能被放入父亲的 ETT 中。
      • 它与儿子的关系：当前 ETT 子树区间的所有儿子都会变成异色的，同时可能会有本来异色的儿子变为同色的。因为在刚刚我们将颜色相同且父亲相同的儿子的 ETT 收尾相接，所以可以直接把整个 splay 挂在当前的点的括号序之间。
    • 考虑操作二，对块颜色进行修改，那么就是整个 ETT 被带着跑。考虑信息改变部分。
      • 它的块根与父亲的关系：可能整颗 ETT 被放入块根父亲的括号序之间，或者什么也没有。
      • 整个块向外连出的异色边：有可能修改的目标颜色会涉及多个异色边。
    • 前者很好维护，后者我们看所谓的“异色边”的本质。先把“异色边”新定义放这：每个节点向某个异色亲儿子点集的连边。（一个集合算一条）
    • 因为我们将颜色、父亲相同的块根的 ETT 相接，因此可以直接集合操作。即异色边的本质应该是：每个节点的亲儿子当中不同于当前节点颜色的种数，处于 O(n)O(n)，再看异色边的变化，每次操作一最多增加 2 的异色边，分别为操作节点的父亲与操作节点当前同色的儿子。操作二会遍历一颗 ETT 来找到将删除的异色边，因为用了平衡树作为维护 ETT 的东西，所以找到一个节点的复杂度是均摊 O(log⁡n)O(\log n) 的，每个节点对于一种颜色最多只有一条异色边。所以复杂度是均摊 O(log⁡n)O(\log n) 减少一条“异色边”。全局均摊复杂度是完全能够接受的。
    //ayame保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
#include<bits/stdc++.h>
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
	if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
	return buf[p1++];
}
#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
	long long ret=0,flag=1;
	char c=gc();
	while(c<'0'||c>'9') {
		if(c=='-')flag=-1;
		c=gc();
	}
	while(c<='9'&&c>='0') {
		ret=(ret<<3)+(ret<<1)+c-'0';
		c=gc();
	}
	return ret*flag;
}
void pc(char x) {
	if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
	wb[p2++]=x;
}
void wrt(long long x) {
	if(x<0)pc('-'),x=-x;
	int c[24]= {0};
	if(!x)return pc('0'),void();
	while(x)c[++c[0]]=x%10,x/=10;
	while(c[0])pc(c[c[0]--]+'0');
}
int n,m,a[100005];
int fa[100005],dep[100005];
int o[100005][31],prt[20][100005];
namespace ETT {
	struct node {
		int ch[2],fa,pre,suf;
		int vl,sz,dep,mx,mi,etag,stag;
		int col,ctag;
	} v[200005];
	void push_down(int rt) {
		if(v[rt].ctag) {
			if(v[rt].ch[0])v[v[rt].ch[0]].ctag=v[v[rt].ch[0]].col=v[rt].ctag;
			if(v[rt].ch[1])v[v[rt].ch[1]].ctag=v[v[rt].ch[1]].col=v[rt].ctag;
			v[rt].ctag=0;
		}
	}
	void push_up(int rt) {
		v[rt].pre=v[rt].suf=rt;
		v[rt].mx=v[rt].mi=v[rt].dep;
		if(v[rt].ch[0])v[rt].pre=v[v[rt].ch[0]].pre,v[rt].mx=max(v[rt].mx,v[v[rt].ch[0]].mx),v[rt].mi=min(v[rt].mi,v[v[rt].ch[0]].mi);
		if(v[rt].ch[1])v[rt].suf=v[v[rt].ch[1]].suf,v[rt].mx=max(v[rt].mx,v[v[rt].ch[1]].mx),v[rt].mi=min(v[rt].mi,v[v[rt].ch[1]].mi);
		v[rt].stag=v[rt].etag|v[v[rt].ch[0]].stag|v[v[rt].ch[1]].stag;
		v[rt].sz=v[v[rt].ch[0]].sz+v[rt].vl+v[v[rt].ch[1]].sz;
	}
	void rot(int x) {
		int p=v[x].fa,g=v[p].fa;
		bool d=v[p].ch[1]==x;
		if(g)v[g].ch[v[g].ch[1]==p]=x;
		v[p].ch[d]=v[x].ch[d^1];
		v[v[x].ch[d^1]].fa=p;
		v[x].ch[d^1]=p;
		v[x].fa=g,v[p].fa=x;
		push_up(p),push_up(x);
	}
	void pre_push_down(int rt) {
		if(v[rt].fa)pre_push_down(v[rt].fa);
		push_down(rt);
	}
	void splay(int x,int f=0) {
		if(!x)return;
		pre_push_down(x);
		while(v[x].fa!=f) {
			int p=v[x].fa,g=v[p].fa;
			if(g!=f)rot(v[g].ch[0]==p^v[p].ch[0]==x?x:p);
			rot(x);
		}
	}
	void init() {
		for(int i=1; i<=n; i++) {
			v[i<<1].vl=1,v[i<<1].ch[1]=i<<1|1,v[i<<1|1].fa=i<<1,v[i<<1].col=a[i];
			v[i<<1].dep=v[i<<1|1].dep=dep[i],push_up(i<<1|1),push_up(i<<1);
		}
	}
	int merge_bro(int x,int y) {
		if(!x||!y)return x|y;
		splay(x),splay(y);
		int d=v[x].suf;
		splay(d),v[d].ch[1]=y,v[y].fa=d,push_up(d);
		return x;
	}
	void merge_prt(int x,int y) {
		splay(x<<1),splay(v[v[x<<1].ch[1]].pre,x<<1),splay(y);
		v[v[x<<1].ch[1]].ch[0]=y,v[y].fa=v[x<<1].ch[1],push_up(v[x<<1].ch[1]),push_up(x<<1);
	}
	int ask(int x) {
		if(x==0)return x;
		return splay(x),v[x].pre;
	}
	void dfs(int x,int c,vector<int>&vec) {
		push_down(x);
		if(v[x].etag>>c&1)vec.push_back(x>>1),v[x].etag^=1<<c;
		if(v[v[x].ch[0]].stag>>c&1)dfs(v[x].ch[0],c,vec);
		if(v[v[x].ch[1]].stag>>c&1)dfs(v[x].ch[1],c,vec);
		push_up(x);
	}
}
void ask(int x) {
	int p=x;
	for(int i=19; i>=0; i--)if(ETT::ask(p<<1)==ETT::ask(prt[i][p]<<1))p=prt[i][p];
	ETT::splay(p<<1),ETT::splay(p<<1|1,p<<1);
	int sz=ETT::v[ETT::v[p<<1|1].ch[0]].sz+1,len=max(ETT::v[ETT::v[p<<1|1].ch[0]].mx-dep[p],0)+1;
	wrt(ETT::v[p<<1].col),pc(' '),wrt(sz),pc(' '),wrt(len),pc('\n');
}
void paint_point(int x,int gc) {
	int p=x;
	for(int i=19; i>=0; i--)if(ETT::ask(p<<1)==ETT::ask(prt[i][p]<<1))p=prt[i][p];
	ETT::splay(x<<1),ETT::splay(x<<1|1,x<<1);
	int l=ETT::v[x<<1].ch[0],r=ETT::v[x<<1|1].ch[1],col=ETT::v[x<<1].col;
	ETT::v[l].fa=0,ETT::v[r].fa=0,ETT::v[x<<1].ch[0]=0,ETT::v[x<<1|1].ch[1]=0;
	ETT::push_up(x<<1|1),ETT::push_up(x<<1);

	if(fa[x]) {
		int tmp=ETT::merge_bro(l,r);
		o[fa[p]][col]=tmp;
		ETT::splay(fa[p]<<1);
		if(!o[fa[p]][col])ETT::v[fa[p]<<1].etag^=1<<col;
		ETT::push_up(fa[p]<<1);
	} else ETT::merge_bro(l,r);

	if(ETT::v[x<<1|1].ch[0]) {
		int d=ETT::v[x<<1|1].ch[0];
		ETT::v[d].fa=0,ETT::v[x<<1|1].ch[0]=0;
		ETT::push_up(x<<1|1),ETT::push_up(x<<1);
		o[x][col]=d,ETT::v[x<<1].etag|=1<<col,ETT::push_up(x<<1);
	}

	ETT::v[x<<1].col=ETT::v[x<<1|1].col=gc;

	if(o[x][gc]) {
		int d=o[x][gc];
		o[x][gc]=0,ETT::splay(d),ETT::v[x<<1|1].ch[0]=d,ETT::v[d].fa=x<<1|1;
		ETT::v[x<<1].etag^=1<<gc,ETT::push_up(x<<1|1),ETT::push_up(x<<1);
	}

	if(fa[x]) {
		ETT::splay(fa[x]<<1);
		if(gc!=ETT::v[fa[x]<<1].col) {
			o[fa[x]][gc]=ETT::merge_bro(o[fa[x]][gc],x<<1);
			ETT::splay(fa[x]<<1);
			ETT::v[fa[x]<<1].etag|=1<<gc;
			ETT::push_up(fa[x]<<1);
		} else ETT::merge_prt(fa[x],x<<1);
	}
}
void paint_block(int x,int gc) {
	for(int i=19; i>=0; i--)if(ETT::ask(x<<1)==ETT::ask(prt[i][x]<<1))x=prt[i][x];
	ETT::splay(x<<1),ETT::splay(x<<1|1,x<<1);
	int l=ETT::v[x<<1].ch[0],r=ETT::v[x<<1|1].ch[1],col=ETT::v[x<<1].col;
	ETT::v[l].fa=0,ETT::v[r].fa=0,ETT::v[x<<1].ch[0]=0,ETT::v[x<<1|1].ch[1]=0;
	ETT::push_up(x<<1|1),ETT::push_up(x<<1);

	if(fa[x]) {
		o[fa[x]][col]=ETT::merge_bro(l,r);
		ETT::splay(fa[x]<<1);
		if(!o[fa[x]][col])ETT::v[fa[x]<<1].etag^=1<<col;
		ETT::push_up(fa[x]<<1);
	} else ETT::merge_bro(l,r);

	ETT::v[x<<1].col=ETT::v[x<<1].ctag=gc;

	vector<int> vec;
	ETT::dfs(x<<1,gc,vec);
	for(int w:vec)ETT::merge_prt(w,o[w][gc]),o[w][gc]=0;

	if(fa[x]) {
		ETT::splay(fa[x]<<1);
		if(gc!=ETT::v[fa[x]<<1].col) {
			o[fa[x]][gc]=ETT::merge_bro(o[fa[x]][gc],x<<1);
			ETT::splay(fa[x]<<1);
			ETT::v[fa[x]<<1].etag|=1<<gc;
			ETT::push_up(fa[x]<<1);
		} else ETT::merge_prt(fa[x],x<<1);
	}
}
int main() {
	n=getint();
	for(int i=1; i<=n; i++)prt[0][i]=fa[i]=getint(),dep[i]=dep[fa[i]]+1;
	for(int j=1; j<20; j++)
		for(int i=1; i<=n; i++)prt[j][i]=prt[j-1][prt[j-1][i]];
	for(int i=1; i<=n; i++)a[i]=getint();
	ETT::init(),m=getint();
	for(int i=n; i>=2; i--) {
		if(a[fa[i]]==a[i])ETT::merge_prt(fa[i],i<<1);
		else o[fa[i]][a[i]]=ETT::merge_bro(o[fa[i]][a[i]],i<<1),ETT::splay(fa[i]<<1),ETT::v[fa[i]<<1].etag|=1<<a[i],ETT::push_up(fa[i]<<1);
	}
	for(int i=1; i<=m; i++) {
		int opt=getint();
		if(opt==1) {
			int x=getint(),c=getint();
			paint_point(x,c);
		}
		if(opt==2) {
			int x=getint(),c=getint();
			paint_block(x,c);
		}
		if(opt==3)ask(getint());
	}
	fwrite(wb,1,p2,stdout);
	return Loli Kon;
}
    • 1

    [Ynoi2012] 梦断 SCOI2017

    信息

    ID
    4298
    时间
    1000ms
    内存
    125MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 26ms