隐藏
「JZOJ5512」送你一棵圣诞树 - Set+树状数组套主席树 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「JZOJ5512」送你一棵圣诞树 - Set+树状数组套主席树

发表于 更新于 分类于 Valine：

题目大意

    送你一棵$n$个点的树，树根为$1$。一开始每个点上有一个$1\ldots n$的颜色$c_i$不同点颜色可以相同。
    现在有$q$次操作，分为两种类型：

  1. $u\,\,l\,\,r$：询问子树$u$中有多少种在$l$到$r$之间的颜色至少出现了一次。
  2. $u\,\,c$：将$u$的颜色修改为$c$。

    部分测试点要求强制在线.

题目分析

可以将不同颜色单独扯出来建立虚树。
对于每一棵虚树，可以通过在$x,y$端点$+1$，$lca(x,y)-1$的方法在子树内统计去重。
如何统计区间颜色的答案？
使用树套树解决。
外层树状数组（线段树）维护颜色，内层主席树维护位置坐标。
查询即可在$O(\log^2 n)$的时间内完成。

如何处理修改？
使用平衡树（set）（不能使用链表）维护每种颜色的Dfs序，首先在原来的颜色删除该结点，除去其前驱后继的影响，再在新的颜色中加入该结点，加入其前驱后继的影响。
修改即可在$O(\log^2 n)$的时间内完成。

常熟略大，使用快读。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
 
namespace FastIO {
	const int L=1<<15;
	char buf[L],*S,*T;
	char getchar() {
		if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
		return *S++;
	}
	int Get_Int() {
		int res=0,bj=1;char c=getchar();
		while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
		while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
		return res*bj;
	}
}
using FastIO::Get_Int;

const int maxn=100005,K=18;

int n,size=0,root[maxn];

struct Segment_Tree {
	struct Tree {
		int lson,rson,sum;
	} tree[maxn*350];
#define ls tree[index].lson
#define rs tree[index].rson
	void push_up(int index) {
		tree[index].sum=tree[ls].sum+tree[rs].sum;
	}
	void modify(int &index,int left,int right,int target,int val) {
		if(left>target||right<target)return;
		if(!index)index=++size;
		if(left==right) {
			tree[index].sum+=val;
			return;
		}
		int mid=(left+right)>>1;
		modify(ls,left,mid,target,val);
		modify(rs,mid+1,right,target,val);
		push_up(index);
	}
	int query(int index,int left,int right,int Left,int Right) {
		if(left>Right||right<Left)return 0;
		if(Left<=left&&Right>=right)return tree[index].sum;
		int mid=(left+right)>>1;
		return query(ls,left,mid,Left,Right)+query(rs,mid+1,right,Left,Right);
	}
} st;

struct BIT {
	int c[maxn];
#define lowbit(x) x&(-x)
	void add(int x,int pos,int v) {
		for(int i=x; i<=n; i+=lowbit(i))st.modify(root[i],1,n,pos,v);
	}
	int sum(int x,int l,int r) {
		int ans=0;
		for(int i=x; i>=1; i-=lowbit(i))ans+=st.query(root[i],1,n,l,r);
		return ans;
	}
} bit;

int q,t,lastans=0,step=0,a[maxn],First[maxn],Last[maxn],M[maxn],Depth[maxn],p[maxn][K];
vector<int> edges[maxn],color[maxn];
set<int> S[maxn];

bool cmp(int x,int y) {
	return First[x]<First[y];
}

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
	First[Now]=++step;
	M[step]=Now;
	Depth[Now]=depth;
	p[Now][0]=fa;
	for(int j=1; j<K; j++)
		if(~p[Now][j-1])p[Now][j]=p[p[Now][j-1]][j-1];
		else break;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(Next==fa)continue;
		Dfs(Next,Now,depth+1);
	}
	Last[Now]=step;
}

int LCA(int x,int y) {
	if(Depth[x]<Depth[y])swap(x,y);
	for(int i=K-1; i>=0; i--)
		if(Depth[x]==Depth[y])break;
		else if(Depth[x]-(1<<i)>=Depth[y])x=p[x][i];
	if(x==y)return y;
	for(int i=K-1; i>=0; i--)
		if(~p[x][i]&&p[x][i]!=p[y][i]) {
			x=p[x][i];
			y=p[y][i];
		}
	return p[x][0];
}

int main() {
	memset(p,-1,sizeof(p));
	n=Get_Int();
	q=Get_Int();
	t=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
	}
	Dfs(1,-1,1);
	for(int i=1; i<=n; i++)color[a[i]].push_back(i);
	for(int i=1; i<=n; i++)
		if(!color[i].empty()) {
			sort(color[i].begin(),color[i].end(),cmp);
			for(int j=0; j<color[i].size(); j++)S[i].insert(First[color[i][j]]);
			bit.add(i,First[color[i][0]],1);
			for(int j=1; j<color[i].size(); j++) {
				bit.add(i,First[color[i][j]],1);
				bit.add(i,First[LCA(color[i][j],color[i][j-1])],-1);
			}
		}
	for(int i=1; i<=q; i++) {
		int opt=Get_Int();
		if(opt==1) {
			int x=Get_Int()^(lastans*t),l=Get_Int()^(lastans*t),r=Get_Int()^(lastans*t);
			printf("%d\n",lastans=bit.sum(r,First[x],Last[x])-bit.sum(l-1,First[x],Last[x]));
		} else {
			int x=Get_Int()^(lastans*t),y=Get_Int()^(lastans*t),pre=0,suc=0;
			//cut
			set<int>::iterator it=S[a[x]].find(First[x]),it2=it,pos=it;
			if(it!=S[a[x]].begin())pre=M[*--it];
			if(++it2!=S[a[x]].end())suc=M[*it2];
			S[a[x]].erase(pos);
			if(pre)bit.add(a[x],First[LCA(pre,x)],1);
			if(suc)bit.add(a[x],First[LCA(x,suc)],1);
			if(pre&&suc)bit.add(a[x],First[LCA(pre,suc)],-1);
			bit.add(a[x],First[x],-1);
            a[x]=y;
			//link
			S[a[x]].insert(First[x]);
			pre=suc=0,it=S[a[x]].find(First[x]),it2=it;
			if(it!=S[a[x]].begin())pre=M[*--it];
			if(++it2!=S[a[x]].end())suc=M[*it2];
			if(pre)bit.add(a[x],First[LCA(pre,x)],-1);
			if(suc)bit.add(a[x],First[LCA(x,suc)],-1);
			if(pre&&suc)bit.add(a[x],First[LCA(pre,suc)],1);
			bit.add(a[x],First[x],1);
		}
	}
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~