LG-P3603 雪辉 Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个点的树，存在点权，多次询问每次给定多对点分别表示一条树链，求所有树链中有多少不同点权，及其点权的 $\mathrm{mex}$$\operatorname{mex}$。强制在线。

Solution

首先看到计算不同点权和求 $\mathrm{mex}$$\operatorname{mex}$ 且值域不大，自然想到 bitset，当我们求得答案的 bitset，我们只需要调用 count() 即可获得点权种类数，将其取反后，调用 _Find_first() 即可获得 $\mathrm{mex}$$\operatorname{mex}$。且上述所有操作均会除去一个 bitset 特有的，$w$$w$ 的复杂度。

这里的 $w$$w$ 根据编译器版本一般为 $32$$32$ 或 $64$$64$，且这里记作 $w$$w$ 而不是 $\omega$$\omega$ 是因为个人认为理解为 word 较为合理。

考虑如何维护，首先提供一个十分显然的思路，对原树进行树剖，然后在线段树上每个节点均开一个 bitset 建树，令 $v$$v$ 表示点权，这样的复杂度显然是 $O({\displaystyle \frac{nv}{w}})$$O(\dfrac{nv}{w})$ 的，而对于每次询问，直接查询并强行合并，分析这样的复杂度：树剖有一只 $O(\log n)$$O(\log n)$，线段树上查询的节点数是 $O(\log n)$$O(\log n)$，每次合并需要 $O({\displaystyle \frac{v}{w}})$$O(\dfrac{v}{w})$，若共 $q$$q$ 次询问则最终复杂度 $O({\displaystyle \frac{qv{\log }^{2}n}{w}})$$O(\dfrac{qv\log^2 n}{w})$，显然无法通过，但是本题似乎限制较小，这样也可以通过。

考虑分析上述做法的空间复杂度，显然为 $O({\displaystyle \frac{nv}{w}})$$O(\dfrac{nv}{w})$，但是线段树一般有一个 $4$$4$ 的空间常数，简单计算发现精细实现后大致需要 $262413$$262413$，这样大致需要 1GiB，考虑优化，显然对于线段树的底层每个点仅维护了一个数，而倒数第二层每个点仅维护了两个数，于是不难想到我们将倒数这两层改为用 pair 维护即可，这样可以去掉 $131072+65536$$131072 + 65536$ 左右个 bitset 的空间复杂度，优化极大，空间冗余较多，实现平凡。

下面提供一个来自 @Zpair 的高妙思路，可以将复杂度去掉一只 $O(\log n)$$O(\log n)$，显然这样的复杂度就是理论正确的了。即考虑在树剖后每个重链上维护这整个重链的 bitset，同时类似上文维护线段树，对于每次询问中，所有整个重链的查询直接调用，容易证明残缺的重链查询最多有 $3$$3$ 次，可以认为是常数，故优化掉一只 $O(\log n)$$O(\log n)$，容易证明这样的复杂度在当前时空限制是可以通过的。同时若空间无法通过还可考虑对于所有点数小于 ${\displaystyle \frac{v}{w}}$$\dfrac{v}{w}$ 的直接用 basic_string 维护，这样可以更进一步地大幅优化空间。

当然这里因为前者虽然复杂度错误但常数不大可以通过，于是这里直接挂前者的代码了。

Code

xxxxxxxxxx
148
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3
#include <bitset>
4

5
#define PI M_PI
6
#define E M_E
7
#define npt nullptr
8
#define SON i->to
9
#define OPNEW void* operator new(size_t)
10
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
11
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
12

13
using namespace std;
14

15
mt19937 rnd(random_device{}());
16
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17
bool rnddd(int x){return rndd(1, 100) <= x;}
18

19
typedef unsigned int uint;
20
typedef unsigned long long unll;
21
typedef long long ll;
22
typedef long double ld;
23

24
#define LIM (110000)
25

26
template < typename T = int >
27
inline T read(void);
28

29
int N, Q, F;
30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    OPNEW;
34
}ed[LIM << 1];
35
ROPNEW;
36
Edge* head[LIM];
37
int val[LIM];
38
int lst(0);
39

40
int dep[LIM], hson[LIM], top[LIM], fa[LIM], siz[LIM], dfn[LIM], idx[LIM];
41

