題意：給出一個字符串，有m次操作，每次給出一個區間，把區間重新調整成一個回文序列，如果有多種操作，選擇字典序最小的。如果不能操作則不操作。最後輸出最終的字符串 剛入手，感覺好神奇的題，其實要自己多思考。想一下，其實還是很簡單的。 首先我們統計一下區間內各個字母的數量，然後比較區間長度的奇偶性，就知道是否 可以操作。 面對於回文串的字典序最小，顯然是確定，只需要從小到大枚舉26個字母就行了。 所以做法是：線段樹統計區間內各個字母的數量 然後根據區間長度的奇偶性，判斷是否可以操作。 如果可以操作，就進行對稱的區間更新。 注意個細節：對於如果是區間長度是奇數的，那麼肯定有且只有一種字母的個數是奇數，那麼肯定這個字母位於中間，然後其它字母還是按照字母順序，兩邊更新。 大概的每次更新的復雜度是大概查詢是26*lgn,然後更新是26*lgn，大概跑了2.5s [cpp] #include<iostream> #include<cstdio> #include<cstring> #define mem(a,b) memset(a,b,sizeof(a)) #define N 100005 #define lson step<<1 #define rson step<<1|1 using namespace std; struct Seg_tree{ int left,right; int cnt[26],lazy; }L[N<<2]; int n,m; char str[N]; int cnt[26]; void push_up(int step){ for(int i=0;i<26;i++) L[step].cnt[i]=L[lson].cnt[i]+L[rson].cnt[i]; } void update(int step,int l,int r,int k); void push_down(int step){ if(L[step].lazy!=-1){ int l=L[step].left,r=L[step].right,m=(l+r)>>1; update(lson,l,m,L[step].lazy); update(rson,m+1,r,L[step].lazy); L[step].lazy=-1; } } void bulid(int step,int l,int r){ L[step].left=l; L[step].right=r; L[step].lazy=-1; mem(L[step].cnt,0); if(l==r){ L[step].cnt[str[l]-'a']++; L[step].lazy=str[l]-'a'; return ; } int m=(l+r)>>1; bulid(lson,l,m); bulid(rson,m+1,r); push_up(step); } void query(int step,int l,int r){ if(L[step].left==l&&L[step].right==r){ for(int i=0;i<26;i++) cnt[i]+=L[step].cnt[i]; return ; } int m=(L[step].left+L[step].right)>>1; push_down(step); if(r<=m) query(lson,l,r); else if(l>m) query(rson,l,r); else { query(lson,l,m); query(rson,m+1,r); } } void update(int step,int l,int r,int k){ if(L[step].left==l&&L[step].right==r){ mem(L[step].cnt,0); L[step].cnt[k]=r-l+1; L[step].lazy=k; return ; } push_down(step); int m=(L[step].left+L[step].right)>>1; if(r<=m) update(lson,l,r,k); else if(l>m) update(rson,l,r,k); else { update(lson,l,m,k); update(rson,m+1,r,k); } push_up(step); } void slove(int step){ if(L[step].left==L[step].right){ putchar(L[step].lazy+'a'); return ; } push_down(step); slove(lson); slove(rson); } int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d%s",&n,&m,str+1); bulid(1,1,n); while(m--){ int l,r; scanf("%d%d",&l,&r); mem(cnt,0); query(1,l,r); if((r-l+1)&1){ int k=0,p; for(int i=0;i<26;i++) if(cnt[i]&1) k++,p=i; if(k==1){ int a=l,b=r; cnt[p]--; for(int i=0;i<26;i++){ if(cnt[i]){ update(1,a,a+cnt[i]/2-1,i); update(1,b-cnt[i]/2+1,b,i); a+=cnt[i]/2; b-=cnt[i]/2; } } update(1,a,b,p); } } else{ int k=0; for(int i=0;i<26;i++) if(cnt[i]&1){ k=1; break; } if(!k){ int a=l,b=r; for(int i=0;i<26;i++){ if(cnt[i]){ update(1,a,a+cnt[i]/2-1,i); update(1,b-cnt[i]/2+1,b,i); a+=cnt[i]/2; b-=cnt[i]/2; } } } } } slove(1);putchar('\n'); return 0; } #include<iostream> #include<cstdio> #include<cstring> #define mem(a,b) memset(a,b,sizeof(a)) #define N 100005 #define lson step<<1 #define rson step<<1|1 using namespace std; struct Seg_tree{ int left,right; int cnt[26],lazy; }L[N<<2]; int n,m; char str[N]; int cnt[26]; void push_up(int step){ for(int i=0;i<26;i++) L[step].cnt[i]=L[lson].cnt[i]+L[rson].cnt[i]; } void update(int step,int l,int r,int k); void push_down(int step){ if(L[step].lazy!=-1){ int l=L[step].left,r=L[step].right,m=(l+r)>>1; update(lson,l,m,L[step].lazy); update(rson,m+1,r,L[step].lazy); L[step].lazy=-1; } } void bulid(int step,int l,int r){ L[step].left=l; L[step].right=r; L[step].lazy=-1; mem(L[step].cnt,0); if(l==r){ L[step].cnt[str[l]-'a']++; L[step].lazy=str[l]-'a'; return ; } int m=(l+r)>>1; bulid(lson,l,m); bulid(rson,m+1,r); push_up(step); } void query(int step,int l,int r){ if(L[step].left==l&&L[step].right==r){ for(int i=0;i<26;i++) cnt[i]+=L[step].cnt[i]; return ; } int m=(L[step].left+L[step].right)>>1; push_down(step); if(r<=m) query(lson,l,r); else if(l>m) query(rson,l,r); else { query(lson,l,m); query(rson,m+1,r); } } void update(int step,int l,int r,int k){ if(L[step].left==l&&L[step].right==r){ mem(L[step].cnt,0); L[step].cnt[k]=r-l+1; L[step].lazy=k; return ; } push_down(step); int m=(L[step].left+L[step].right)>>1; if(r<=m) update(lson,l,r,k); else if(l>m) update(rson,l,r,k); else { update(lson,l,m,k); update(rson,m+1,r,k); } push_up(step); } void slove(int step){ if(L[step].left==L[step].right){ putchar(L[step].lazy+'a'); return ; } push_down(step); slove(lson); slove(rson); } int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d%s",&n,&m,str+1); bulid(1,1,n); while(m--){ int l,r; scanf("%d%d",&l,&r); mem(cnt,0); query(1,l,r); if((r-l+1)&1){ int k=0,p; for(int i=0;i<26;i++) if(cnt[i]&1) k++,p=i; if(k==1){ int a=l,b=r; cnt[p]--; for(int i=0;i<26;i++){ if(cnt[i]){ update(1,a,a+cnt[i]/2-1,i); update(1,b-cnt[i]/2+1,b,i); a+=cnt[i]/2; b-=cnt[i]/2; } } update(1,a,b,p); } } else{ int k=0; for(int i=0;i<26;i++) if(cnt[i]&1){ k=1; break; } if(!k){ int a=l,b=r; for(int i=0;i<26;i++){ if(cnt[i]){ update(1,a,a+cnt[i]/2-1,i); update(1,b-cnt[i]/2+1,b,i); a+=cnt[i]/2; b-=cnt[i]/2; } } } } } slove(1);putchar('\n'); return 0; }
