Steven_MengのBlog

首先,乖♂乖♂交♂出数据生成器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
inline int gen(){
return (rand()<<15)|(rand());
}
int main(){
srand(time(NULL));
int n=1000,m=1000;
printf("%d %d\n",n,m);
for (register int i=1;i<=n;++i){
printf("%d ",gen()%10+1);
}
printf("\n");
for (register int i=2;i<=n;++i){
printf("%d %d\n",i,gen()%(i-1)+1);
}
printf("\n");
for (register int i=1;i<=m;++i){
int opr=(rand()%10==0)?1:2;
printf("%d %d\n",opr,gen()%n+1);
}
}

使用printf(“%d “,gen()%10+1);是因为如果$val[i]$的范围太大,数据基本上全是$0$。

所以这题的数据范围是假的,当然最后一个点是真·数据范围。

为什么int opr=(rand()%10==0)?1:2;呢?,是因为换♂根太多也不好啊。


$30pts$

真·大暴力,每次求出颜色总数,根据组合数算一下就可以了:

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
int col[MAXN];
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 nowu;
int val[MAXN];
void dfs(int u,int father,bool in){
if (u==nowu) in=true;
if (in) col[val[u]]++;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father){
dfs(v,u,in);
}
}
}
int main(){
int n=read(),m=read();
for (register int i=1;i<=n;++i) val[i]=read();
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
int rt=1;
for (register int i=1;i<=m;++i){
int opr=read();
if (opr==1) rt=read();
else {
nowu=read();
memset(col,0,sizeof(col));
dfs(rt,rt,0);
int ans=0;
for (register int i=1;i<=n;++i){
if (col[i]>1) ans+=col[i]*(col[i]-1)/2;
}
printf("%d\n",ans);
}
}
}

100pts

考虑莫队,首先,参考这篇题解,你就会发现这个换根是假的。

前两种情况,就是查询$[1,n]$和$[L[u],R[u]]$直接放进一个莫队里面搞就可以了,但是别忘了还要查询$[1,L[v]-1]$,$[R[v]+1,n]$,如果$i$,$j$都在$[1,L[v]-1]$,或者都在$[R[v]+1,n]$还是可以套用上面的方法,如果$i$在$[1,L[v]-1]$,$j$在$[R[v]+1,n]$的话,怎么搞呢?

我想了一个笨办法,再开一个莫队就可以了,询问$i \in[1,l],j \in [r,n]$之间数对的个数,最后加起来就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
if (u==rt){
AddQuery1(1,n,qu);
}
else if (LCA(u,rt)==u){
int v=Hop(rt,u);
if (L[v]>1) AddQuery1(1,L[v]-1,qu);
if (R[v]<n) AddQuery1(R[v]+1,n,qu);
AddQuery2(L[v]-1,R[v]+1,qu);
}
else {
AddQuery1(L[u],R[u],qu);
}

献上写得很丑的标算,注意要开$\text{long long}$,我应该刻意卡了$\text {int}$:

时间复杂度$O(n \sqrt 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
#include <bits/stdc++.h>
#define MAXN 500005
#define MAXM 19
#define int long long
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],dfn,seq[MAXN];
int anc[MAXN][MAXM],dep[MAXN];
int val[MAXN],n,m;
void dfs(int u,int father){
seq[L[u]=++dfn]=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]=dfn;
}
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;
}
int pos[MAXN],rt;
struct Query1{
int l,r;//表示询问[l,r]内相同的数对个数
int id;
}q1[MAXN];
inline bool operator < (const Query1 &a,const Query1 &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
struct Query2{
int l,r;//表示询问[1,l][r,n]之间相同数对的个数
int id;
}q2[MAXN];
inline bool operator < (const Query2 &a,const Query2 &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int c1,c2;
inline void AddQuery1(int l,int r,int id){q1[++c1]=Query1{l,r,id};}
inline void AddQuery2(int l,int r,int id){q2[++c2]=Query2{l,r,id};}
int cnt[MAXN];
int cnt1[MAXN],cnt2[MAXN];
long long Ans[MAXN],ans;
inline void Add(int x){
++cnt[x],ans+=(cnt[x]-1);//除去自己
}
inline void Del(int x){
ans-=(cnt[x]-1),--cnt[x];
}
#undef int
int main(){
#define int long long
n=read(),m=read();
for (register int i=1;i<=n;++i){
val[i]=read();
}

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;
int qu=0;
for (register int i=1;i<=m;++i){
int opr=read();
if (opr==1){
rt=read();
}
else {
qu++;
int u=read();
if (u==rt){
AddQuery1(1,n,qu);
}
else if (LCA(u,rt)==u){
int v=Hop(rt,u);
if (L[v]>1) AddQuery1(1,L[v]-1,qu);
if (R[v]<n) AddQuery1(R[v]+1,n,qu);
AddQuery2(L[v]-1,R[v]+1,qu);
}
else {
AddQuery1(L[u],R[u],qu);
}
}
}
//to compelete Query1
sort(q1+1,q1+1+c1);
int l=1,r=0;
ans=0;
for (register int i=1;i<=c1;++i){
while (l<q1[i].l) Del(seq[l++]);
while (l>q1[i].l) Add(seq[--l]);
while (r<q1[i].r) Add(seq[++r]);
while (r>q1[i].r) Del(seq[r--]);
Ans[q1[i].id]+=ans;
}

//to compelete Query2
sort(q2+1,q2+1+c2);
l=0,r=n+1;
ans=0;
for (register int i=1;i<=c2;++i){
while (l<q2[i].l){
++cnt1[seq[++l]];
ans+=cnt2[seq[l]];
}
while (l>q2[i].l){
--cnt1[seq[l]];
ans-=cnt2[seq[l--]];
}
while (r<q2[i].r){
--cnt2[seq[r]];
ans-=cnt1[seq[r++]];
}
while (r>q2[i].r){
++cnt2[seq[--r]];
ans+=cnt1[seq[r]];
}
Ans[q2[i].id]+=ans;
}
for (register int i=1;i<=qu;++i){
printf("%lld\n",Ans[i]);
}
}

这道题$O(n \log n)$预处理$O(1)$查询的方法应该也有,但是我太菜了,不想写。

你们写出来就可以爆碾标算了。

最后一个点出锅了,正在修复

 评论