BZOJ4866: [Ynoi2017]由乃的商场之旅【莫队+异或】

4866: [Ynoi2017]由乃的商场之旅

【题目描述】

传送门

【题解】

可以将字符串压位,然后就可以异或了,预处理出所有可能的情况(异或和为0或者只有一位存在),总共27种,然后莫队跑就可以了。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=60005;
int n,m,K,D,NowAns,Ans[MAXN],block[MAXN],a[MAXN][30],b[MAXN*30],hsh[MAXN*30];char ch[MAXN];
struct md{
    int L,R,id;
    bool operator <(const md b)const{return (block[L]<block[b.L])||(block[L]==block[b.L]&&(block[L]&1?R<b.R:R>b.R));}
}W[MAXN];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
void Add(int x){
    for(int j=0;j<=26;j++) NowAns+=hsh[a[x][j]];
    hsh[a[x][0]]++;
}
void Del(int x){
    hsh[a[x][0]]--;
    for(int j=0;j<=26;j++) NowAns-=hsh[a[x][j]];
}
int main(){
    n=read(),m=read();K=2*sqrt(n);
    for(int i=0,cnt=0;i<=n;i++) block[i]=cnt,cnt+=(i%K==0);
    scanf("%s",ch+1);
    for(int i=0;i<=n;i++){
        if(i) a[i][0]=a[i-1][0]^(1<<(ch[i]-'a'));
        b[++D]=a[i][0];
        for(int j=1;j<=26;j++) b[++D]=a[i][j]=a[i][0]^(1<<j-1);
    }
    sort(b+1,b+1+D);D=unique(b+1,b+1+D)-b-1;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=26;j++) a[i][j]=lower_bound(b+1,b+1+D,a[i][j])-b;
    for(int i=1;i<=m;i++) W[i]=(md){read()-1,read(),i};
    sort(W+1,W+1+m);
    for(int i=1,L=0,R=-1;i<=m;i++){
        while(L<W[i].L) Del(L++);
        while(L>W[i].L) Add(--L);
        while(R<W[i].R) Add(++R);
        while(R>W[i].R) Del(R--);
        Ans[W[i].id]=NowAns;
    }
    for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部