[Luogu 4135] 作诗

文章内容大纲 (右击展开→→)

内容预览:
  • Description 神犇SJY虐完HEOI之后给傻×LYD出了一题: SHY是T国的公主,...~
  • 而且SHY认为选出的汉字的种类数(两个一样的汉字称为同一种)越多越好(...~
  • Range 对于100%的数据,1<=n,c,m<=10^5 Solution 分块~

Description

神犇SJY虐完HEOI之后给傻×LYD出了一题:

SHY是T国的公主,平时的一大爱好是作诗。

由于时间紧迫,SHY作完诗之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数(两个一样的汉字称为同一种)越多越好(为了拿到更多的素材!)。于是SHY请LYD安排选法。

LYD这种傻×当然不会了,于是向你请教……

问题简述:N个数,M组询问,每次问[l,r]中有多少个数出现正偶数次。

Input

输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。

第二行有n个整数,每个数Ai在[1, c]间,代表一个编码为Ai的汉字。

接下来m行每行两个整数l和r,设上一个询问的答案为ans(第一个询问时ans=0),令L=(l+ans)mod n+1, R=(r+ans)mod n+1,若L>R,交换L和R,则本次询问为[L,R]。

Output

输出共m行,每行一个整数,第i个数表示SHY第i次能选出的汉字的最多种类数。

Range

对于100%的数据,1<=n,c,m<=10^5

Solution

分块。

我们把数列分成 (sqrt N) 块。

(mathcal) 表示从 (l) 块到 (r) 块的答案,可以在 (mathcal) 得到。

(sum[i][j]) 表示第 (1-i) 块数字 (j) 出现了多少次,这个我们可以先求出第 (i) 块中数字 (j) 出现了多少次,然后求前缀和即可。这个可以在 (mathcal) 内得到。

对于询问区间 ([l,r]),我们可以从 (ans) 数组中快速求出中间连续的完整的块的答案。

对于剩余部分,我们可以一个一个调整答案,反正剩余部分的长度是 (sqrt N) 级别的。

ps:判断一个数是不是偶数时不能简单的

if(i^1) 
...

如果这样判断,只要 (i) 不为 (0),那么这个值一定为真。

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#define N 100005

int tot;
int n,c,m;
int val[N];
int cnt[N];
int sum[405][N];
int l[405],r[405];
int ans[405][405];
int block,belong[N];

void read(int &x){
x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}

int query(int x,int y){
if(belong[x]==belong[y] or belong[x]+1==belong[y]){
int now=0;
for(int i=x;i<=y;i++){
cnt[val[i]]++;
if(cnt[val[i]]%2==0) now++;
else if(cnt[val[i]]>2) now--;
}
memset(cnt,0,sizeof cnt);
return now;
}
int now=ans[belong[x]+1][belong[y]-1];
for(int i=x;i<=r[belong[x]];i++)
cnt[val[i]]++;
for(int i=y;i>=l[belong[y]];i--)
cnt[val[i]]++;
for(int i=x;i<=r[belong[x]];i++){
if(cnt[val[i]]){
int tmp=sum[belong[y]-1][val[i]]-sum[belong[x]][val[i]];
//printf("tmp=%dn",tmp);
if(!tmp and (cnt[val[i]]%2==0)) now++;
else if(tmp and (tmp&1) and (cnt[val[i]]&1)) now++;
else if(tmp and (tmp%2==0) and (cnt[val[i]]&1)) now--;
cnt[val[i]]=0;
}
}
for(int i=y;i>=l[belong[y]];i--){
if(cnt[val[i]]){
int tmp=sum[belong[y]-1][val[i]]-sum[belong[x]][val[i]];
//printf("tmp=%dn",tmp);
if(!tmp and (cnt[val[i]]%2==0)) now++;
else if(tmp and (tmp&1) and (cnt[val[i]]&1)) now++;
else if(tmp and (tmp%2==0) and (cnt[val[i]]&1)) now--;
cnt[val[i]]=0;
}
}
return now;
}

void file(){
freopen("in.txt","r",stdin);
freopen("out1.txt","w",stdout);
}

signed main(){
//file();
read(n),read(c),read(m);
block=sqrt((double)n);
tot=n/block;
if(n%block) tot++;
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
belong[i]=(i-1)/block+1;
sum[belong[i]][val[i]]++;
}
for(int i=1;i<=tot;i++){
l[i]=(i-1)*block+1;
r[i]=i*block;
for(int j=1;j<=c;j++) sum[i][j]+=sum[i-1][j];
}
/*for(int i=1;i<=tot;i++){
for(int j=1;j<=c;j++)
printf("i=%d,j=%d,sum=%dn",i,j,sum[i][j]);
}*/
for(int i=1;i<=tot;i++){
int now=0;
for(int j=l[i];j<=n;j++){
cnt[val[j]]++;
if(cnt[val[j]]%2==0) now++;
else if(cnt[val[j]]>2) now--;
ans[i][belong[j]]=now;
}
/*for(int j=l[i];j<=n;j++)
cnt[val[j]]--;*/
memset(cnt,0,sizeof cnt);
}
int last=0;
while(m--){
int a,b,x,y;
read(a),read(b);
x=(a+last)%n+1;
y=(b+last)%n+1;
if(x>y) x^=y^=x^=y;
printf("%dn",last=query(x,y));
}
return 0;
}

以上就是:[Luogu 4135] 作诗 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论