题解 P4135 【作诗】
Yaha
2021-02-01 20:44:46
### 分块
**题意**：
给定数列，$m$次询问$[l_i,r_i]$中，出现正偶数次的数的个数。
**思路**：
想到分块暴力。预处理出：
**$cnt[i][j]$ 为前$i$块中 $j$出现的次数**，**$ans[i][j]$为第$i$块到第$j$块中 出现偶数次的数的个数**
我的变量：
- $l[i] $为第$i$块的左端点，$r[i]$为第$i$块的右端点，$pos[i]$为$i$点所在的块，$len$为块的长度，$num$为块的个数
- $cnt[i][j]$ 为前$i$块中 $j$出现的次数，$ans[i][j]$为第$i$块到第$j$块中 出现偶数次的数的个数
- $t[i]$为桶，每次用完清零
代码里有详细注释，（个人觉得分块题用这种写法较其他题解更好写且不易错
```cpp
#include<bits/stdc++.h>
using namespace std;
const int amou=1e5+90,sqt=1e3+90;
int l[amou],r[amou],pos[amou],len,num;
int a[amou],n,m,c,las;
int cnt[sqt][amou],ans[sqt][sqt];
int t[amou];
int query(int ll,int rr){
int posl=pos[ll],posr=pos[rr];
if(posl+1>=posr)//只有1个块或者2个块都可以直接暴力
{
int s=0;//答案，即出现偶数次的数的个数
for(int i=ll;i<=rr;i++)
{
t[a[i]]++;//桶
if(!(t[a[i]]&1)) s++;//说明在t[]在+1之前是奇数，所以这是一种新方案
else if(t[a[i]]>=3) s--;//说明t[]在+1之前是偶数，并且之前的t[]>=2，故s需-1
}
for(int i=ll;i<=rr;i++) t[a[i]]--;//由于memset超时，所以直接撤销
return s;
}
else
{
int s=ans[posl+1][posr-1];
for(int i=ll;i<=r[posl];i++)
{
t[a[i]]++;
int temp=cnt[posr-1][a[i]]-cnt[posl][a[i]];//a[i]在posl+1~posr-1这几个块中出现的次数
if(!((t[a[i]]+temp)&1)) s++;
else if(t[a[i]]+temp>=3) s--;
}
for(int i=l[posr];i<=rr;i++)
{
t[a[i]]++;
int temp=cnt[posr-1][a[i]]-cnt[posl][a[i]];
if(!((t[a[i]]+temp)&1)) s++;
else if(t[a[i]]+temp>=3) s--;
}
for(int i=ll;i<=r[posl];i++) t[a[i]]--;
for(int i=l[posr];i<=rr;i++) t[a[i]]--;
return s;
}
}
int main(){
scanf("%d%d%d",&n,&c,&m);
len=sqrt(n);
num=ceil(n*1.0/len);
for(int i=1;i<=num;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
r[num]=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=(i-1)/len+1;
cnt[pos[i]][a[i]]++;
}
for(int i=1;i<=num;i++)
for(int j=0;j<=c;j++)
cnt[i][j]+=cnt[i-1][j];//累加前缀和
for(int i=1;i<=num;i++)//固定块i
{
for(int j=i;j<=num;j++)枚举右端块j
{
ans[i][j]=ans[i][j-1];//作为初始值
for(int k=l[j];k<=r[j];k++)//枚举块j的左右端点
{
t[a[k]]++;
if(!(t[a[k]]&1)) ans[i][j]++;
else if(t[a[k]]>=3) ans[i][j]--;
}
}
memset(t,0,sizeof t);//桶用完清零
}
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int L=(l+las)%n+1,R=(r+las)%n+1;
if(L>R) swap(L,R);
int as=query(L,R);
printf("%d\n",as);
las=as;
}
return 0;
}
```