LG-P3603 雪辉 Solution
目录更好的阅读体验戳此进入
题面
给定 $ n $ 个点的树，存在点权，多次询问每次给定多对点分别表示一条树链，求所有树链中有多少不同点权，及其点权的 $ \operatorname{mex} $。强制在线。
Solution
首先看到计算不同点权和求 $ \operatorname{mex} $ 且值域不大，自然想到 bitset，当我们求得答案的 bitset，我们只需要调用 count() 即可获得点权种类数，将其取反后，调用 _Find_first() 即可获得 $ \operatorname{mex} \(。且上述所有操作均会除去一个 `bitset` 特有的，\) w $ 的复杂度。
这里的 $ w $ 根据编译器版本一般为 $ 32 $ 或 $ 64 $，且这里记作 $ w $ 而不是 $ \omega $ 是因为个人认为理解为 word 较为合理。
考虑如何维护，首先提供一个十分显然的思路，对原树进行树剖，然后在线段树上每个节点均开一个 bitset 建树，令 $ v $ 表示点权，这样的复杂度显然是 $ O(\dfrac{nv}{w}) $ 的，而对于每次询问，直接查询并强行合并，分析这样的复杂度：树剖有一只 $ O(\log n) $，线段树上查询的节点数是 $ O(\log n) $，每次合并需要 $ O(\dfrac{v}{w}) $，若共 $ q $ 次询问则最终复杂度 $ O(\dfrac{qv\log^2 n}{w}) $，显然无法通过，但是本题似乎限制较小，这样也可以通过。
考虑分析上述做法的空间复杂度，显然为 $ O(\dfrac{nv}{w}) $，但是线段树一般有一个 $ 4 $ 的空间常数，简单计算发现精细实现后大致需要 $ 262413 $，这样大致需要 1GiB，考虑优化，显然对于线段树的底层每个点仅维护了一个数，而倒数第二层每个点仅维护了两个数，于是不难想到我们将倒数这两层改为用 pair 维护即可，这样可以去掉 $ 131072 + 65536 $ 左右个 bitset 的空间复杂度，优化极大，空间冗余较多，实现平凡。
下面提供一个来自 @Zpair 的高妙思路，可以将复杂度去掉一只 $ O(\log n) $，显然这样的复杂度就是理论正确的了。即考虑在树剖后每个重链上维护这整个重链的 bitset，同时类似上文维护线段树，对于每次询问中，所有整个重链的查询直接调用，容易证明残缺的重链查询最多有 $ 3 $ 次，可以认为是常数，故优化掉一只 $ O(\log n) $，容易证明这样的复杂度在当前时空限制是可以通过的。同时若空间无法通过还可考虑对于所有点数小于 $ \dfrac{v}{w} $ 的直接用 basic_string 维护，这样可以更进一步地大幅优化空间。
当然这里因为前者虽然复杂度错误但常数不大可以通过，于是这里直接挂前者的代码了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <bitset>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define LIM (110000)
template < typename T = int >
inline T read(void);
int N, Q, F;
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[LIM << 1];
ROPNEW;
Edge* head[LIM];
int val[LIM];
int lst(0);
int dep[LIM], hson[LIM], top[LIM], fa[LIM], siz[LIM], dfn[LIM], idx[LIM];
void dfs_pre(int p = 1, int fa = 0){
::fa[p] = fa, dep[p] = dep[fa] + 1, siz[p] = 1;
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
dfs_pre(SON, p);
siz[p] += siz[SON];
if(siz[SON] > siz[hson[p]])hson[p] = SON;
}
}
void dfs_make(int p = 1, int top = 1){
static int cdfn(0);
dfn[p] = ++cdfn, idx[cdfn] = p;
::top[p] = top;
if(hson[p])dfs_make(hson[p], top);
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa[p] || SON == hson[p])continue;
dfs_make(SON, SON);
}
}
class SegTree{
private:
//sum is 262143
bitset < 30010 > tr[120000];
pair < int, int > base[LIM << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
void Pushup(int p, int gl, int gr){
if(gr - gl + 1 <= 2)return;
if(MID - gl + 1 == 1)tr[p][base[LS].first] = true;
else if(MID - gl + 1 == 2)tr[p][base[LS].first] = tr[p][base[LS].second] = true;
else tr[p] |= tr[LS];
if(gr - (MID + 1) + 1 == 1)tr[p][base[RS].first] = true;
else if(gr - (MID + 1) + 1 == 2)tr[p][base[RS].first] = tr[p][base[RS].second] = true;
else tr[p] |= tr[RS];
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return base[p] = {val[idx[gl = gr]], -1}, void();
if(gr - gl + 1 == 2)base[p] = {val[idx[gl]], val[idx[gr]]};
Build(LS, gl, MID), Build(RS, MID + 1, gr);
Pushup(p, gl, gr);
}
auto Query(int l, int r, int p = 1, int gl = 1, int gr = N){
bitset < 30010 > ret; ret.reset();
if(l <= gl && gr <= r){
if(gl == gr){ret[base[p].first] = true; return ret;}
if(gr - gl + 1 == 2){ret[base[p].first] = ret[base[p].second] = true; return ret;}
return tr[p];
}
if(l <= MID)ret |= Query(l, r, LS, gl, MID);
if(r >= MID + 1)ret |= Query(l, r, RS, MID + 1, gr);
return ret;
}
}st;
auto Query(int s, int t){
bitset < 30010 > ret; ret.reset();
while(top[s] != top[t]){
if(dep[top[s]] < dep[top[t]])swap(s, t);
ret |= st.Query(dfn[top[s]], dfn[s]);
s = fa[top[s]];
}if(dep[s] < dep[t])swap(s, t);
ret |= st.Query(dfn[t], dfn[s]);
return ret;
}
int main(){
N = read(), Q = read(), F = read();
for(int i = 1; i <= N; ++i)val[i] = read();
for(int i = 1; i <= N - 1; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}dfs_pre(), dfs_make();
st.Build();
while(Q--){
int M = read();
bitset < 30010 > ans; ans.reset();
for(int i = 1; i <= M; ++i){
int s = read() ^ (lst * F), t = read() ^ (lst * F);
ans |= Query(s, t);
}
int ans1 = ans.count(), ans2 = (~ans)._Find_first();
lst = ans1 + ans2;
printf("%d %d\n", ans1, ans2);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_02_17 初稿
标签：LG,int,题解,复杂度,ret,SON,雪辉,top,bitset From： https://www.cnblogs.com/tsawke/p/17180236.html