「CF2153F」Odd Queries on Odd Array

发表于 分类于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

Description

Link：CF2153F

给出一个长度为 nn 的序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n，满足不存在 1≤i<j<k<l≤n1 \leq i < j < k < l \leq n 使得 ai≠aja_i \neq a_j，ai=aka_i = a_k，aj=ala_j = a_l。

有 QQ 次询问，每次询问给出两个整数 l,r(1≤l≤r≤n)l, r(1 \leq l \leq r \leq n)，你需要求出区间 [l,r][l, r] 中所有出现了奇数次的数之和。

本题强制在线。

数据范围：1≤n,Q≤5×1051 \leq n, Q \leq 5\times 10^5，1≤ai≤n1 \leq a_i \leq n，1≤l≤r≤n1 \leq l \leq r \leq n。

时空限制：1010s / 10241024MiB。

记一种神秘性质，所构建的神奇的树形结构。

此题可以被分块通过（我们只关心出现次数的奇偶性，使用 bool 数组存储出现次数即可）。

Solution

根据数组的神秘性质建树：

  • 初始栈中只有一个节点 00。
  • 依次遍历 a1,⋯ ,ana_1, \cdots, a_n，假设当前遍历到了 aia_i。
    • 将当前栈顶与节点 ii 连边，节点 ii 的点权为 aia_i。
    • 若 ii 是 aia_i 的第一次出现位置，则将节点 ii 入栈。
    • 若 ii 是 aia_i 最后一次出现位置，则将栈顶节点出栈（可以证明出栈的节点点权恰为 aia_i）。

性质 1：每次出栈的节点，恰为 aia_i 第一次出现时入栈的节点。

因为从 aia_i 第一次出现到最后一次出现之间，内部的元素必定仅出现在该范围内（否则不满足给定条件），故内部的所有元素必定已出栈。

性质 2：点权均为 vv 的节点，必定构成一个连通块。且第二次以后出现的节点无儿子，以第一次出现的节点为父亲。

证明：假设权值 xx 第一次出现时，加入了节点 uu。另有一节点 vv 的权值等于 xx，现在要证明 u,vu, v 直接相连。

假设 u,vu, v 之间存在一个节点 zz 的权值 ≠x\neq x，此时 zz 必定还未出栈，于是 aza_z 最后一次出现的位置必定在 xx 之后，就形成了 {x,az,x,az}\{x, a_z, x, a_z\} 的结构。与题目条件矛盾。

由于一种权值入栈的节点只有一个，于是第二次以后出现的节点无儿子，以第一次出现的节点为父亲。

性质 3：该树的 dfs 序为 0,1,⋯ ,n0, 1, \cdots, n。

考虑如何回答询问。设 u=LCA(x,y)u = \mathrm{LCA}(x, y)，由于 dfs 序的性质，区间 [l,r][l, r] 可以拆成 uu 的若干个连续子树，以及 l,rl, r 所在的残缺子树。注意特判一下 u=lu = l 的情况。

运用性质 2。以点 uu 分割 uu 的所有子树，对于 uu 每个儿子 vv：

  • 若 av=aua_v = a_u，子树 vv 仅有 vv 一个孤立点。
  • 若 av≠aua_v \neq a_u，子树 vv 与外界相互独立，（使用树上差分）提前预处理出子树 vv 的答案即可。

对于询问中的连续子树，我们使用前缀和预处理出 av≠aua_v \neq a_u 部分的答案之和，同时也处理出 av=aua_v = a_u 的孤立点个数以便后续统计奇偶性。

对于 ll 所在的残缺子树：

  • 若 al=aua_l = a_u，则 ll 所在的残缺子树仅有一个孤立点 ll，计入孤立点个数即可。
  • 若 al≠aua_l \neq a_u，则 ll 所在的残缺子树答案与外界独立。设 L\mathrm{L} 表示 ll 所在子树的最大节点编号，我们要求的是 al,⋯ ,La_{l, \cdots, L} 的答案，使用 sufl−sufL+1\mathrm{suf}_l - \mathrm{suf}_{L + 1} 得到即可。

（rr 所在的残缺子树同理，需要预处理出每个前缀的答案）

最后统计一下有多少个权值为 aua_u 的孤立点，若为奇数个同样也要计入答案。

时间复杂度 O((n+Q)log⁡n)\mathcal{O}((n + Q) \log n)。

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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 500100;

int n, Q;
int a[N];

std::vector<int> pos[N];

std::vector<int> son[N];

void buildTree() {
    for (int i = 0; i <= n; i ++) {
        son[i].clear();
    }

    std::stack<int> s;
    s.push(0);

    for (int i = 1; i <= n; i ++) {
        int u = s.top();
        son[u].push_back(i);

        if (pos[a[i]].front() == i) {
            s.push(i);
        }
        if (pos[a[i]].back() == i) {
            s.pop();
        }
    }
}

s64 f[N];
s64 sum[N];

int lp[N], rp[N];

int dep[N];
int anc[20][N];

