BZOJ 2821: 作诗(Poetize)

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

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次能选出的汉字的最多种类数。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
1

HINT

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

题解

强制在线的题目，50S一看就是分块解决。
我们可以分成根号n个快，然后预处理O(n根号n)维护出两两块之间的答案。
每次询问的时候我们根据预处理答案，然后再暴力维护一下两边多出来的部分，分情况讨论就行了。

代码

#include<cstdio>
using namespace std;
const int Maxn=100005;
const int Sqrtn=325;
struct Cnt{
    //int tim[Maxn];
    int siz;
};
Cnt cnt[Sqrtn];
int sn,slen;
int num[Maxn];
int sum[Maxn][Sqrtn];
int tmp[Maxn];
int belong[Maxn];
int stack[Maxn];
int inStack[Maxn];
int tim[Maxn];
int top=0;
int ans[Sqrtn][Sqrtn];
int n,m,c;
inline int sqr(int x){
    return x*x;
}
inline void swap(int &x,int &y){
    int tmp=x;x=y;y=tmp;
}
inline int remax(int a,int b){
    if (a>b) return a;
    return b;
}
int main(){
    scanf("%d%d%d",&n,&c,&m);
    for (int i=1;i<=n;i++) scanf("%d",&num[i]);
    slen=0;while(sqr(slen+1)<=n)slen++;
    sn=n/slen+(n%slen==0?0:1);
    for (int i=1;i<sn;i++) cnt[i].siz=slen;cnt[sn].siz=n-(sn-1)*slen;
    for (int i=1;i<=sn;i++){
        for (int j=1;j<=c;j++) sum[j][i]=sum[j][i-1];
        for (int j=(i-1)*slen+1;j<=(i-1)*slen+cnt[i].siz;j++){
            sum[num[j]][i]++;
            belong[j]=i;
        }
    }
    int tot;
    for(int i=1;i<=sn;i++){
        for (int j=(i-1)*slen+1;j<=n;j++)tmp[num[j]]=0;
        tot=0;
        for (int j=(i-1)*slen+1;j<=n;j++){
            if(!(tmp[num[j]]&1)&&tmp[num[j]])tot--;
            tmp[num[j]]++;
            if(!(tmp[num[j]]&1))tot++;
            ans[i][belong[j]]=tot;
        }
    }
    int lastAns=0;
    for (int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l=((l+lastAns)%n)+1;r=((r+lastAns)%n)+1;
        if (l>r) swap(l,r);
        int lc=belong[l]+1,rc=belong[r]-1;
        int Ans=ans[lc][rc];
        if (lc>rc) Ans=0;
        top=0;
        int j;
        for (j=l;j<=(belong[l]-1)*slen+cnt[belong[l]].siz && j<=r;j++){
            if (inStack[num[j]]!=i){
                inStack[num[j]]=i;
                tim[num[j]]=1;
                stack[++top]=num[j];
            }else{
                tim[num[j]]++;
            }
        }
        for (j=remax((belong[r]-1)*slen+1,j);j<=r;j++){
            if (inStack[num[j]]!=i){
                inStack[num[j]]=i;
                tim[num[j]]=1;
                stack[++top]=num[j];
            }else{
                tim[num[j]]++;
            }
        }
        for (int j=1;j<=top;j++){
            int ctim=sum[stack[j]][rc]-sum[stack[j]][lc-1];
            if (lc>rc) ctim=0;
            if (ctim!=0 && (ctim+tim[stack[j]])%2==0 && ctim%2==1) Ans++;
            if (ctim!=0 && (ctim+tim[stack[j]])%2==1 && ctim%2==0) Ans--;
            if (ctim==0 && tim[stack[j]]%2==0 && tim[stack[j]]!=0) Ans++;
        }
        lastAns=Ans;
        printf("%dn",Ans);
    }
    return 0;
}

#include<cstdio>

using namespace std;

const int Maxn=100005;

const int Sqrtn=325;

struct Cnt{

//int tim[Maxn];

int siz;

};

Cnt cnt[Sqrtn];

int sn,slen;

int num[Maxn];

int sum[Maxn][Sqrtn];

int tmp[Maxn];

int belong[Maxn];

int stack[Maxn];

int inStack[Maxn];

int tim[Maxn];

int top=0;

int ans[Sqrtn][Sqrtn];

int n,m,c;

inline int sqr(int x){

return x*x;

}

inline void swap(int &x,int &y){

int tmp=x;x=y;y=tmp;

}

inline int remax(int a,int b){

if (a>b) return a;

return b;

}

