\(\text{Links}\)
题外话
-
今天小卖部有可爱多，但是发生意外导致我没有吃到，破防了，我真的破防了。
-
今晚的饭不难吃。
-
不懂这题怎么评到 *2600，感觉虚高。
-
好吧代码写得有点长。
-
尝试了黑树所说的东西，感觉挺好！
题意
给定一个长度为 \(n\) \((n\le 10^5)\) 的小写字母序列 \(a\)，有 \(m\) \((m\le 10^5)\) 次操作，每次操作给定 \(l,r\)，你需要先判断序列中 \([l,r]\) 的部分是否能够通过重排列构成回文串，如果能的话，就把它们重排为回文串并满足此部分字典序最小，否则不进行任何操作。求 \(m\) 次操作之后的序列。
3.00s 250.00MB
题解
首先只考虑判定，十分简单，形如 P3604 美好的每一天，状压一下每个字符出现次数的奇偶性，满足至多只有一个字符出现奇数次即可。可以差分直接解决静态版本，动态版本直接改成 \(\text{SegT}\) 即可。
然后考虑操作。考虑把 \(\text{SegT}\) 记录每个字符的出现次数的奇偶性扩展为直接记录 \(cnt\)。
每次查询 \(cnt\) 并存在数组里面，然后把每个字符出现次数砍半，然你后在线段树上把它们 \(\text{sort}\) 进去。利用线段树递归到的区间是从左到右的顺序的特性，直接用一个 \(pos\) 扫一下就好。后面一半部分倒着做一遍一样的就行。如果操作区间长度为奇数就单独找出中间那个字符然后单独做一下就好。
然后，在 \(\text{SegT}\) 上记录 \(tag=0/1/2\) 分别表示没有标记，有升序 \(\text{sort}\) \(tag\) 以及有降序 \(\text{sort}\) \(tag\)，\(\text{Pushdown}\) 的时候和上面一样的操作，用 \(pos\) 正着或者倒着扫一遍就行。
时间复杂度 \(O(n\log n V)\)，其中 \(V\) 为字符集大小。
以上是我的做法，事实上有点复杂，然后下面介绍一种来自 Zi_Gao 的更简洁的做法。
考虑字典序最小的限制会使两边相同的字符都各会排在一起（中间单独的字符除外），所以最多只会产生 \(26\times 2+1=53\) 个连续颜色段。直接对每个段做一次区间覆盖即可。
时间复杂度也是 \(O(n\log n V)\)，但是听着就明显感觉要简洁很多。
警示后人
请开 freopen。请开 freopen。请开 freopen。
本人因为这个 ILE 浪费了时间。
\(\text{AC Code}\)（4.8k 震撼代码警告）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=1e5+113,V=30;
int n,m,a[N],tmp[V],pos,tmp2[V];
char str[N];
il int lowbit(int x){
return x&(-x);
}
struct SegT{
int cnt[V],mask,tag;
}L[N<<2];
#define ls (id<<1)
#define rs (id<<1|1)
il void CalcMask(SegT &fa){
fa.mask=0;
for(re int i=0;i<26;i++)
if(fa.cnt[i]&1)fa.mask+=(1<<i);
}
il void Pushup(SegT &fa,SegT lson,SegT rson){
for(re int i=0;i<26;i++)
fa.cnt[i]=lson.cnt[i]+rson.cnt[i];
CalcMask(fa);
}
il void Pushdown(SegT &fa,SegT &lson,SegT &rson,int l,int r){
int t=fa.tag,mid=(l+r)>>1;
if(!t)return;
lson.tag=rson.tag=t;
int lenL=mid-l+1,tot=0;
for(re int i=0;i<26;i++)
lson.cnt[i]=rson.cnt[i]=0;
re int i;
if(t==1){
i=0;
for(;i<26;i++){
tot+=fa.cnt[i];
if(tot>=lenL){
tot-=fa.cnt[i],tot=lenL-tot;
lson.cnt[i]=tot;
break;
}
lson.cnt[i]=fa.cnt[i];
}
rson.cnt[i]=fa.cnt[i]-tot,i++;
for(;i<26;i++)rson.cnt[i]=fa.cnt[i];
}
else{
i=26;
for(;i>=0;i--){
tot+=fa.cnt[i];
if(tot>=lenL){
tot-=fa.cnt[i],tot=lenL-tot;
lson.cnt[i]=tot;
break;
}
lson.cnt[i]=fa.cnt[i];
}
rson.cnt[i]=fa.cnt[i]-tot,i--;
for(;i>=0;i--)rson.cnt[i]=fa.cnt[i];
}
CalcMask(lson),CalcMask(rson);
fa.tag=0;
}
il int GetMask(int id,int l,int r,int x,int y){
if(l>=x&&r<=y){
for(re int i=0;i<26;i++)
tmp[i]+=L[id].cnt[i];
return L[id].mask;
}
int mid=(l+r)>>1;
Pushdown(L[id],L[ls],L[rs],l,r);
int res=0;
if(x<=mid)res^=GetMask(ls,l,mid,x,y);
if(y>mid)res^=GetMask(rs,mid+1,r,x,y);
return res;
}
il void Sort(int id,int l,int r,int x,int y,int op){
if(l>=x&&r<=y){
L[id].tag=op;
re int tot=0,len=r-l+1;
for(re int i=0;i<26;i++)L[id].cnt[i]=0;
if(op==1){
for(;pos<26;pos++){
tot+=tmp[pos];
if(tot>=len){
tot-=tmp[pos],tot=len-tot;
tmp[pos]-=tot;
L[id].cnt[pos]=tot;
break;
}
L[id].cnt[pos]=tmp[pos],tmp[pos]=0;
}
}
else{
for(;pos>=0;pos--){
tot+=tmp[pos];
if(tot>=len){
tot-=tmp[pos],tot=len-tot;
tmp[pos]-=tot;
L[id].cnt[pos]=tot;
break;
}
L[id].cnt[pos]=tmp[pos],tmp[pos]=0;
}
}
CalcMask(L[id]);
return;
}
int mid=(l+r)>>1;
Pushdown(L[id],L[ls],L[rs],l,r);
if(x<=mid)Sort(ls,l,mid,x,y,op);
if(y>mid)Sort(rs,mid+1,r,x,y,op);
Pushup(L[id],L[ls],L[rs]);
}
il void Print(int id,int l,int r){
if(l==r){
putchar('a'+__builtin_ctz(L[id].mask));
return;
}
int mid=(l+r)>>1;
Pushdown(L[id],L[ls],L[rs],l,r);
Print(ls,l,mid),Print(rs,mid+1,r);
}
il void Build(int id,int l,int r){
if(l==r){
L[id].cnt[a[l]]=1;
L[id].mask=(1<<a[l]);
return;
}
int mid=(l+r)>>1;
Build(ls,l,mid),Build(rs,mid+1,r);
Pushup(L[id],L[ls],L[rs]);
}
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read(),m=read();
scanf("%s",str+1);
for(re int i=1;i<=n;i++)a[i]=str[i]-'a';
Build(1,1,n);
while(m--){
int l=read(),r=read(),mid=(l+r)>>1;
if(l==r)continue;
for(re int i=0;i<26;i++)tmp[i]=0;
int mask=GetMask(1,1,n,l,r);
if(mask&&(mask^lowbit(mask)))continue;
if(mask){
int ch=__builtin_ctz(mask);
tmp[ch]--;
for(re int i=0;i<26;i++)
tmp[i]>>=1,tmp2[i]=tmp[i];
pos=0,Sort(1,1,n,l,mid-1,1);
tmp[ch]++,pos=ch,Sort(1,1,n,mid,mid,1);
for(re int i=0;i<26;i++)tmp[i]=tmp2[i];
pos=26,Sort(1,1,n,mid+1,r,2);
}
else{
for(re int i=0;i<26;i++)
tmp[i]>>=1,tmp2[i]=tmp[i];
pos=0,Sort(1,1,n,l,mid,1);
for(re int i=0;i<26;i++)tmp[i]=tmp2[i];
pos=26,Sort(1,1,n,mid+1,r,2);
}
}
Print(1,1,n);
return 0;
}