关于一道区间众数的题目：

关于一道分块好题：

还有一道好题：

1、wyh2000 and sequence

离线做法：莫队 \(O(n\sqrt{n})\)

在线做法：分块 \(O(n\sqrt{n})\)

预处理出一个块中出现次数的前缀和 \(sum[i][j]\)，表示第 \(i\) 个数在前 \(j\) 块出现的次数。再预处理两个块的答案，然后更新一下答案。

看起来可能还有一个快速幂带来的 \(\log\)，但是快速幂的部分可以预处理，然后扔进 \(vector\) 里面，就少了一个 \(\log\)

一遍过这题还是很爽的！！！

\(Code\ Below:\)

#include 
    
     #define ll long longusing namespace std;const int maxn=50000+10;const int mod=1e9+7;int n,m,a[maxn],mp[maxn],pos[maxn],L[maxn],R[maxn],cnt[maxn],b[maxn][230],sum[maxn][230],tot,blo;vector
     
       v[maxn];inline int read(){    register int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return (f==1)?x:-x;}int query(int l,int r){    int p=pos[l],q=pos[r],ans=0,num;    if(p+1>=q){        for(int i=l;i<=r;i++){            if(cnt[a[i]]) ans=(ans-v[a[i]][cnt[a[i]]]+mod)%mod;            cnt[a[i]]++;            ans=(ans+v[a[i]][cnt[a[i]]])%mod;        }        for(int i=l;i<=r;i++) cnt[a[i]]=0;    }    else {        ans=b[p+1][q-1];        for(int i=l;i<=R[p];i++){            num=sum[a[i]][q-1]-sum[a[i]][p]+cnt[a[i]];            if(num) ans=(ans-v[a[i]][num]+mod)%mod;            cnt[a[i]]++;num++;            ans=(ans+v[a[i]][num])%mod;        }        for(int i=L[q];i<=r;i++){            num=sum[a[i]][q-1]-sum[a[i]][p]+cnt[a[i]];            if(num) ans=(ans-v[a[i]][num]+mod)%mod;            cnt[a[i]]++;num++;            ans=(ans+v[a[i]][num])%mod;        }        for(int i=l;i<=R[p];i++) cnt[a[i]]=0;        for(int i=L[q];i<=r;i++) cnt[a[i]]=0;    }    return ans;}int main(){    int T=read();    while(T--){        n=read(),m=read();blo=sqrt(n);        for(int i=1;i<=n;i++){            pos[i]=(i-1)/blo+1;            if(pos[i]!=pos[i-1]){                L[pos[i]]=i;                R[pos[i-1]]=i-1;            }        }        R[pos[n]]=n;        for(int i=1;i<=n;i++) mp[i]=a[i]=read();        sort(mp+1,mp+n+1);        tot=unique(mp+1,mp+n+1)-mp-1;        for(int i=1;i<=n;i++){            a[i]=lower_bound(mp+1,mp+tot+1,a[i])-mp;            cnt[a[i]]++;sum[a[i]][pos[i]]++;        }        for(int i=1;i<=tot;i++)            for(int j=1;j<=pos[n];j++)                sum[i][j]+=sum[i][j-1];        int now,x,y,l,r,lastans=0;        for(int i=1;i<=tot;i++){            now=1;v[i].push_back(now);            for(int j=1;j<=cnt[i];j++){                now=(ll)now*mp[i]%mod;                v[i].push_back(now);            }        }        for(int i=1;i<=n;i++) cnt[a[i]]=0;        for(int i=1;i<=pos[n];i++){            now=0;            for(int j=L[i];j<=n;j++){                if(cnt[a[j]]) now=(now-v[a[j]][cnt[a[j]]]+mod)%mod;                cnt[a[j]]++;                now=(now+v[a[j]][cnt[a[j]]])%mod;                if(j%blo==0||j==n) b[i][pos[j]]=now;            }            for(int j=L[i];j<=n;j++) cnt[a[j]]=0;        }        for(int i=1;i<=m;i++){            x=read(),y=read();            l=min((x^lastans)%n+1,(y^lastans)%n+1);            r=max((x^lastans)%n+1,(y^lastans)%n+1);            printf("%d\n",lastans=query(l,r));        }        for(int i=1;i<=tot;i++) v[i].clear();        for(int i=1;i<=tot;i++)            for(int j=1;j<=n;j++) sum[i][j]=0;    }    return 0;}