int lca(int x, int y) {
    if (dep[x] > dep[y]) {
        std::swap(x, y);
    }
    for (int i = 19; i >= 0; i --) {
        if (dep[x] <= dep[y] - (1 << i)) {
            y = anc[i][y];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i --) {
        if (anc[i][x] ^ anc[i][y]) {
            x = anc[i][x], y = anc[i][y];
        }
    }
    return anc[0][x];
}

void dfs_init(int u, int fu) {
    if (u) {
        dep[u] = dep[fu] + 1;
        anc[0][u] = fu;
        for (int i = 1; i <= 19; i ++) {
            anc[i][u] = anc[i - 1][anc[i - 1][u]];
        }
    }

    lp[u] = rp[u] = u;
    for (int v : son[u]) {
        dfs_init(v, u);
        sum[u] += sum[v];
        chmin(lp[u], lp[v]), chmax(rp[u], rp[v]);
    }
    f[u] += sum[u];
}

bool tmp[N];
s64 pre[N], suf[N];

std::vector<s64> s[N];
std::vector<int> c[N];

s64 ask(int l, int r) {
    if (l == r) {
        return a[l];
    }

    int u = lca(l, r);
    if (u == l) {
        int pr = std::upper_bound(son[u].begin(), son[u].end(), r) - son[u].begin() - 1;

        s64 ans = 0;

        int cnt = 1;
        if (pr) {
            ans += s[u][pr - 1];
            cnt += c[u][pr - 1];
        }

        if (a[r] == a[u]) {
            cnt ++;
        } else {
            ans += pre[r];
            ans -= pre[lp[son[u][pr]] - 1];
        }

        if (cnt & 1) {
            ans += a[u];
        }

        return ans;
    }

    int pl = std::upper_bound(son[u].begin(), son[u].end(), l) - son[u].begin() - 1,
        pr = std::upper_bound(son[u].begin(), son[u].end(), r) - son[u].begin() - 1;

    s64 ans = s[u][pr - 1] - s[u][pl];
    int cnt = c[u][pr - 1] - c[u][pl];

    if (a[l] == a[u]) {
        cnt ++;
    } else {
        ans += suf[l];
        ans -= suf[rp[son[u][pl]] + 1];
    }

    if (a[r] == a[u]) {
        cnt ++;
    } else {
        ans += pre[r];
        ans -= pre[lp[son[u][pr]] - 1];
    }

    if (cnt & 1) {
        ans += a[u];
    }

    return ans;
}

void work() {
    std::cin >> n >> Q;

    a[0] = 0;
    for (int i = 1; i <= n; i ++) {
        std::cin >> a[i];
    }

    for (int i = 0; i <= n; i ++) {
        pos[i].clear();
        f[i] = sum[i] = 0;
    }
    for (int i = 0; i <= n; i ++) {
        pos[a[i]].push_back(i);
    }

    buildTree();

    for (int v = 0; v <= n; v ++) {
        if (pos[v].size() == 0) {
            continue;
        }

        int p = pos[v][0];
        if (pos[v].size() & 1) {
            sum[p] += v;
        }

        for (int i = 1; i < pos[v].size(); i ++) {
            f[pos[v][i]] += v;
        }
    }

    dfs_init(0, 0);

    /* 前缀答案 */
    for (int i = 1; i <= n; i ++) {
        tmp[i] = 0;
    }

    pre[0] = 0;
    for (int i = 1; i <= n; i ++) {
        pre[i] = pre[i - 1];
        tmp[a[i]] ^= 1;
        if (tmp[a[i]]) {
            pre[i] += a[i];
        } else {
            pre[i] -= a[i];
        }
    }

    /* 后缀答案 */
    for (int i = 1; i <= n; i ++) {
        tmp[i] = 0;
    }

    suf[n + 1] = 0;
    for (int i = n; i >= 1; i --) {
        suf[i] = suf[i + 1];
        tmp[a[i]] ^= 1;
        if (tmp[a[i]]) {
            suf[i] += a[i];
        } else {
            suf[i] -= a[i];
        }
    }

    for (int u = 0; u <= n; u ++) {
        s[u].resize(son[u].size());
        c[u].resize(son[u].size());

        for (int i = 0; i < son[u].size(); i ++) {
            int v = son[u][i];

            if (a[v] == a[u]) {
                s[u][i] = 0;
                c[u][i] = 1;
            } else {
                s[u][i] = f[v];
                c[u][i] = 0;
            }

            if (i) {
                s[u][i] += s[u][i - 1];
                c[u][i] += c[u][i - 1];
            }
        }
    }

    s64 lastans = 0;
    while (Q --) {
        s64 l, r;
        std::cin >> l >> r;
 
        l = (l - 1 + lastans) % n + 1;
        r = (r - 1 + lastans) % n + 1;
        if (l > r) {
            std::swap(l, r);
        }
 
        std::cout << (lastans = ask(l, r)) << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    std::cin >> T;
    
    while (T --) {
        work();
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/

/*
1
3 1
2 3 2
2 3
*/