luogu P3604 美好的每一天（莫队+二进制）-白红宇

luogu P3604 美好的每一天（莫队+二进制）

阅读量：4695 次

发布时间：2019-06-09

本文共 1497 字，大约阅读时间需要 4 分钟。

这个题还是可以的。

但是卡常卡得我心力憔悴。还是太菜了

我们把一个区间当做一个26位二进制数，每一位代表一个英文，二进制数的每一个位0代表这一位对应的字母出现了偶数次，否则出现了奇数次。

那么一个区间可以升天，当且仅当这个区间对应的二进制数为0或\(x^i\)。

我们用莫队。用\(a[i]\)代表异或前缀和。考虑\([l,r]->[l,r+1]\)贡献的变化，贡献会加上，\(\sum{(a[r+1]==a[x])}+\sum{a[r+1]\oplus{(1<<i)}}(l-1\leq x\leq r,0\leq i\leq 25)\)

我们维护一个\(a[i]\)在当前区间出现次数的桶\(c[i]\)就成了\(c[a[r+1]]+\sum{c[a[r+1]\oplus{(1<<i)}]}(0\leq i\leq 25)\)就可以做了。

卡常居然用到了 unsigned short。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;const int N=60100;map
          
            book;int n,m,ans[N],tmp,a[N],block[N],pw[30];unsigned short c[(1<<26)+100];int cnt,head[N];struct edge{ int to,nxt;}e[N*26];void add(int u,int v){ cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;}char s[N];struct ques{ int l,r,id;}qu[N];bool cmp(ques a,ques b){ if(block[a.l]==block[b.l])return a.r
           
            '9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return sum*f;}int main(){ n=read(),m=read(); int Block=sqrt(n); scanf("%s",s+1); book[0]=1; for(int i=1;i<=n;++i){ a[i]=a[i-1]^(1<<(s[i]-'a')); block[i]=(i-1)/Block+1; book[a[i]]=1; } for(int i=0;i<=n;i++) for(int j=0;j<=25;j++) if(book[a[i]^(1<
            
             <
             
              qu[j].l){ l--; tmp+=c[a[l-1]]; for(int i=head[l-1];i;i=e[i].nxt)tmp+=c[e[i].to]; c[a[l-1]]++; } while(r>qu[j].r){ c[a[r]]--; tmp-=c[a[r]]; for(int i=head[r];i;i=e[i].nxt)tmp-=c[e[i].to]; r--; } while(l

转载于:https://www.cnblogs.com/Xu-daxia/p/10124558.html

你可能感兴趣的文章