记录编号	600958	评测结果	AAAAAAAAAA
题目名称	2661.[BZOJ 2821]作诗	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	20.488 s
提交时间	2025-05-21 21:52:37	内存使用	33.74 MiB

#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("poetize.in","r",stdin);
	    freopen("poetize.out","w",stdout);
    int n, c, m;
    scanf("%d%d%d", &n, &c, &m);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    const int S = (int)sqrt(n) + 1;
    const int B = (n + S - 1) / S;

    vector<vector<int>> pre(c + 1, vector<int>(B + 1, 0));
    for (int i = 0; i < B; ++i) {
        int st = i * S;
        int ed = min((i + 1) * S, n);
        vector<int> cnt(c + 1, 0);
        for (int j = st; j < ed; ++j) {
            cnt[a[j]]++;
        }
        for (int x = 1; x <= c; ++x) {
            pre[x][i + 1] = pre[x][i] + cnt[x];
        }
    }

    vector<vector<int>> f(B, vector<int>(B, 0));
    for (int i = 0; i < B; ++i) {
        vector<int> cnt(c + 1, 0);
        int ans = 0;
        for (int j = i; j < B; ++j) {
            int st = j * S;
            int ed = min((j + 1) * S, n);
            for (int k = st; k < ed; ++k) {
                int x = a[k];
                cnt[x]++;
                if (cnt[x] % 2 == 0) {
                    ans++;
                } else {
                    if (cnt[x] > 1) {
                        ans--;
                    }
                }
            }
            f[i][j] = ans;
        }
    }

    int prv = 0;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int L = (l + prv) % n;
        int R = (r + prv) % n;
        if (L > R) swap(L, R);

        int al = L / S;
        int ar = R / S;
        int aa = al + 1;
        int bb = ar - 1;

        int mid = 0;
        if (aa <= bb && aa < B && bb < B) {
            mid = f[aa][bb];
        }

        vector<int> sc;
        if (aa <= bb) {
            int stm = aa * S;
            for (int i = L; i < stm; ++i) {
                sc.push_back(a[i]);
            }
            int edm = (bb + 1) * S;
            for (int i = edm; i <= R; ++i) {
                sc.push_back(a[i]);
            }
        } else {
            for (int i = L; i <= R; ++i) {
                sc.push_back(a[i]);
            }
        }

        vector<int> cnts(c + 1, 0);
        vector<int> scx;
        for (int x : sc) {
            if (cnts[x]++ == 0) {
                scx.push_back(x);
            }
        }

        for (int x : scx) {
            int k = 0;
            if (aa <= bb) {
                k = pre[x][bb + 1] - pre[x][aa];
            }
            int tot = k + cnts[x];
            bool pin = (k > 0) && (k % 2 == 0);
            bool nin = (tot > 0) && (tot % 2 == 0);
            if (pin != nin) {
                mid += nin ? 1 : -1;
            }
        }

        prv = mid;
        printf("%d\n", prv);
    }

    return 0;
}