WC2013 糖果公园

发表于 | 分类于

WC2013 糖果公园

$\text{Candyland} $有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园玩。

糖果公园的结构十分奇特，它由$ n$ 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 $1$ 至 $n$。有 $n−1$ 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共$ m$ 种，它们的编号依次为$ 1$ 至 $m$。每一个糖果发放处都只发放某种特定的糖果，我们用 $ci$ 来表示 $i$ 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分，我们得到了糖果的美味指数，第 ii 种糖果的美味指数为$ v_i$。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 $i$ 次品尝某类糖果的新奇指数 $w_i$，如果一位游客第 $i$ 次品尝第 $j$种糖果，那么他的愉悦指数 HH 将会增加对应的美味指数与新奇指数的乘积，即 $v_jw_i$。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 $m$ 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

输入格式

第一行包含三个正整数 $n,m,q$，分别表示游览点个数、糖果种类数和操作次数。

第二行包含 $m$ 个正整数 $v_1,v_2,…,v_m$。

第三行包含 $n$ 个正整数 $w_1,w_2,…,w_n$。

第四行到第 $n+2$行，每行包含两个正整数$ ai,bi$，表示这两个游览点之间有路径可以直接到达。

第 $n+3$ 行包含 $n$ 个正整数$ c_1,c_2,…,c_n$。

接下来 $q$ 行，每行包含三个整数$ t,x,y$，表示一次操作：

若 $t$ 为 $0$，则$ 1\leq x\leq n$，$1\leq y\leq m$，表示编号为 $x$ 的游览点发放的糖果类型改为 $y$；

若 $t$ 为 $1$，则 $1\leq x,y\leq n$，表示对出发点为 $x$，终止点为$ y$ 的路线询问愉悦指数。

输出格式

按照输入的先后顺序，对于每个$ t$ 为 $1$ 的操作输出一行，用一个正整数表示答案。

样例一

input

1
2
3
4
5
6
7
8
9
10
11
12
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2

output

1
2
3
4
84
131
27
84

限制与约定

对于所有的数据，$1≤vi,wi≤10^6$，$1≤ai,bi≤n$，$1≤ci≤m$，$w_1,w_2,…,w_n$ 是非递增序列，即对任意 $1<i≤n$，满足$ wi≤wi−1$。

测试点编号 $n$ $m$ $q$ 其它限制
1 $≤20$ $≤20$ $≤20$ 无
2 $≤2000$ $≤2000$ $≤2000$ 无
3 $≤10000$ $≤10000$ $≤10000$ 无
4 $≤80000$ $≤100$ $≤80000$ 没有修改操作；给出的图构成一条链
5 $≤90000$ $≤100$ $≤90000$ 没有修改操作；给出的图构成一条链
6 $≤80000$ $≤80000$ $≤80000$ 没有修改操作
7 $≤90000$ $≤90000$ $≤90000$ 没有修改操作
8 $≤80000$ $≤80000$ $≤80000$ 给出的图构成一条链
9 $≤90000$ $≤90000$ $≤90000$ 给出的图构成一条链
10 $≤100000$ $≤100000$ $≤100000$ 无

题解

前$30$pts就是暴力，然后看到后面没有修改操作的一条链，可以用裸的莫队水过去。然后正解显然是带修改的树上莫队了，但是这两个都只听说过都没学过，于是就学一下。

2011国家集训队 数颜色

要求支持带修改的区间颜色个数询问。

传统的莫队不支持修改，但是我们可以在复杂度升高的情况下让其支持修改操作。

莫队每个询问包含$(l,r)$这样一个二元组，现在将其扩展成$(l,r,x)$代表区间$(l,r)$的询问是在修改$x$次后的。

