Steven_MengのBlog

洛谷

LOJ

BZOJ

首先,考虑这样一个问题:给你一个序列${a_i}$,和四个数$l1,r1,l2,r2$,求区间$[l1,r1],[l2,r2]$中相同的数有多少对。

这个可以参见我出的一道题:相同颜色对

当然你不能维护四个指针,考虑容斥原理,我们不妨设$f(x,y)$为下标为$[1,x]$和下标为$[1,y]$中相同的$a_i$有多少对,这样我们可以开心地容斥$Query(l1,r1,l2,r2)=f(l2,r2)-f(l1-1,r2)-f(r1,l2-1)+f(l1-1,l2-1)$。

具体实现的时候,$Query$结构体里面存一个$f$代表符号即可。


回到本题,首先明确一件事情,这个换根其实是吓你的,

$1.$只有最近的一次换根才会对答案有影响(显然)

$2.$分情况讨论,我们始终以$1$节点为根,设现在查询的节点为$u$,上一次换根的根为$rt$($rt$是一个假的根) ,我们画出$3$个图:

若$u==rt$,显然现在查询的是整棵树,对应到区间$[1,n]$:

1
2
3
if (u==rt){//整棵树
A[++top]=1,B[top]=n;
}

若$LCA(u,rt)==u$(或者说$rt$在$u$的子树中),

我们想象一下,把$rt$从底下提上来,查询的就是红色圈圈起来的部分

再把这个红色圈圈起来的部分对应回去

原来就是整棵树去掉$v$的子树的部分,其中$v$为$u$的孩子,$rt$的祖先(可以树上倍增搞一下)

这个可以对应到两个区间$[1,L[v]-1]$,$[R[v]+1,n]$

1
2
3
4
5
else if (LCA(u,rt)==u){
int v=Hop(rt,u);//除去v的子树
if (L[v]>1) A[++top]=1,B[top]=L[v]-1;
if (R[v]<n) A[++top]=R[v]+1,B[top]=n;
}

最后一种情况,若$LCA(u,rt)!=u$,那么我们再画一个图:

发现这个换根和没换一样,所以就是查询区间$[L[u],R[u]]$

1
2
3
else{//换根相当于没换
A[++top]=L[u],B[top]=R[u];
}

好了,最重要的部分讲完了,剩下的都是细节,注意要离散化,开$\text{long long}$,具体实现时,可以开两个栈,把区间存进去,然后互相搞一下,如下:

1
2
3
4
5
for (register int j=1;j<=top1;++j){
for (register int k=1;k<=top2;++k){
RC(A1[j],B1[j],A2[k],B2[k],qu);
}
}

注意边界。

代码如下:

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
#include <bits/stdc++.h>
#define MAXN 500005
#define MAXM 19
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int L[MAXN],R[MAXN],cnt,seq[MAXN];
int anc[MAXN][MAXM],dep[MAXN];
int val[MAXN],n,m,temp[MAXN];
void dfs(int u,int father){
seq[L[u]=++cnt]=val[u];
anc[u][0]=father;
for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father){
dep[v]=dep[u]+1;
dfs(v,u);
}
}
R[u]=cnt;
}
inline int LCA(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
}
if (u==v) return u;
for (register int i=MAXM-1;i>=0;--i){
if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
}
return anc[u][0];
}
inline int Hop(int u,int v){//h♂p to v's son
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>dep[v]){
u=anc[u][i];
}
}
return u;
}
inline void discrete(){
for (register int i=1;i<=n;++i){
temp[i]=val[i];
}
sort(temp+1,temp+1+n);
for (register int i=1;i<=n;++i){
val[i]=lower_bound(temp+1,temp+1+n,val[i])-temp;
}
}
//用容斥转换成只有一个指针的莫队
int pos[MAXN],rt;
inline void Add(int u,int &top,int *A,int *B){//最核心的操作就在这里
if (u==rt){//整棵树
A[++top]=1,B[top]=n;
}
else if (LCA(u,rt)==u){
int v=Hop(rt,u);//除去v的子树
if (L[v]>1) A[++top]=1,B[top]=L[v]-1;
if (R[v]<n) A[++top]=R[v]+1,B[top]=n;
}
else{//换根相当于没换
A[++top]=L[u],B[top]=R[u];
}
}

int A1[MAXN],B1[MAXN],A2[MAXN],B2[MAXN];
int top1,top2;
struct Query{
int pos1,pos2;//代表的是[1,pos1],[1,pos2]
int id,f;//容斥的符号
}Q[MAXN*16];
inline bool operator < (const Query &a,const Query &b){
return pos[a.pos1]<pos[b.pos1]||(pos[a.pos1]==pos[b.pos1]&&((pos[a.pos1]&1)?a.pos2<b.pos2:a.pos2>b.pos2));
}
int qcnt;
inline void AddQuery(int pos1,int pos2,int id,int f){
if (pos1<=0||pos2<=0) return ;
if (pos1>pos2) swap(pos1,pos2);
Q[++qcnt].f=f,Q[qcnt].id=id,Q[qcnt].pos1=pos1,Q[qcnt].pos2=pos2;
}
inline void RC(int l1,int r1,int l2,int r2,int i){//容斥
AddQuery(r1,r2,i,1);
AddQuery(l1-1,r2,i,-1);
AddQuery(r1,l2-1,i,-1);
AddQuery(l1-1,l2-1,i,1);
}
long long Ans[MAXN];
int cnt1[MAXN],cnt2[MAXN];
int main(){
n=read(),m=read();
for (register int i=1;i<=n;++i){
val[i]=read();
}
discrete();
int Size=sqrt(n);
for (register int i=1;i<=n;++i){
pos[i]=(i-1)/Size+1;
}

for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
dfs(1,1);

rt=1;//因为只有每一次询问前最后一次换根才能起作用,所以只有记录一个rt
int qu=0;
for (register int i=1;i<=m;++i){
int opr=read();
if (opr==1){
rt=read();
}
else {
int u=read(),v=read();
qu++;
top1=top2=0;//清空栈
Add(u,top1,A1,B1);
Add(v,top2,A2,B2);
for (register int j=1;j<=top1;++j){
for (register int k=1;k<=top2;++k){
RC(A1[j],B1[j],A2[k],B2[k],qu);
}
}
}
}
sort(Q+1,Q+1+qcnt);
int r1=0,r2=0;
long long ans=0;
for (register int i=1;i<=qcnt;++i){
while (r1<Q[i].pos1){
++cnt1[seq[++r1]];
ans+=cnt2[seq[r1]];
}
while (r1>Q[i].pos1){
--cnt1[seq[r1]];
ans-=cnt2[seq[r1--]];
}
while (r2<Q[i].pos2){
++cnt2[seq[++r2]];
ans+=cnt1[seq[r2]];
}
while (r2>Q[i].pos2){
--cnt2[seq[r2]];
ans-=cnt1[seq[r2--]];
}
Ans[Q[i].id]+=(long long)Q[i].f*ans;
}
for (register int i=1;i<=qu;++i){
printf("%lld\n",Ans[i]);
}
}

 评论