题意
给定一棵 $n$ 个点的无根树, 点带权. $q$ 次询问, 每次给定树上的若干路径, 求这些路径上的点共有多少种不同权值以及这些点的权值组成的集合的 $\operatorname{mex}$.
$n,q\le1\times 10^5,v_i\le30000$. 部分测试点强制在线.
题解
首先吐槽一下沙雕考试出题人又出原题
这个只有 $30000$ 的值域明示要用 std::bitset 趴…
然后发现这个 std::bitset 的标准接口不滋磁查 lowbit, 于是 $\operatorname{mex}$ 就没法求了…(于是沙雕rvalue就手写了一个)
然后按照套路树剖一下把树链拆成 DFS 序上的 $\log$ 段区间, 然后变成求若干段区间的 bitset 的并. 发现数据范围刚好允许开 $O(n)$ 个 bitset, 那么直接对 DFS 序分块, 然后把一段连续的块的 bitset 都求出来, 这样查询的时候就可以只处理两端的散块了.
对于一次查询, 首先树剖出若干个区间, 然后发现这一坨区间可能有很多重复, 我们随手排个序把相交的区间都并起来. 直接在预处理好的连续块数据上增量构造就可以了.
时间复杂度好像是 $O\left(n\left(\sqrt n+\frac V w\right)+q\left(\sqrt n\log n+\frac V w\right)\right)$. 实测跑得巨快无比. 大概是因为复杂度中 $O(q \sqrt n \log n)$ 的部分因为无法造出每条树链长度都达到 $O(\sqrt n)$ 的同时剖出来的树链数量达到 $\log n$ 的路径而跑不满趴(树链数量增加必然导致整树深度变浅)…神仙 hzoizcl 说这个那个 $O(\sqrt n \log n)$ 实际只能达到 $O\left(\log\left (\sqrt n^{\sqrt n}\right)\right)$ 级别qaq…(这个值大概是 $2\texttt{k}$ 左右于是复杂度好像没毛病)
参考代码
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
201
202
203
|
#include <bits/stdc++.h>
const int SQRN=320;
const int MAXV=1e5+10;
const int MAXE=2e5+10;
typedef unsigned int uint;
struct Edge{
int from;
int to;
Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* topE=E;
struct Bits{
static const int MAXL=940;
uint data[MAXL];
Bits(){}
inline void operator|=(const Bits& b){
for(int i=0;i<MAXL;i++)
this->data[i]|=b.data[i];
}
inline int count(){
int ans=0;
for(int i=0;i<MAXL;i++)
ans+=__builtin_popcount(this->data[i]);
return ans;
}
inline int mex(){
for(int i=0;i<MAXL;i++){
if(__builtin_popcount(this->data[i])!=32){
for(int j=0;j<32;j++)
if(((this->data[i]>>j)&1)==0)
return (i<<5)|j;
}
}
return MAXL<<5;
}
inline void set(int p){
this->data[p>>5]|=(1u<<(p&31));
}
};
Bits s[SQRN][SQRN];
Bits ans;
int n;
int q;
int clk;
int sqrn;
int blk[MAXV];
int dfn[MAXV];
int val[MAXV];
int pos[MAXV];
int prt[MAXV];
int top[MAXV];
int son[MAXV];
int deep[MAXV];
int size[MAXV];
int cur;
std::pair<int,int> R[MAXV];
void Merge();
void DFS(int,int);
void Export(int,int);
inline int ReadInt();
void DFS(int,int,int);
inline void Insert(int,int);
int main(){
int T;
n=ReadInt(),q=ReadInt(),T=ReadInt();
sqrn=sqrt(n+0.5);
for(int i=1;i<=n;i++)
val[i]=ReadInt();
for(int i=1;i<n;i++){
int a=ReadInt(),b=ReadInt();
Insert(a,b);
Insert(b,a);
}
DFS(1,0,0);
DFS(1,1);
for(int i=0;i*sqrn<n;i++){
for(int j=i;j*sqrn<n;j++){
if(j>i)
s[i][j]=s[i][j-1];
for(int k=j*sqrn;blk[k]==j&&k<n;k++)
s[i][j].set(val[pos[k]]);
}
}
// Query;
int lastans=0;
for(int i=0;i<q;i++){
memset(ans.data,0,sizeof(ans.data));
int cnt=ReadInt();
cur=0;
while(cnt--){
int a=ReadInt()^(lastans*T),b=ReadInt()^(lastans*T);
Export(a,b);
}
Merge();
for(int i=0;i<cur;i++){
int l=R[i].first,r=R[i].second;
if(blk[l]==blk[r]){
for(int i=l;i<=r;i++)
ans.set(val[pos[i]]);
}
else{
if(blk[l]<blk[r]-1)
ans|=s[blk[l]+1][blk[r]-1];
for(int i=l;blk[i]==blk[l];i++)
ans.set(val[pos[i]]);
for(int i=r;blk[i]==blk[r];i--)
ans.set(val[pos[i]]);
}
// printf("%d %d %d\n",ans.data[0],ans.data[1],ans.data[2]);
}
int x=ans.count(),y=ans.mex();
printf("%d %d\n",x,y);
lastans=x+y;
}
return 0;
}
void Export(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])
std::swap(x,y);
R[cur++]=std::make_pair(dfn[top[x]],dfn[x]);
x=prt[top[x]];
}
if(deep[x]>deep[y])
std::swap(x,y);
R[cur++]=std::make_pair(dfn[x],dfn[y]);
}
void Merge(){
int cnt=cur;
std::sort(R,R+cnt);
int l=R[0].first,r=R[0].second;
for(int i=1;i<cnt;i++){
if(R[i].first>r){
R[cur++]=std::make_pair(l,r);
l=R[i].first;
r=R[i].second;
}
else
r=std::max(r,R[i].second);
}
R[cur++]=std::make_pair(l,r);
}
void DFS(int root,int prt,int deep){
::prt[root]=prt;
::deep[root]=deep;
::size[root]=1;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(i->to!=prt){
DFS(i->to,root,deep+1);
size[root]+=size[i->to];
if(size[i->to]>size[son[root]])
son[root]=i->to;
}
}
}
void DFS(int root,int top){
::dfn[root]=clk;
::pos[clk]=root;
::blk[clk]=clk/sqrn;
++clk;
::top[root]=top;
if(son[root])
DFS(son[root],top);
for(Edge* i=head[root];i!=NULL;i=i->next)
if(i->to!=son[root]&&i->to!=prt[root])
DFS(i->to,i->to);
}
inline void Insert(int from,int to){
topE->from=from;
topE->to=to;
topE->next=head[from];
head[from]=topE++;
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
|
