洛谷P3604 美好的每一天（莫队）

传送门

由乃的题还是一如既往的可怕……

先放上原题解

标解：

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

发现这个和 $xor$ 类似

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

把每个位置的值变为前缀 $xor$ 和，那么区间 $[l,r]$ 可以回归天空当且仅当 $a[l - 1] \oplus a[r]$ 为 $0$ 或者 $2^x$

$a[i]$ 即 $1->i$ 的异或和

这样用莫队算法，可以做到 $O( 26n\sqrt{n} )$ 的复杂度

然后怎么用莫队？可以参考一下这道题目->异或序列

考虑区间$[l,r]->[l,r+1]$就是要看这个区间里有多少前缀异或$a[r+1]$等于$0$或$1<<x$

那么只要用桶存起来就好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getchar()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getchar());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=,M=(<<)+;

 int a[N],rt[N],l,r,n,m,bl;char s[N];

 struct node{

     int l,r,id;

     inline bool operator <(const node b)const

     {

         if(rt[l]!=rt[b.l]) return l<b.l;

         return rt[l]&?r<b.r:r>b.r;

     }

 }q[N];

 unsigned short c[M];

 int ans[N],ansn;

 inline void add(int x){

     ansn+=c[a[x]];

     for(int i=;i<;++i) ansn+=c[a[x]^(<<i)];

     ++c[a[x]];

 }

 inline void del(int x){

     --c[a[x]];

     ansn-=c[a[x]];

     for(int i=;i<;++i) ansn-=c[a[x]^(<<i)];

 }

 int main(){

     n=read(),m=read(),bl=sqrt(n);

     scanf("%s",s+);

     for(int i=;i<=n;++i) a[i]=(<<(s[i]-'a'))^a[i-],rt[i]=(i-)/bl+;

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

     q[i].l=read()-,q[i].r=read(),q[i].id=i;

     sort(q+,q++m);

     l=,r=,c[]=;

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

         while(l>q[i].l) add(--l);

         while(r<q[i].r) add(++r);

         while(l<q[i].l) del(l++);

         while(r>q[i].r) del(r--);

         ans[q[i].id]=ansn;

     }

     for(int i=;i<=m;++i) print(ans[i]);

     Ot();

     return ;

 }

然而实际上每一次都要做位运算太慢了，可以直接一波离散把所有能转移到的状态找出来，然后就会快很多（上面那个 7040ms，下面这个938ms）

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getchar()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getchar());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=,M=(<<)+;

 int a[N],b[N],rt[N],l,r,n,m,bl,ver[N*],Next[N*],head[N],tot;char s[N];

 struct node{

     int l,r,id;

     inline bool operator <(const node b)const

     {

         if(rt[l]!=rt[b.l]) return l<b.l;

         return rt[l]&?r<b.r:r>b.r;

     }

 }q[N];

 unsigned short c[M];

 int ans[N],ansn;

 inline void addedge(int u,int v){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

 }

 inline void add(int x){

     for(int i=head[a[x]];i;i=Next[i]) ansn+=c[ver[i]];

     ++c[a[x]];

 }

 inline void del(int x){

     --c[a[x]];

     for(int i=head[a[x]];i;i=Next[i]) ansn-=c[ver[i]];

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read(),m=read(),bl=sqrt(n);

     scanf("%s",s+);

     for(int i=;i<=n;++i) b[i]=a[i]=(<<(s[i]-'a'))^a[i-],rt[i]=i/bl;

     sort(b,b++n);

     int k=unique(b,b++n)-b;

     for(int i=;i<k;++i){

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

             int t=b[i]^(<<j);

             int y=lower_bound(b,b+k,t)-b;

             if(b[y]==t) addedge(i,y);

         }

         addedge(i,i);

     }

     for(int i=;i<=n;++i) a[i]=lower_bound(b,b+k,a[i])-b;

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

     q[i].l=read()-,q[i].r=read(),q[i].id=i;

     sort(q+,q++m);

     l=,r=,c[]=;

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

         while(l>q[i].l) add(--l);

         while(r<q[i].r) add(++r);

         while(l<q[i].l) del(l++);

         while(r>q[i].r) del(r--);

         ans[q[i].id]=ansn;

     }

     for(int i=;i<=m;++i) print(ans[i]);

     Ot();

     return ;

 }

巴特西

洛谷P3604 美好的每一天（莫队）

最新文章

热门文章