题目背景

时间限制3s,空间限制162MB

素晴らしき日々

我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧...

由于世界会在7月20日完结，作为救世主，间宫卓司要在19日让所有人回归天空

现在已经是19日傍晚，大家集合在C栋的天台上，一共n个人

在他们面前，便是终之空，那终结的天空

题目描述

回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母'a'->'z'作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空

由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了，所以卓司的信徒很多

输入输出格式

输入格式：

 

第一行两个数n,m

之后一行一个长为n的字符串，代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

输出格式：

m行，每行一个数表示答案

输入输出样例

输入样例#1：

6 6zzqzzq1 62 43 42 34 51 1

输出样例#1：

1642231

说明

对于10%的数据，n,m<=100

对于30%的数据，n,m<=2000

对于100%的数据，n,m<=60000

字符集大小有梯度

在大家回归天空之后，彩名露出了阴冷的笑容

---

先奉上O(n2) 30分骗分

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=2005;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,Q,l,r;char c[N];int a[N][N],s[N][N],cnt[300],now;void ini(){    for(int i=1;i<=n;i++){        memset(cnt,0,sizeof(cnt));now=0;        for(int j=i;j<=n;j++){            if(cnt[c[j]]%2==0) now++;            else now--;            cnt[c[j]]++;            if((j-i+1)%2==0&&now==0) a[i][j]=1;            if((j-i+1)%2==1&&now==1) a[i][j]=1;            s[i][j]=s[i][j-1]+a[i][j];            //printf("hi %d %d %d  %d\n",i,j,a[i][j],s[i][j]);        }    }}void solve(int l,int r){    int ans=0;    for(int i=l;i<=r;i++) ans+=s[i][r]-s[i][i-1];    printf("%d\n",ans);}int main(int argc, const char * argv[]) {    n=read();Q=read();    scanf("%s",c+1);    ini();    while(Q--){        l=read();r=read();        solve(l,r);    }    return 0;}
         
        
       
      

 

标解：

一个区间可以重排成为回文串，即区间中最多有一个字母出现奇数次，其他的都出现偶数次

发现这个和  类似

这样如果一个区间的  和为  或者  ，则这个区间可以重排成为回文串，即回归天空

把每个位置的值变为前缀  和，那么区间  可以回归天空当且仅当  为  或者 

 即  的异或和

这样用莫队算法，可以做到  的复杂度

怎么用莫队呢？去请教了__stdcall

考虑[l,r]—>[l,r+1]，就是要找出这个区间里有几个前缀xor满足 a[r+1]^它 =0或(1<<x)

那么用一个桶c存起来 更新答案加上c[a[r+1]^(1<<x)]和c[a[r+1]]就行了

有个细节，[l,r]对应的桶中应该是[l-1,r]的a

然后内存原因c用short

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=6e4+5,M=(1<<26)+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,Q,a[N],bl,pos[N];char s[N];struct ques{    int l,r,id;    bool operator <(const ques &a)const{        return pos[l]==pos[a.l]?r
          
           
            q[i].r) del(r),r--;//printf("hi %d %d %d\n",l,r,ans); while(l
            
             q[i].l) l--,add(l-1);//printf("hi %d %d %d\n",l,r,ans); anss[q[i].id]=ans; } for(int i=1;i<=Q;i++) printf("%d\n",anss[i]);}int main(int argc, const char * argv[]) { n=read();Q=read(); scanf("%s",s+1); bl=sqrt(n); for(int i=1;i<=n;i++) a[i]=(1<<(s[i]-'a'))^a[i-1],pos[i]=(i-1)/bl+1; for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; solve(); return 0;}
            
           
          
         
        
       
      
     

怎么卡常也还是70分

////  main.cpp//  BB////  Created by Candy on 2017/2/2.//  Copyright © 2017年 Candy. All rights reserved.//#pragma GCC optimize("O2")#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=6e4+5,M=(1<<26)+5;inline int read(){    char c=getchar();register int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,Q,a[N],bl,pos[N],bit[27];char s[N];struct ques{    int l,r,id;    bool operator <(const ques &a)const{        return pos[l]==pos[a.l]?r
           
            
             q[i].r) del(r--);//printf("hi %d %d %d\n",l,r,ans); while(l
             
              q[i].l) add(--l-1);//printf("hi %d %d %d\n",l,r,ans); anss[q[i].id]=ans; } for(int i=1;i<=Q;i++) printf("%d\n",anss[i]);}int main(int argc, const char * argv[]) { n=read();Q=read(); scanf("%s",s+1); bl=sqrt(n); for(int i=1;i<=n;i++) a[i]=(1<<(s[i]-'a'))^a[i-1],pos[i]=(i-1)/bl+1; for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; solve(); return 0;}