「CodeChef WALKBT」Walks on the binary tree

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

CodeChef WALKBT

一棵高度为 $n$ 的满二叉树（节点数为 $2^{n+1}-1$），用一个 $[0,2^n)$ 的数 $X$ 表示一条根到叶子的路径（从最高位开始，为0则走左儿子，否则走右儿子）。

初始 $X = 0$，有两种操作共 $q$ 个：

  • 将 $X$ 改为 $(X + 2^C) \bmod 2^n$，然后从根出发走到叶子。
  • 询问当前有多少个节点至少被访问一次。

$n,q\le 10^5$。

主要思路

考虑一次新增的节点数，不难发现是 $n$ 减去新的 $X$ 与之前所有数的 lcp 的最大值。
不难发现这个最大值必然在新 $X$ 的前驱或后继中取得。

考虑加上 $2^C$ 的操作，实质上是把前面的一段1赋为0，把一个0赋为1。
于是每个修改操作只会改变均摊 $O(1)$ 个位置。
于是可以上棵可持久化线段树维护每个位的值。

那么如何比较大小？
可以在可持久化线段树上二分第一个两数不同的位置，然后 $O(\log n)$ 比较。
那么我们希望能够 $O(1)$ 比较两棵线段树上的一个区间是否完全相等。
这个哈希一下就好了。

于是我们获得了一个 $O(\log n)$ 比较大小的方法，再套个set维护前驱后继就 $O(n\log^2n)$ 走了。

然后这题被出到模拟赛里有人被卡常了，所以是 CC 太快还是 CC 数据水啊（

参考代码

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef long long i64;
typedef const int CI;
#define fr first
#define sc second
#define MP make_pair
#define Templ(T) template <typename T>
inline int read() {
    Rint ans = 0;
    reg char c = getchar();
    while (!isdigit(c)) c = getchar();
    for (; isdigit(c); c = getchar())
        ans = ans * 10 + c - '0';
    return ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define m1 88888901
#define m2 77777803
} // namespace my_std
using namespace my_std;

#define N 200010
int pw1[N], pw2[N];
const bool init = [&](){
    *pw1 = *pw2 = 1;
    FOR(i, 1, N - 1){
        pw1[i] = (pw1[i - 1] << 1) % m1;
        pw2[i] = (pw2[i - 1] << 1) % m2;
    }
    return true;
}();

int n, q;

int rt[N], lc[N << 5], rc[N << 5], s1[N << 5], s2[N << 5];
int tt, cc;

#define lt lc[t]
#define rt rc[t]
#define ls lc[s]
#define rs rc[s]
#define f1 s1[t]
#define f2 s2[t]
#define g1 s1[s]
#define g2 s2[s]
void upd(int &t, CI &s, CI &l, CI &r, CI &p, CI &v){
    t = ++cc;
    lt = ls, rt = rs;
    f1 = g1, f2 = g2;
    if(l == r) return f1 = f2 = v, void();
    CI mid = (l + r) >> 1;
    if(p <= mid) upd(lt, ls, l, mid, p, v);
    else upd(rt, rs, mid + 1, r, p, v);
    f1 = (s1[lt] + (i64)pw1[mid - l + 1] * s1[rt]) % m1;
    f2 = (s2[lt] + (i64)pw2[mid - l + 1] * s2[rt]) % m2;
}
int is_1(CI &t, CI &l, CI &r, CI &p){
    if(!t) return 0;
    if(l == r) return s1[t];
    CI mid = (l + r) >> 1;
    if(p <= mid) return is_1(lt, l, mid, p);
    else return is_1(rt, mid + 1, r, p);
}
pair<bool, int> cpr(CI &t, CI &s, CI &l, CI &r){
    if(l == r) return MP(f1 <= g1, f1 == g1 ? -1 : l);
    CI mid = (l + r) >> 1;
    if(s1[rt] == s1[rs] && s2[rt] == s2[rs])
        return cpr(lt, ls, l, mid);
    else return cpr(rt, rs, mid + 1, r);
}
#undef lt
#undef rt
#undef ls
#undef rs
#undef f1
#undef f2
#undef g1
#undef g2

#define upd(p, v) \
    ++tt, upd(rt[tt], rt[tt - 1], 0, n - 1, p, v)
#define cpr(t, s) \
    cpr(t, s, 0, n - 1)

struct cmp{
    inline bool operator()(CI &x, CI &y)const{
        return cpr(rt[x], rt[y]).fr;
    }
};

typedef set<int, cmp> SCI;
SCI st;
i64 ans;

inline void work(){
    ans = 0, tt = 0, cc = 0;
    st.clear();
    n = read(), q = read();
    FOR(o, 1, q){
        char c = getchar();
        while(c != '!' && c != '?') c = getchar();
        if(c == '?'){
            printf("%lld\n", ans ? ans : 1);
            continue;
        }
        int x = read();
        while(x < n && is_1(rt[tt], 0, n - 1, x)) upd(x++, 0);
        if(x < n) upd(x, 1);
        SCI::iterator i = st.insert(tt).fr, nxt = next(i), pre = prev(i);
        int res = n;
        if(i != st.begin())
            chkmin(res, cpr(rt[*i], rt[*pre]).sc);
        if(nxt != st.end())
            chkmin(res, cpr(rt[*i], rt[*nxt]).sc);
        ans += res + 1;
        // printf("%lld\n", ans);
    }
}

int main() {
    int esac = read();
    while(esac--) work();
    return 0;
}