题面。
之前做过一道很类似的题目 洛谷P4168蒲公英 ，然后看到这题很快就想到了解法，做完这题可以对比一下，真的很像。
题目要求区间内出现次数为正偶数的数字的数量。
数据范围1e5，可以分块。
我们预处理出这么两个数组。
一个是某个数字出现次数的分块前缀和，这个很简单。
一个是sum[ i ][ j ]代表从第i个分块到第j个分块出现次数为正偶数的数字的个数。
这个数组很好维护，只需要枚举左端点分块和右端点分块然后统计数字出现次数即可。
这些代码里有一些细节，可以结合注释理解。
for(int i=1;i<=get_pos(n);i++){
int kin=0;
for(int j=i;j<=get_pos(n);j++){
for(int k=(j-1)*len+1;k<=min(n,j*len);k++){//这里有一些细节
tmp[a[k]]++;
if((tmp[a[k]]&1))//如果这个数加完之后变成了奇数
if(tmp[a[k]]>1)//如果加完之后出现次数大于一，那么这个数就作为正偶数被统计进答案了，要减掉
kin--;
else//否则这个数在加一之前没有被统计过，没有必要更改，这里写个else是因为防止与下面那个else产生冲突
kin+=0;
else//加完之后如果变成了偶数那肯定从奇数变成了正偶数，对答案有贡献
kin++;
}
sum[i][j]=kin;
}
for(int j=1;j<=c;j++)//清空辅助数组
tmp[j]=0;
}接下来处理询问。
对于询问的l,r，算出其所在的分块lb,rb。
若l，r所在分块相同或相邻则暴力计算，时间复杂度n1/2。
若l，r所在分块之间相隔至少一个分块，那么先将答案设成这两个分块之间的出现次数为正偶数的数字数量。
然后，计算两边散块内数字对答案的贡献。
情况较多，可结合注释理解。
void get_q(){
ans=0;
for(int i=l;i<=lb*len;i++){
tmp[a[i]]++;
if(tmp[a[i]]&1)//如果这个数在散块中出现次数为奇数
if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)//如果它在中间块中出现次数为奇数，那么它没有被预先统计进答案里，且目前它对答案有贡献
ans++;
else//如果这个数在中间块中出现次数为偶数
if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)//如果这个数在中间块中出现次数为正偶数，那么它已经作为答案被统计过了，现在不符合条件要减掉
ans--;
else//这个数并没有作为答案被统计过
if(tmp[a[i]]>1)//如果这个数在散块中之前已经作为正偶数被统计了，要减掉
ans--;
else//否则并没有影响
ans-=0;
else//这个数在散块中出现次数为偶数
if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)//如果这个数在中间块中出现次数为奇数，那么这个数的出现次数被作为正偶数统计过，要减掉
ans--;
else//否则这个数之前没有算进答案里，要加进去
ans++;
}
for(int i=(rb-1)*len+1;i<=r;i++){//以下分类同上
tmp[a[i]]++;
if(tmp[a[i]]&1)
if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)
ans++;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)
ans--;
else
if(tmp[a[i]]>1)
ans--;
else
ans-=0;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)
ans--;
else
ans++;
}
for(int i=l;i<=lb*len;i++)//清空辅助数组
tmp[a[i]]--;
for(int i=(rb-1)*len+1;i<=r;i++)
tmp[a[i]]--;
ans+=sum[lb+1][rb-1];
}处理单次询问时间复杂度为n1/2，可以通过本题。
#include<bits/stdc++.h>
using namespace std;
const int h=100010;
const int b_h=1010;
int n,m,c;
int len;
int a[h];
int sum[b_h][b_h];
int tim[b_h][h];
int tmp[h];
int get_pos(int x){
return (x-1)/len+1;
}
void get_pre(){
for(int i=1;i<=get_pos(n);i++)
for(int j=1;j<=c;j++)
tim[i][j]+=tim[i-1][j];
for(int i=1;i<=get_pos(n);i++){
int kin=0;
for(int j=i;j<=get_pos(n);j++){
for(int k=(j-1)*len+1;k<=min(n,j*len);k++){
tmp[a[k]]++;
if((tmp[a[k]]&1))
if(tmp[a[k]]>1)
kin--;
else
kin+=0;
else
kin++;
}
sum[i][j]=kin;
}
for(int j=1;j<=c;j++)
tmp[j]=0;
}
}
int l,r,lb,rb;
int ans;
void get_vio(){
ans=0;
for(int i=l;i<=r;i++){
tmp[a[i]]++;
if((tmp[a[i]]&1))
if(tmp[a[i]]>1)
ans--;
else
ans+=0;
else
ans++;
}
for(int i=l;i<=r;i++)
tmp[a[i]]--;
}
void get_q(){
ans=0;
for(int i=l;i<=lb*len;i++){
tmp[a[i]]++;
if(tmp[a[i]]&1)
if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)
ans++;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)
ans--;
else
if(tmp[a[i]]>1)
ans--;
else
ans-=0;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)
ans--;
else
ans++;
}
for(int i=(rb-1)*len+1;i<=r;i++){
tmp[a[i]]++;
if(tmp[a[i]]&1)
if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)
ans++;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)
ans--;
else
if(tmp[a[i]]>1)
ans--;
else
ans-=0;
else
if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)
ans--;
else
ans++;
}
for(int i=l;i<=lb*len;i++)
tmp[a[i]]--;
for(int i=(rb-1)*len+1;i<=r;i++)
tmp[a[i]]--;
ans+=sum[lb+1][rb-1];
}
int main(){
scanf("%d%d%d",&n,&c,&m);
len=sqrt(n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),tim[get_pos(i)][a[i]]++;
get_pre();
int lst=0;
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
l=(l+lst)%n+1,r=(r+lst)%n+1;
if(l>r)
swap(l,r);
lb=get_pos(l),rb=get_pos(r);
if(lb>=rb-1)
get_vio();
else
get_q();
lst=ans;
printf("%d\n",ans);
}
return 0;
}完整代码
标签：
留言评论