【分块】P4135 作诗

女爷i 2023-06-01 06:08 14阅读 0赞

分块太暴力惹...

没做出来。看了题解qaq

**分析：**

两头$\\sqrt\{n\}$暴力维护

预处理ans\[i\]\[j\],sum\[i\]\[j\]

sum\[i\]\[j\]是一个前缀和，前i块值为j的数量

ans\[i\]\[j\]表示第i块到第j块的答案总和

询问的时候先做两头，最后把ans\[\]\[\]加上去就好了！

主要难点在预处理和卡常

1 #pragma GCC optimize(3)
     2 #pragma GCC optimize(2)
     3 #pragma GCC optimize("Ofast")
     4 #include<bits/stdc++.h>
     5 using namespace std;
     6 inline int read(){
     7     int ans=0,f=1;char chr=getchar();
     8     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    10     return ans*f;
    11 }const int M=1e5+5,N=320;
    12 int sum[N][M],ans[N][N],n,c,m,x,y,bl[M],k,a[M],cnt[M],lst,tmp,i,j,now;
    13 int Query(int l,int r){
    14     tmp=0;
    15     if(bl[l]==bl[r]){
    16         for(i=l;i<=r;++i){
    17             ++cnt[a[i]];
    18             if(!(cnt[a[i]]&1)) ++tmp;
    19             else if(cnt[a[i]]>2) --tmp;
    20         }for(i=l;i<=r;i++) --cnt[a[i]];
    21         return tmp;
    22     }else{
    23         for(i=l;i<=bl[l]*k;++i){
    24             ++cnt[a[i]];
    25             if(!((cnt[a[i]]+sum[bl[r]-1][a[i]]-sum[bl[l]][a[i]])&1)) ++tmp;
    26             else if(cnt[a[i]]+sum[bl[r]-1][a[i]]-sum[bl[l]][a[i]]>2) --tmp;
    27         }
    28         for(i=(bl[r]-1)*k+1;i<=r;i++){
    29             ++cnt[a[i]];
    30             if(!((cnt[a[i]]+sum[bl[r]-1][a[i]]-sum[bl[l]][a[i]])&1)) ++tmp;
    31             else if(cnt[a[i]]+sum[bl[r]-1][a[i]]-sum[bl[l]][a[i]]>2) --tmp;
    32         }
    33         for(i=l;i<=bl[l]*k;i++) --cnt[a[i]];
    34         for(i=(bl[r]-1)*k+1;i<=r;i++) --cnt[a[i]];
    35         tmp+=ans[bl[l]+1][bl[r]-1];    
    36         return tmp;
    37     }
    38 }
    39 signed main(){
    40     n=read(),c=read(),m=read();k=sqrt(n)+1;
    41     for(i=1;i<=n;++i) a[i]=read();
    42     for(i=1;i<=n;++i) bl[i]=(i-1)/k+1,++sum[bl[i]][a[i]];
    43     for(i=1;i<=bl[n];++i)for(j=1;j<=c;++j)sum[i][j]+=sum[i-1][j];
    44     for(i=1;i<=bl[n];++i){
    45         for(j=(i-1)*k+1,now=0;j<=n;++j){
    46             cnt[a[j]]++;
    47             if(!(cnt[a[j]]&1)) ++now;
    48             else if(cnt[a[j]]>2) --now;
    49             ans[i][bl[j]]=now;
    50         }for(j=i*k-k+1;j<=n;++j)--cnt[a[j]];
    51     }while(m--){
    52         x=read(),y=read(),x=(x+lst)%n+1,y=(y+lst)%n+1;
    53         if(x>y) swap(x,y);
    54         printf("%d\n",lst=Query(x,y));
    55     }return 0;
    56 }

转载于:https://www.cnblogs.com/zhenglw/p/11255732.html