int main(){

scanf("%d%d%d",&n,&c,&m);

for (int i=1;i<=n;i++) scanf("%d",&num[i]);

slen=0;while(sqr(slen+1)<=n)slen++;

sn=n/slen+(n%slen==0?0:1);

for (int i=1;i<sn;i++) cnt[i].siz=slen;cnt[sn].siz=n-(sn-1)*slen;

for (int i=1;i<=sn;i++){

for (int j=1;j<=c;j++) sum[j][i]=sum[j][i-1];

for (int j=(i-1)*slen+1;j<=(i-1)*slen+cnt[i].siz;j++){

sum[num[j]][i]++;

belong[j]=i;

}

int tot;

for(int i=1;i<=sn;i++){

for (int j=(i-1)*slen+1;j<=n;j++)tmp[num[j]]=0;

tot=0;

for (int j=(i-1)*slen+1;j<=n;j++){

if(!(tmp[num[j]]&1)&&tmp[num[j]])tot--;

tmp[num[j]]++;

if(!(tmp[num[j]]&1))tot++;

ans[i][belong[j]]=tot;

}

int lastAns=0;

for (int i=1;i<=m;i++){

int l,r;

scanf("%d%d",&l,&r);

l=((l+lastAns)%n)+1;r=((r+lastAns)%n)+1;

if (l>r) swap(l,r);

int lc=belong[l]+1,rc=belong[r]-1;

int Ans=ans[lc][rc];

if (lc>rc) Ans=0;

top=0;

int j;

for (j=l;j<=(belong[l]-1)*slen+cnt[belong[l]].siz && j<=r;j++){

if (inStack[num[j]]!=i){

inStack[num[j]]=i;

tim[num[j]]=1;

stack[++top]=num[j];

}else{

tim[num[j]]++;

}

for (j=remax((belong[r]-1)*slen+1,j);j<=r;j++){

if (inStack[num[j]]!=i){

inStack[num[j]]=i;

tim[num[j]]=1;

stack[++top]=num[j];

}else{

tim[num[j]]++;

}

for (int j=1;j<=top;j++){

int ctim=sum[stack[j]][rc]-sum[stack[j]][lc-1];

if (lc>rc) ctim=0;

if (ctim!=0 && (ctim+tim[stack[j]])%2==0 && ctim%2==1) Ans++;

if (ctim!=0 && (ctim+tim[stack[j]])%2==1 && ctim%2==0) Ans--;

if (ctim==0 && tim[stack[j]]%2==0 && tim[stack[j]]!=0) Ans++;

}

lastAns=Ans;

printf("%dn",Ans);

}

return 0;

}

#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=100005;
int num[Maxn];
int col[Maxn];
int n,c,m;
int main(){
    freopen("in.txt","r",stdin);
    freopen("ans.txt","w",stdout);
    scanf("%d%d%d",&n,&c,&m);
    for (int i=1;i<=n;i++) scanf("%d",&num[i]);
    int lastAns=0;
    for (int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l=((l+lastAns)%n)+1;r=((r+lastAns)%n)+1;
        if (l>r){
            int tmp=l;
            l=r;
            r=tmp;
        }
        memset(col,0,sizeof(col));
        for (int j=l;j<=r;j++) col[num[j]]++;
        //for (int j=l;j<=r;j++) printf("%dn",num[j]);
        lastAns=0;
        //for (int j=1;j<=c;j++) printf("Col[%d]:%dn",j,col[j]);
        for (int j=1;j<=c;j++) if (col[j]!=0 && col[j]%2==0) lastAns++;
        printf("%dn",lastAns);
    }
}

#include<cstdio>

#include<cstring>

using namespace std;

const int Maxn=100005;

int num[Maxn];

int col[Maxn];

int n,c,m;

int main(){

freopen("in.txt","r",stdin);

freopen("ans.txt","w",stdout);

scanf("%d%d%d",&n,&c,&m);

for (int i=1;i<=n;i++) scanf("%d",&num[i]);

int lastAns=0;

for (int i=1;i<=m;i++){

int l,r;

scanf("%d%d",&l,&r);

l=((l+lastAns)%n)+1;r=((r+lastAns)%n)+1;

if (l>r){

int tmp=l;

l=r;

r=tmp;

}

memset(col,0,sizeof(col));

for (int j=l;j<=r;j++) col[num[j]]++;

//for (int j=l;j<=r;j++) printf("%dn",num[j]);

lastAns=0;

//for (int j=1;j<=c;j++) printf("Col[%d]:%dn",j,col[j]);

for (int j=1;j<=c;j++) if (col[j]!=0 && col[j]%2==0) lastAns++;

printf("%dn",lastAns);

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