记录编号	600821	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2821]作诗	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	7.497 s
提交时间	2025-05-19 15:37:23	内存使用	124.10 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5, B=405;
int n, c, m, len, bl[N], l[B], a[N], ans;
int cnt[B][N], f[B][B], t_val[N], t_time[N], current_time;
vector<int> modified;
void update(int x) {
    if (t_time[x] != current_time) {
        t_val[x] = 0;
        t_time[x] = current_time;
        modified.push_back(x);
    }
    t_val[x]++;
}
int main() {
	freopen("poetize.in","r",stdin);
	freopen("poetize.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> c >> m; 
    len = sqrt(n) + 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bl[i] = (i-1)/len + 1;
        if (bl[i] != bl[i-1]) l[bl[i]] = i;
    }
    bl[n+1] = bl[n] + 1; l[bl[n+1]] = n+1;
    for (int i = 1; i <= bl[n]; i++) {
        int tmp = 0;
        memset(cnt[i], 0, sizeof(cnt[i]));
        for (int j = l[i]; j <= n; j++) {
            cnt[i][a[j]]++;
            int &v = cnt[i][a[j]];
            if (v % 2 == 0) tmp++;
            else if (v > 1) tmp--;
            if (bl[j] != bl[j+1]) f[i][bl[j]] = tmp;
        }
    }
    while (m--) {
        int x, y; cin >> x >> y;
        int ql = (x + ans) % n + 1, qr = (y + ans) % n + 1;
        if (ql > qr) swap(ql, qr);
        int res = 0;
        if (bl[ql] == bl[qr] || bl[qr] - bl[ql] == 1) {
            current_time++;
            modified.clear();
            for (int i = ql; i <= qr; i++) {
                update(a[i]);
                int cnt = t_val[a[i]];
                if (cnt % 2 == 0) res++;
                else if (cnt > 1) res--;
            }
            ans = res;
        } else {
            current_time++;
            modified.clear();
            int lb = bl[ql] + 1, rb = bl[qr] - 1;
            res = f[lb][rb];
            for (int i = ql; i < l[lb]; i++) update(a[i]);
            for (int i = l[rb+1]; i <= qr; i++) update(a[i]);
            for (int x : modified) {
                int edge_cnt = t_val[x];
                int mid_cnt = cnt[lb][x] - cnt[rb+1][x];
                int old_contrib = (mid_cnt > 0 && mid_cnt % 2 == 0);
                int total = mid_cnt + edge_cnt;
                int new_contrib = (total > 0 && total % 2 == 0);
                res += new_contrib - old_contrib;
            }
            ans = res;
        }
        cout << ans << '\n';
    }
    return 0;
}