「CF2153F」Odd Queries on Odd Array

    「CF2153F」Odd Queries on Odd Array

    CF2153F

    给出一个长度为 nn 的序列 a1,a2,…,ana_1, a_2, \dots, 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,rl, r (1≤l≤r≤n1 \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。

    Solution

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

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

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

    • 初始栈中只有一个节点 00。
    • 依次遍历 a1,…,ana_1, \dots, 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, \dots, 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, \dots, 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)。

    #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
    */