「Ynoi2011」竞赛实验班

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

算是 Ynoi 里面较简单和套路的一题吧。

题意简述

给定一个初始长为 $n$ 的数组 $A$ ，有 $m$ 个操作：

  1. 在末尾加入 $x$。
  2. 求 $\sum\limits_{i=l}^{r} A_i$。
  3. 将整个数组异或上 $x$。
  4. 将整个数组排序。

$n, m\le 10^5, 0\le x, a_i \le 10^9$，不必强制在线。

[Luogu 5312]

主要思路

没有操作 1 的话大家都会，只要建棵 Trie 就能 $O(\log^2 W)$ 求最小的 $k$ 个数的和。（$O(W)$ 为值域）

大概就是每个点 $O(\log W)$ 空间存一下子树内每一位分别为 $1$ 的数的个数。

那么现在加上在末尾插入的操作，显然整个数列是前面一段有序的和后面一段无序的。无序的显然可以直接前缀和一下，$O(\log W)$ 求出某一段的和。

如果需要排序整个序列，就把前缀和清零一下，然后把每个未排序的数扔到 Trie 里去，单次 $O(\log^2 W)$。每个数只会进入 Trie 一次，故总复杂度 $O((n + m) \log^2 W)$ 。

参考代码

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
#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)
#define FORit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b) + 1; i != ed_##i; ++i)
#define ROFit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b)-1; i != ed_##i; --i)
#define GO(x, p, e, i, v) for (register int i = p[x].head, v; i; i = e[i].link)
#define MEM(x, v) memset(x, v, sizeof(x))
#define fir first
#define sec second
#define pq priority_queue
#define MP make_pair
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
#define Templ(T) template <typename T>
static char InB[1 << 21], *In_s = InB, *In_t = InB;
static char OutB[1 << 21], *Out_s = OutB;
inline void FGO(){
    fwrite(OutB, 1, Out_s - OutB, stdout), Out_s = OutB;
    return;
}
inline char gcr(){
    if(In_s == In_t){
        In_t = (In_s = InB) + fread(InB, 1, 1 << 21, stdin);
        if(In_s == In_t) return EOF;
    }
    return *In_s ++;
}
inline void pcr(const char &c){
    if(Out_s - OutB == 1 << 21) fwrite(OutB, 1, 1 << 21, stdout), Out_s = OutB;
    *Out_s ++ = c;
}
inline int read() {
    reg int ans = 0;
    reg char c = gcr();
    while (!isdigit(c)) c = gcr();
    for (; isdigit(c); c = gcr()) ans = (ans << 1) + (ans << 3) + (c ^ 48);
    return ans;
}
inline void write(LL x){
    static int sta[12];
    if(x < 0) return pcr('-'), write(-x);
    Rint top = 0;
    do{
        sta[top ++] = x % 10, x /= 10;
    }while(x);
    while(top) pcr(sta[-- top] ^ 48);
}
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 using_mod
const int mod = 998244353;
#ifdef using_mod
inline void inc(int &x, const int &y) { x += y; if (x >= mod) x -= mod; }
inline void dec(int &x, const int &y) { x -= y; if (x < 0) x += mod; }
inline int ksm(int x, LL y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1) res = 1ll * res * x % mod;
    return res;
}
#endif
Templ(_Tp) inline _Tp gcd(_Tp x, _Tp y) { return y ? gcd(y, x % y) : x; }
#define FILE(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
} // namespace my_std
using namespace my_std;

const int N = 200020, M = 31, NM = 33;
int n, m, sn;//sn: sorted_length
LL sn_q;
int a[N], pre[N][NM];
//pre[p][k]: 现在未排序段到第 p 个数中有多少个第 k 位为 1 的数
int ch[N << 5][2], cnt[N << 5][NM], siz[N << 5], node_cnt = 1;
//cnt[u][k]: 节点 u 子树内有多少个第 k 位为 1 的数
int rev[NM], xr;//rev[i]: （对 trie）第 i 位是否交换; xr: 整个序列被 xor 的值

//trie 应按位从大到小操作
inline LL soq(int p){//sorted_query
    if(!p) return 0;
    reg LL res = 0;
    Rint v = 0, u = 1;
    ROF(k, M - 1, 0){
        if(p <= siz[ch[u][rev[k]]]){
            u = ch[u][rev[k]], v |= rev[k] << k;
        }//没有该位置为 1 的数
        else{
            Rint id = ch[u][rev[k]], tmp;
            p -= siz[id];
            FOR(t, 0, M - 1){
                tmp = cnt[id][t];
                res += (LL)(((xr >> t) & 1) ? siz[id] - tmp : tmp) << t;
            }
            u = ch[u][rev[k] ^ 1];
            v |= (rev[k] ^ 1) << k;
        }
    }
    //最后剩下的都是 v
    return res + (LL)p * (v ^ xr);
}
inline LL scq(int l, int r){//scattered_query
    Rint len = r - l + 1, tmp;
    reg LL res = 0;
    FOR(k, 0, M - 1){
        tmp = pre[r][k] - pre[l - 1][k];
        res += (LL)(((xr >> k) & 1) ? len - tmp : tmp) << k;
    }
    return res;
}
inline LL query(int l, int r){
    if(r <= sn) return soq(r) - soq(l - 1);
    if(l > sn) return scq(l, r);
    return soq(sn) - soq(l - 1) + scq(sn + 1, r);
}

inline void insert(int x){
    ++ siz[1];
    FOR(t, 0, M - 1) cnt[1][t] += (x >> t) & 1;
    Rint u = 1, d;
    ROF(k, M - 1, 0){
        d = (x >> k) & 1;
        u = ch[u][d] ? ch[u][d] : ch[u][d] = ++ node_cnt;
        ++ siz[u];
        FOR(t, 0, M - 1) cnt[u][t] += (x >> t) & 1;
    }
    return;
}

int main(){
    n = read(), sn = 0;
    FOR(i, 1, n){
        a[i] = read();
        FOR(k, 0, M - 1) pre[i][k] = pre[i - 1][k] + ((a[i] >> k) & 1);
    }
    m = read();
    Rint sta, l, r;
    while(m --){
        sta = read();
        if(sta == 1){
            a[++ n] = read() ^ xr;
            FOR(k, 0, M - 1) pre[n][k] = pre[n - 1][k] + ((a[n] >> k) & 1);
        }else if(sta == 2){
            l = read(), r = read();
            // printf("%lld\n", query(l, r));
            write(query(l, r)), pcr('\n');
        }else if(sta == 3){
            l = read(), xr ^= l;
        }else if(sta == 4){
            while(sn < n) insert(a[++ sn]);
            FOR(k, 0, M - 1) rev[k] = (xr >> k) & 1;
            FOR(k, 0, M - 1) pre[n][k] = 0;
            sn_q = soq(sn);
        }
    }
    return FGO(), 0;
}