我们只需要增加一个指针，代表当前已经完成的修改，每次对一个询问进行区间的移动的时候。先进行修改指针的移动，然后判断修改指针是否统计在当前的答案中了，对$ans$进行修改，然后再进行区间的移动的更改。可以证明(我不会)复杂度是$O(n^{\frac {3} {5}})$的。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+1e3+7;
int n,m,c[N],sz,cnt,cc,last[N],L,R,now,vis[N],ans,fans[N];
struct Query{
	int l,r,lb,rb,id,x;
}q[N*2+1];
bool cmp(Query a,Query b)
{
	return a.lb<b.lb||(a.lb==b.lb&&(a.rb<b.rb||(a.rb==b.rb&&a.x<b.x)));
}
struct Modiry{
	int t,x,y,last;
}s[N*2+1];
void change(int x,int y)
{
	if(L<=x&&R>=x)
	{
		vis[c[x]]--;
		if(vis[c[x]]==0)
			ans--;
		c[x]=y;
		if(vis[c[x]]==0)
			ans++;
		vis[c[x]]++;
	}
	else
		c[x]=y;
}
void insert(int x)
{
	if(vis[c[x]]==0)
		ans++;
	vis[c[x]]++;
}
void del(int x)
{
	vis[c[x]]--;
	if(vis[c[x]]==0)
		ans--;
}
int main()
{
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);
	sz=sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]),last[i]=c[i];
	for(int i=1;i<=m;i++)
	{
		char op[3];
		int x,y;
		scanf("%s%d%d",op,&x,&y);
		if(op[0]=='Q')
		{
			++cnt;
			q[cnt].l=x;
			q[cnt].r=y;
			q[cnt].id=i;
			q[cnt].lb=x/sz;
			q[cnt].rb=y;
			q[cnt].x=cc;
		}
		else
		{
			++cc;
			s[cc].x=x;
			s[cc].y=y;
			s[cc].last=last[s[cc].x];
			last[s[cc].x]=s[cc].y;
		}
	}
	sort(q+1,q+cnt+1,cmp);
	L=R=0,now=0;
	for(int i=1;i<=cnt;i++)
	{
		while(now<q[i].x)
			now++,change(s[now].x,s[now].y);
		while(now>q[i].x)
			change(s[now].x,s[now].last),now--;
		while(L<q[i].l)
			del(L),L++;
		while(L>q[i].l)
			L--,insert(L);
		while(R<q[i].r)
			R++,insert(R);
		while(R>q[i].r)
			del(R),R--;
		fans[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)
		if(fans[i])
			printf("%d\n",fans[i]);
}

SPOJ Count On Tree II

给定一棵树，询问某两点路径间的颜色个数。

树上子树询问的莫队很简单，直接$\text{dfs}$序搞搞就行了，但是路径显然不能树剖拆开搞了，因为没法合并。

所以我们依然记录一下$\text{dfs}$序然后每个点记录一个$st_x,ed_x$

分类讨论一下，如果一个询问是$(x,y) (st_x<st_y)$，设$p=\text{lca}(x,y)$

  • $p=x$

    很显然就是树上的一条向下的链，那么只需要询问$st_x,st_y$然后可以知道，这之间不在$x,y$路径上的点一定出现了$0$或$2$次，那么我们只需要修改的时候吧加入和删除写在一起，如果加入过就删除，删除过就加入即可。

  • $p\neq x$

    这种情况我们显然考虑$ed_x,st_y$，那么跟刚刚情况一样，无用的点出现了$0$或$2$次，同样的操作即可。但是注意到$p$也会出现两次但是被删除掉了，所以要对于$p$在统计答案之前插入一次，统计之后删除。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+1e3+7;
int n,m,a[N],c[N],st[N],ed[N],dfn[N],cnt,head[N],fa[N],anc[N][18],dc,dep[N];
int fans[N],l,r,vis[N],md[N],ans;
struct node{
	int ne,to;
}edg[N*2+1];
struct Query{
	int l,r,lb,p,id;
}q[N*2+1];
bool cmp(Query a,Query b)
{
	return a.lb<b.lb||(a.lb==b.lb&&a.r<b.r);
}
void build(int u,int v)
{
	++cnt;
	edg[cnt].to=v;
	edg[cnt].ne=head[u];
	head[u]=cnt;
}
void dfs(int i,int f)
{
	fa[i]=f;
	dep[i]=dep[f]+1;
	st[i]=++dc;
	dfn[dc]=i;
	for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
	{
		int v=edg[tmp].to;
		if(v==f)
			continue;
		dfs(v,i);
	}
	ed[i]=++dc;
	dfn[dc]=i;
}
void pre()
{
	for(int i=1;i<=n;i++)
		anc[i][0]=fa[i];
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=17;i>=0;i--)
		if(dep[x]-(1<<i)>=dep[y])
			x=anc[x][i];
	if(x==y)
		return x;
	for(int i=17;i>=0;i--)
		if(anc[x][i]!=anc[y][i])
			x=anc[x][i],y=anc[y][i];
	return anc[x][0];	
}
void update(int x)
{
	x=dfn[x];
	if(md[x])
	{
		vis[c[x]]--;
		if(!vis[c[x]])
			ans--;
		md[x]=0;
	}
	else
	{
		if(!vis[c[x]])
			ans++;
		vis[c[x]]++;
		md[x]=1;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int sz=sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]),a[i]=c[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		c[i]=lower_bound(a+1,a+n+1,c[i])-a;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		build(u,v);
		build(v,u);
	}
	dfs(1,0);
	pre();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(st[x]>st[y])
			swap(x,y);
		int p=lca(x,y);
		if(p==x)
		{
			q[i].l=st[x];
			q[i].lb=st[x]/sz;
			q[i].r=st[y];
			q[i].id=i;
		}
		else
		{
			q[i].l=ed[x];
			q[i].lb=ed[x]/sz;
			q[i].r=st[y];
			q[i].p=p;
			q[i].id=i;
		}
	}
	sort(q+1,q+m+1,cmp);
	l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l)
			update(l),l++;
		while(l>q[i].l)
			l--,update(l);
		while(r<q[i].r)
			r++,update(r);
		while(r>q[i].r)
			update(r),r--;
		if(st[q[i].p])
			update(st[q[i].p]);
		fans[q[i].id]=ans;
		if(q[i].p)
			update(st[q[i].p]);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",fans[i]);
}

