作诗

说起来我分块和主席树都没写学习笔记，分块应该是咕了，把这篇当学习笔记好了。

传送门

题意

​ N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次，强制在线。

​ 有没有觉得这题很像蒲公英那个题？因为恶意的强制在线，优美的莫队和巧妙的树状数组或主席树被卡掉了（我可能要出个题专门让树状数组过），所以只有丑陋的分块了。

做法

​ 预处理两个数组$num$和$o$，$num[i][j]$表示第$i$块到第$j$块中的答案数，$o[i][j]$表示前$i$个块中第$j$种颜色的个数，显然这需要$n \times \sqrt n$的时间和空间。

​ 查询是，如果$l$和$r$所在一个块或所在块相邻的话，就直接暴力$\sqrt n$查询，否则就处理散块，中间的部分用$num$和$o$做前缀和统计。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int lk[501],rk[501],a[100101],m,bl[100201],blo;
int u[100401],o[501][100101],n,num[501][505],f;
inline int query(int x,int y){
    int ans=0;
    memset(u,0,sizeof(u));
    if (bl[y]-bl[x]<=1){
        for (int i=x; i<=y; i++){
            if (u[a[i]]){
                if (u[a[i]]&1) ans++;
                else ans--;
            }
            u[a[i]]++;
        }
        return ans;
    }
    ans=num[bl[x]+1][bl[y]-1];
    for (int i=x; i<=rk[bl[x]]; i++){
        if (!u[a[i]]){
            u[a[i]]=o[bl[y]-1][a[i]]-o[bl[x]][a[i]];
            // continue;
        }
        if (u[a[i]]){
            if (u[a[i]]&1) ans++;
            else ans--;
        }
        u[a[i]]++;
    }
    for (int i=lk[bl[y]]; i<=y; i++){
        if (!u[a[i]]){
            u[a[i]]=o[bl[y]-1][a[i]]-o[bl[x]][a[i]];
        }
        if (u[a[i]]){
            if (u[a[i]]&1) ans++;
            else ans--;
        }
        u[a[i]]++;
    }
    return ans;
}
int main(){
    int x,y,ans;
    scanf("%d%d%d",&n,&f,&m);
    blo=sqrt(n);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        bl[i]=(i-1)/blo+1;
    }
    for (int i=1; i<=bl[n]; i++)
        lk[i]=(i-1)*blo+1,rk[i]=min(lk[i]+blo-1,n);
    for (int i=1; i<=bl[n]; i++){
        ans=0; memset(u,0,sizeof(u));
        for (int j=1; j<=f; j++) o[i][j]=o[i-1][j];
        for (int k=lk[i]; k<=rk[i]; k++){
            if (u[a[k]]){
                if (u[a[k]]&1) ans++;
                else ans--;
            }
            u[a[k]]++; o[i][a[k]]++;
        }
        num[i][i]=ans;
        for (int j=i+1; j<=bl[n]; j++){
            for (int k=lk[j]; k<=rk[j]; k++){
                if (u[a[k]]){
                    if (u[a[k]]&1) ans++;
                    else ans--;
                }
                u[a[k]]++;
            }
            num[i][j]=ans;
        }
    }
    int last=0;
    while (m--){
        scanf("%d%d",&x,&y);
        x=(x+last)%n+1; y=(y+last)%n+1;
        if (x>y) swap(x,y);
        last=query(x,y); printf("%d %d %d\n",x,y,last);
    }
    return 0;
}

ps:写的时候仗着复杂度正确什么优化都没加还肆无忌惮的memset，所以跑了16000多ms，大家都是分块就我像暴力水过去的。