BZOJ2821/CH4907 作诗分块

╰+哭是因爲堅強的太久メ 2021-12-16 06:13 174阅读 0赞

## 题意：N个数，M组询问，每次问\[l,r\]中有多少个数出现正偶数次。 ##

## 分析：分块大法好，类似区间众数的做法，预处理F\[i\]\[j\]表示第i块到第j块的答案一个询问l-r，那么中间大块x-y的答案已经得到了，只要考虑l-x和y-r对答案的影响，对于这至多2√n个数，对于每个数统计它在x-y出现次数t1，以及l-r出现次数t2，根据t1，t2的奇偶性考虑其对答案的影响，每块大小√（n/logn），复杂度n√n logn，关于块大小分析，设分块大小为x，分块数n/x，预处理n/x\*n。m与n同级，视为n个询问，每次询问二分x次n\*x\*logn（除非相同的数字很多，否则logn会很小），复杂度n\*（x\*logn+n/x）的分块大小应该是sqrt(n/logn)。后面一想发现用莫队也可以，类似于小z的袜子（统计区间不同数的个数）。 ##

## 注意：STL真心慢，把`fill`改成`memset`才能AC。（fill函数参数：fill(first,last,val); ##

## fill的原理是把那一块单元赋成指定的值，也就是说任何值都可以。memset则是将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值）所以fill比memset要慢。 ##

## 参考：[https://www.cnblogs.com/autoint/p/10661022.html、][https_www.cnblogs.com_autoint_p_10661022.html][http://hzwer.com/3663.html。][http_hzwer.com_3663.html] ##

## 代码： ##

#include<bits/stdc++.h>
    #pragma GCC optimize("O3")
    #define rg register
    #define il inline
    #define co const
    template<class T>il T read(){
        rg T data=0,w=1;rg char ch=getchar();
        while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
        while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
        return data*w;
    }
    template<class T>il T read(rg T&x) {return x=read<T>();}
    typedef long long ll;
    using namespace std;
    
    co int N=1e5+1,T=1300;
    int n,m,a[N],tot,b[N];
    int c[N],L[N],R[N],pos[N],f[T][T];
    vector<int> e[N];
    bool v[N];
    il bool pd(int x) {return x&&~x&1;}// 判断是否为偶数
    il int find(int x,int l,int r){// 求在[l,r]内x出现次数
        return upper_bound(e[x].begin(),e[x].end(),r)-lower_bound(e[x].begin(),e[x].end(),l);
    }
    int ask(int l,int r){
        int p=pos[l],q=pos[r],cnt=0;
        fill(v+1,v+tot+1,0);
        // 同块
        if(p==q){
            for(int i=l;i<=r;++i){
                if(v[a[i]]) continue;
                v[a[i]]=1;
                if(pd(find(a[i],l,r))) ++cnt;
            }
            return cnt;
        }
        // 分三段处理
        int x=0,y=0;
        if(p+1<=q+1) x=p+1,y=q-1;
        cnt=f[x][y];
        for(int i=l;i<=R[p];++i){
            if(v[a[i]]) continue;
            v[a[i]]=1;
            int c1=find(a[i],l,r),c2=find(a[i],L[x],R[y]);
            if(!pd(c1)&&pd(c2)) --cnt;
            else if(pd(c1)&&!pd(c2)) ++cnt;
        }
        for(int i=L[q];i<=r;++i){
            if(v[a[i]]) continue;
            v[a[i]]=1;
            int c1=find(a[i],l,r),c2=find(a[i],L[x],R[y]);
            if(!pd(c1)&&pd(c2)) --cnt;
            else if(pd(c1)&&!pd(c2)) ++cnt;
        }
        return cnt;
    }
    int main(){
        read(n),read<int>(),read(m);
        for(int i=1;i<=n;++i) read(a[i]);
        copy(a+1,a+n+1,b);
        sort(b+1,b+n+1);
        tot=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;++i) e[a[i]=lower_bound(b+1,b+tot+1,a[i])-b].push_back(i);
        int t=sqrt(n*log(n)/log(2));
        int len=t?n/t:n;
        for(int i=1;i<=t;++i) L[i]=R[i-1]+1,R[i]=i*len;
        if(R[t]<n) L[t+1]=R[t]+1,R[++t]=n;
        for(int i=1;i<=t;++i)
            for(int j=L[i];j<=R[i];++j) pos[j]=i;
        for(int i=1;i<=t;++i){
            fill(c+1,c+tot+1,0);
            int cnt=0;
            for(int j=L[i];j<=n;++j){
                if(++c[a[j]]>1) c[a[j]]&1?--cnt:++cnt;
                f[i][pos[j]]=cnt;
            }
        }
        for(int l,r,x=0;m--;){
            l=(read<int>()+x)%n+1,r=(read<int>()+x)%n+1;
            if(l>r) swap(l,r);
            printf("%d\n",x=ask(l,r));
        }
        return 0;
    }

[https_www.cnblogs.com_autoint_p_10661022.html]: https://www.cnblogs.com/autoint/p/10661022.html
[http_hzwer.com_3663.html]: http://hzwer.com/3663.html