题目大意
请使用文件输入输出！
给定一个长为\(n\)的由a到z组成的字符串,有\(m\)次操作，每次操作将\([l,r]\)这些位置的字符进行重排，得到字典序最小的回文字符串，如果无法操作就不进行。
求\(m\)次操作后的字符串。
\(n,m<=100000\)
分析
初一看，没什么下手的地方。
但是我们仔细分析一下，给我们一个区间[l,r]让我们去将这个区间的字符串重组为一个字典序最小的回文串，如果不行就不做了。并且只有26个字符。
那这就提示，我们可以根据每个字符建立一颗线段树。
我们来，分析一下操作。
我们需要看一下，这个区间每个字符的数量。
如果该区间长度为奇数，则必须有且只有一个字符的数量为奇数。如果该区间长度为偶数，则必须全部为偶数。
判完合法后。接下来对于每一个字符，我们只需要对称的在区间上赋值即可。
看代码。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
struct Node
{
int l,r;
int sum,cov;
}tr[26][N<<2];
int n,m;
string s;
void pushup(int u,int k)
{
tr[k][u].sum = tr[k][u<<1].sum + tr[k][u<<1|1].sum;
}
void build(int u,int l,int r,int k)
{
tr[k][u] = {l,r,0,-1};
if(l==r)
{
if((s[l-1]-'a')==k) tr[k][u].sum = 1;
return ;
}
int mid = l + r >> 1;
build(u<<1,l,mid,k),build(u<<1|1,mid+1,r,k);
pushup(u,k);
}
void pushdown(int u,int k)
{
auto &root = tr[k][u],&left = tr[k][u<<1],&right = tr[k][u<<1|1];
if(root.cov!=-1)
{
left.sum = (left.r - left.l + 1)*root.cov;
left.cov = root.cov;
right.sum = (right.r - right.l + 1)*root.cov;
right.cov = root.cov;
root.cov = -1;
return ;#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
struct Node
{
int l,r;
int sum,cov;
}tr[26][N<<2];
int n,m;
string s;
void pushup(int u,int k)
{
tr[k][u].sum = tr[k][u<<1].sum + tr[k][u<<1|1].sum;
}
void build(int u,int l,int r,int k)
{
tr[k][u] = {l,r,0,-1};
if(l==r)
{
if((s[l-1]-'a')==k) tr[k][u].sum = 1;
return ;
}
int mid = l + r >> 1;
build(u<<1,l,mid,k),build(u<<1|1,mid+1,r,k);
pushup(u,k);
}
void pushdown(int u,int k)
{
auto &root = tr[k][u],&left = tr[k][u<<1],&right = tr[k][u<<1|1];
if(root.cov!=-1)
{
left.sum = (left.r - left.l + 1)*root.cov;
left.cov = root.cov;
right.sum = (right.r - right.l + 1)*root.cov;
right.cov = root.cov;
root.cov = -1;
return ;
}
}
void modify(int u,int l,int r,int t,int k)
{
if(l<=tr[k][u].l&&tr[k][u].r<=r)
{
tr[k][u].sum = (tr[k][u].r - tr[k][u].l + 1) * t;
tr[k][u].cov = t;
return ;
}
pushdown(u,k);
int mid = tr[k][u].l + tr[k][u].r >> 1;
if(l<=mid) modify(u<<1,l,r,t,k);
if(r>mid) modify(u<<1|1,l,r,t,k);
pushup(u,k);
}
int query(int u,int l,int r,int k)
{
// cout<<tr[k][u].l<<" "<<tr[k][u].r<<endl;
if(l<=tr[k][u].l&&tr[k][u].r<=r) return tr[k][u].sum;
int mid = tr[k][u].l + tr[k][u].r >> 1;
pushdown(u,k);
int res = 0;
if(l<=mid) res += query(u<<1,l,r,k);
if(r>mid) res += query(u<<1|1,l,r,k);
return res;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios;
cin>>n>>m;
cin>>s;
for(int i=0;i<26;i++) build(1,1,n,i);
while(m--)
{
int l,r;cin>>l>>r;
int a[26];
int cnt = 0;
for(int i=0;i<26;i++)
{
a[i] = query(1,l,r,i);
// cout<<a[i]<<"\n";
if(a[i]&1) cnt++;
}
if((r-l+1)&1)
{
if(cnt!=1) continue;
}
else if(cnt!=0) continue;
int L = l,R = r;
for(int i=0;i<26;i++)
{
modify(1,l,r,0,i);
if(a[i]&1) modify(1,(l+r)>>1,(l+r)>>1,1,i),a[i]--;
if(!a[i]) continue;
int t = a[i]>>1;
modify(1,L,L+t-1,1,i),modify(1,R-t+1,R,1,i);
L += t,R -= t;
}
}
string res;
for(int i=1;i<=n;i++)
for(int j=0;j<26;j++)
if(query(1,i,i,j))
{
res.push_back('a'+j);
break;
}
cout<<res<<"\n";
return 0;
}
}
}
void modify(int u,int l,int r,int t,int k)
{
if(l<=tr[k][u].l&&tr[k][u].r<=r)
{
tr[k][u].sum = (tr[k][u].r - tr[k][u].l + 1) * t;
tr[k][u].cov = t;
return ;
}
pushdown(u,k);
int mid = tr[k][u].l + tr[k][u].r >> 1;
if(l<=mid) modify(u<<1,l,r,t,k);
if(r>mid) modify(u<<1|1,l,r,t,k);
pushup(u,k);
}
int query(int u,int l,int r,int k)
{
// cout<<tr[k][u].l<<" "<<tr[k][u].r<<endl;
if(l<=tr[k][u].l&&tr[k][u].r<=r) return tr[k][u].sum;
int mid = tr[k][u].l + tr[k][u].r >> 1;
pushdown(u,k);
int res = 0;
if(l<=mid) res += query(u<<1,l,r,k);
if(r>mid) res += query(u<<1|1,l,r,k);
return res;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios;
cin>>n>>m;
cin>>s;
for(int i=0;i<26;i++) build(1,1,n,i);
while(m--)
{
int l,r;cin>>l>>r;
int a[26];
int cnt = 0;
for(int i=0;i<26;i++)
{
a[i] = query(1,l,r,i);
// cout<<a[i]<<"\n";
if(a[i]&1) cnt++;
}
if((r-l+1)&1)
{
if(cnt!=1) continue;
}
else if(cnt!=0) continue;
int L = l,R = r;
for(int i=0;i<26;i++)
{
modify(1,l,r,0,i);
if(a[i]&1) modify(1,(l+r)>>1,(l+r)>>1,1,i),a[i]--;
if(!a[i]) continue;
int t = a[i]>>1;
modify(1,L,L+t-1,1,i),modify(1,R-t+1,R,1,i);
L += t,R -= t;
}
}
string res;
for(int i=1;i<=n;i++)
for(int j=0;j<26;j++)
if(query(1,i,i,j))
{
res.push_back('a'+j);
break;
}
cout<<res<<"\n";
return 0;
}