WC2013 糖果公园

那么很显然把以上两种算法结合一下就好了

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+1e3+7;
struct node{
	int ne,to;
}edg[N*2+1];
int co,cq;
struct Query{
	int l,r,lb,rb,p,x,id;
}q[N*2+1];
struct Modify{
	int x,y,last;
}o[N*2+1];
bool cmp(Query a,Query b)
{
	return a.lb<b.lb||(a.lb==b.lb&&(a.rb<b.rb||(a.rb==b.rb&&a.x<b.x)));
}
int n,m,c[N],w[N],d[N],Q,head[N],cnt,last[N];
int anc[N][18],fa[N],st[N],ed[N],L,R,now,dep[N],dfn[N*2+1],dc,md[N],vis[N];
ll fans[N],ans;
void build(int u,int v)
{
	++cnt;
	edg[cnt].to=v;
	edg[cnt].ne=head[u];
	head[u]=cnt;
}
void dfs(int i,int f)
{
	fa[i]=f;
	dep[i]=dep[f]+1;
	st[i]=++dc;
	dfn[dc]=i;
	for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
	{
		int v=edg[tmp].to;
		if(v==f)
			continue;
		dfs(v,i);
	}
	ed[i]=++dc;
	dfn[dc]=i;
}
void pre()
{
	for(int i=1;i<=n;i++)
		anc[i][0]=fa[i];
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=17;i>=0;i--)
		if(dep[x]-(1<<i)>=dep[y])
			x=anc[x][i];
	if(x==y)
		return x;
	for(int i=17;i>=0;i--)
		if(anc[x][i]!=anc[y][i])
			x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
void update(int x)
{
	x=dfn[x];
	if(md[x])
	{
		ans-=1ll*d[vis[c[x]]]*w[c[x]];
		vis[c[x]]--;
		md[x]=0;
	}
	else
	{
		vis[c[x]]++;
		ans+=1ll*d[vis[c[x]]]*w[c[x]];
		md[x]=1;
	}
}
void change(int x,int y)
{
	if(md[x])
	{
		ans-=1ll*d[vis[c[x]]]*w[c[x]];
		vis[c[x]]--;
		c[x]=y;
		vis[c[x]]++;
		ans+=1ll*d[vis[c[x]]]*w[c[x]];
	}
	else
		c[x]=y;
}
int main()
{
	scanf("%d%d%d",&n,&m,&Q);
	int sz=sqrt(pow((double)n,1.333));
	for(int i=1;i<=m;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&d[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		build(u,v);
		build(v,u);
	}
	dfs(1,0);
	pre();
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]),last[i]=c[i];
	for(int i=1;i<=Q;i++)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==0)
		{
			++co;
			o[co].x=x;
			o[co].y=y;
			o[co].last=last[x];
			last[x]=y;
		}
		else
		{
			++cq;
			int p=lca(x,y);
			if(st[x]>st[y])
				swap(x,y);
			if(p==x)
			{
				q[cq].l=st[x];
				q[cq].r=st[y];
				q[cq].lb=st[x]/sz;
				q[cq].rb=st[y]/sz;
				q[cq].x=co;
				q[cq].id=i;
			}
			else
			{
				q[cq].l=ed[x];
				q[cq].r=st[y];
				q[cq].lb=ed[x]/sz;
				q[cq].rb=st[y]/sz;
				q[cq].p=p;
				q[cq].x=co;
				q[cq].id=i;
			}
		}
	}
	sort(q+1,q+cq+1,cmp);
	L=1,R=0,now=0;
	for(int i=1;i<=cq;i++)
	{
		while(now<q[i].x)
			now++,change(o[now].x,o[now].y);
		while(now>q[i].x)
			change(o[now].x,o[now].last),now--;
		while(L<q[i].l)
			update(L),L++;
		while(L>q[i].l)
			L--,update(L);
		while(R>q[i].r)
			update(R),R--;
		while(R<q[i].r)
			R++,update(R);
		if(q[i].p)
			update(st[q[i].p]);
		fans[q[i].id]=ans;
		if(q[i].p)
			update(st[q[i].p]);
	}
	for(int i=1;i<=Q;i++)
		if(fans[i])
			printf("%lld\n",fans[i]);
}