洛谷P4135 【作诗】 题解

 

题目分析：

首先给出一段序列，共 m 次询问，每一次询问求出给定区间内出现正偶数次数的个数。

算法讲解：

首先，如果忽略本题强制在线的话，可以用莫队来做。

但是，题目中已经规定了需要强制在线来做，于是只能另求他法。

看到数据范围，再结合一下题意，这道题可以用分块来做。

首先，定义两个数组cnt[i][j]表示前i块中j出现的次数ans[i][j]表示第i到第j个块中，出现偶数次数的个数。

这两个数组需要先预处理出来，先来看cnt数组。

相当于一个前缀和的思想，先输入把每一个数+1，然后依次枚举块，把前一块中这个数的出现次数加起来。

for(re int i(1) ; i<=n ; ++i){
    a[i] = read();
    pos[i] = (i-1)/blocksize+1;
    cnt[pos[i]][a[i]]++;
}
for(re int i(1) ; i<=tot ; ++i){
    for(re int j(0) ; j<=c ; ++j){
        cnt[i][j] += cnt[i-1][j];
    }
}

然后来看ans数组。

先枚举每一个块，枚举右端点，让ans[i][j]=ans[i][j−1]作为初始值，往后枚举块j的右端点，可以用一个桶来记录出现次数，具体看代码。

for(re int i(1) ; i<=tot ; ++i){
    for(re int j(i) ; j<=tot ; ++j){
        ans[i][j] = ans[i][j-1]; //赋值
        for(re int k(l[j]) ; k<=r[j] ; ++k){
            t[a[k]]++; //用桶来记录
            if(!(t[a[k]]&1)) ans[i][j]++; //如果现在变为偶数个
            else if(t[a[k]]!=1) ans[i][j]--; //从偶数变为奇数
        }
    }
    memset(t,0,sizeof(t)); //别忘了每一次都要清空
}

这时预处理两个重要的数据已经好了，来看如何分块。

分成 ​ 块，把每一个块的左端点和右端点先记录下来。

inline void init(){
    blocksize = sqrt(n); //块大小
    tot = (n-1)/blocksize+1; //块个数
    for(re int i(1) ; i<=tot ; ++i){
        l[i] = (i-1)*blocksize+1; //左端点
        r[i] = i*blocksize; //右端点
    }
    r[tot] = n; //最后一个块的右端点设为n
}

最后就是处理询问 *** 作了。

每次给定一个l和r，求该区间内偶数次数的个数。

分两种情况。

如果两个端点在一个块中，直接暴力修改就行。

int idx=pos[ll],idy=pos[rr];
if(idy-idx<=1){
    int res=0;
    for(re int i(ll) ; i<=rr ; ++i){
        t[a[i]]++;
        if(!(t[a[i]]&1)) res++;
        else if(t[a[i]]!=1) res--;
    }
    for(re int i(ll) ; i<=rr ; ++i) t[a[i]]--;
    return res;
}

第二种情况，如果两个块中间隔了很远，那么中间的块可以直接用预处理的ans数组，旁边的两个小块暴力询问。

int res = ans[idx+1][idy-1];
for(re int i(ll) ; i<=r[idx] ; ++i){
    t[a[i]]++;
    int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]]; //大块中a[i]出现的次数
    if(!((t[a[i]]+pre)&1)) res++; //从奇数变为偶数
    else if(t[a[i]]+pre!=1) res--; //从偶数变为奇数
}
for(re int i(l[idy]) ; i<=rr ; ++i){
    t[a[i]]++;
    int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]]; //跟上面一样
    if(!((t[a[i]]+pre)&1)) res++;
    else if(t[a[i]]+pre!=1) res--;
}
for(re int i(ll) ; i<=r[idx] ; ++i) t[a[i]]--; //最后别忘了清空
for(re int i(l[idy]) ; i<=rr ; ++i) t[a[i]]--; //而且只要清空这一段就行
return res;

至此，这道题就做完啦。

总代码：

#include
#define re register
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x/10) print(x/10);
    putchar(x%10+'0');
}
const int M = 1e5+10;
int n,c,m; 
int blocksize,tot,last=0;
int a[M],ans[350][350],cnt[350][M],l[M],r[M],pos[M],t[M];
inline void init(){
    blocksize = sqrt(n);
    tot = (n-1)/blocksize+1;
    for(re int i(1) ; i<=tot ; ++i){
        l[i] = (i-1)*blocksize+1;
        r[i] = i*blocksize;
    }
    r[tot] = n;
}
inline int query(int ll,int rr){
    int idx=pos[ll],idy=pos[rr];
    if(idy-idx<=1){
        int res=0;
        for(re int i(ll) ; i<=rr ; ++i){
            t[a[i]]++;
            if(!(t[a[i]]&1)) res++;
            else if(t[a[i]]!=1) res--;
        }
        for(re int i(ll) ; i<=rr ; ++i) t[a[i]]--;
        return res;
    }
    else{
        int res = ans[idx+1][idy-1];
        for(re int i(ll) ; i<=r[idx] ; ++i){
            t[a[i]]++;
            int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]];
            if(!((t[a[i]]+pre)&1)) res++;
            else if(t[a[i]]+pre!=1) res--;
        }
        for(re int i(l[idy]) ; i<=rr ; ++i){
            t[a[i]]++;
            int pre=cnt[idy-1][a[i]]-cnt[idx][a[i]];
            if(!((t[a[i]]+pre)&1)) res++;
            else if(t[a[i]]+pre!=1) res--;
        }
        for(re int i(ll) ; i<=r[idx] ; ++i) t[a[i]]--;
        for(re int i(l[idy]) ; i<=rr ; ++i) t[a[i]]--;
        return res;
    }
}
signed main(){
    n=read(),c=read(),m=read();
    init();
    for(re int i(1) ; i<=n ; ++i){
        a[i] = read();
        pos[i] = (i-1)/blocksize+1;
        cnt[pos[i]][a[i]]++;
    }
    for(re int i(1) ; i<=tot ; ++i){
        for(re int j(0) ; j<=c ; ++j){
            cnt[i][j] += cnt[i-1][j];
        }
    }
    for(re int i(1) ; i<=tot ; ++i){
        for(re int j(i) ; j<=tot ; ++j){
            ans[i][j] = ans[i][j-1];
            for(re int k(l[j]) ; k<=r[j] ; ++k){
                t[a[k]]++;
                if(!(t[a[k]]&1)) ans[i][j]++;
                else if(t[a[k]]!=1) ans[i][j]--;
            }
        }
        memset(t,0,sizeof(t));
    }
    while(m--){
        int ll,rr;
        ll=read(),rr=read();
        int L=(ll+last)%n+1,R=(rr+last)%n+1;
        if(L > R) swap(L,R);
        last = query(L,R);
        printf("%d\n",last);
    }
    return 0;
}