42
void dfs_pre(int p = 1, int fa = 0){
43
    ::fa[p] = fa, dep[p] = dep[fa] + 1, siz[p] = 1;
44
    for(auto i = head[p]; i; i = i->nxt){
45
        if(SON == fa)continue;
46
        dfs_pre(SON, p);
47
        siz[p] += siz[SON];
48
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
49
    }
50
}
51
void dfs_make(int p = 1, int top = 1){
52
    static int cdfn(0);
53
    dfn[p] = ++cdfn, idx[cdfn] = p;
54
    ::top[p] = top;
55
    if(hson[p])dfs_make(hson[p], top);
56
    for(auto i = head[p]; i; i = i->nxt){
57
        if(SON == fa[p] || SON == hson[p])continue;
58
        dfs_make(SON, SON);
59
    }
60
}
61

62
class SegTree{
63
private:
64
    //sum is 262143
65
    bitset < 30010 > tr[120000];
66
    pair < int, int > base[LIM << 2];
67
    #define LS (p << 1)
68
    #define RS (LS | 1)
69
    #define MID ((gl + gr) >> 1)
70
public:
71
    void Pushup(int p, int gl, int gr){
72
        if(gr - gl + 1 <= 2)return;
73
        if(MID - gl + 1 == 1)tr[p][base[LS].first] = true;
74
        else if(MID - gl + 1 == 2)tr[p][base[LS].first] = tr[p][base[LS].second] = true;
75
        else tr[p] |= tr[LS];
76
        if(gr - (MID + 1) + 1 == 1)tr[p][base[RS].first] = true;
77
        else if(gr - (MID + 1) + 1 == 2)tr[p][base[RS].first] = tr[p][base[RS].second] = true;
78
        else tr[p] |= tr[RS];
79
    }
80
    void Build(int p = 1, int gl = 1, int gr = N){
81
        if(gl == gr)return base[p] = {val[idx[gl = gr]], -1}, void();
82
        if(gr - gl + 1 == 2)base[p] = {val[idx[gl]], val[idx[gr]]};
83
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
84
        Pushup(p, gl, gr);
85
    }
86
    auto Query(int l, int r, int p = 1, int gl = 1, int gr = N){
87
        bitset < 30010 > ret; ret.reset();
88
        if(l <= gl && gr <= r){
89
            if(gl == gr){ret[base[p].first] = true; return ret;}
90
            if(gr - gl + 1 == 2){ret[base[p].first] = ret[base[p].second] = true; return ret;}
91
            return tr[p];
92
        }
93
        if(l <= MID)ret |= Query(l, r, LS, gl, MID);
94
        if(r >= MID + 1)ret |= Query(l, r, RS, MID + 1, gr);
95
        return ret;
96
    }
97
}st;
98

99
auto Query(int s, int t){
100
    bitset < 30010 > ret; ret.reset();
101
    while(top[s] != top[t]){
102
        if(dep[top[s]] < dep[top[t]])swap(s, t);
103
        ret |= st.Query(dfn[top[s]], dfn[s]);
104
        s = fa[top[s]];
105
    }if(dep[s] < dep[t])swap(s, t);
106
    ret |= st.Query(dfn[t], dfn[s]);
107
    return ret;
108
}
109

110
int main(){
111
    N = read(), Q = read(), F = read();
112
    for(int i = 1; i <= N; ++i)val[i] = read();
113
    for(int i = 1; i <= N - 1; ++i){
114
        int s = read(), t = read();
115
        head[s] = new Edge{head[s], t};
116
        head[t] = new Edge{head[t], s};
117
    }dfs_pre(), dfs_make();
118
    st.Build();
119
    while(Q--){
120
        int M = read();
121
        bitset < 30010 > ans; ans.reset();
122
        for(int i = 1; i <= M; ++i){
123
            int s = read() ^ (lst * F), t = read() ^ (lst * F);
124
            ans |= Query(s, t);
125
        }
126
        int ans1 = ans.count(), ans2 = (~ans)._Find_first();
127
        lst = ans1 + ans2;
128
        printf("%d %d\n", ans1, ans2);
129
    }
130
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
131
    return 0;
132
}
133

134
template < typename T >
135
inline T read(void){
136
    T ret(0);
137
    int flag(1);
138
    char c = getchar();
139
    while(c != '-' && !isdigit(c))c = getchar();
140
    if(c == '-')flag = -1, c = getchar();
141
    while(isdigit(c)){
142
        ret *= 10;
143
        ret += int(c - '0');
144
        c = getchar();
145
    }
146
    ret *= flag;
147
    return ret;
148
}

UPD

update-2023_02_17 初稿