初始给定字符串S和一些Q查询。对于每个查询，您将有两个整数L和r。对于每个查询，您必须执行以下操作:
排列字母从L到R组成一个回文。如果您可以形成许多这样的回文，那么就选择字典上最小的那个。如果在重新排列字母时没有可能出现回文，则忽略该查询。
您必须在所有查询之后找到最终字符串。
约束条件包括:
1 <= length(S) <= 10^5
1 <= Q <= 10^5
1<= L <= R <= length(S)
示例输入:
4
间13
1样本输出:
反水雷舰
解释:初始字符串是mmcs，有一个查询要求从1 3生成一个回文，所以回文将是mcm。因此字符串将mcms.
如果每个查询需要O(N)时间，则总体时间复杂度为O(NQ)，这将得到TLE。因此，每个查询应该花费大约O(logn)时间。但是我想不出什么办法来解决这个问题。我认为，因为我们只需要找到最后的字符串，而不是什么每个查询结果，我想必须有一些其他的方法来处理这个问题。有人能帮帮我吗?
我们可以使用带范围更新的延迟段树来解决这个问题．我们将为每个角色制作片段树，所以总共会有26个片段树。在片段树的每个节点中，我们将存储该字符在该节点范围内的频率，并跟踪是否更新该范围。
因此对于每个查询执行以下操作->
- 给定L到R的范围
- 首先，我们将找到从L到R的每个字符的频率(这将取O)(26*log(n)) time)
- 现在从上面的频率计算奇数频率的字符数。
- If count>1、不能形成回文，否则可以形成回文
- 如果我们可以形成回文，然后，首先我们将分配0/L到R为每个字符在段树，然后我们将从最小的字符开始，并分配它超过(L,L+计数/2-1)和(R-计数/2+1,R)，然后更新L+ =计数/2和R- =计数/2
因此，每个查询的时间复杂度为O(26log(n))，构建段树的时间复杂度为O(nlog(n))，因此总时间复杂度为O(nlogn + q26logn)。
为了更好地理解，请参阅我的代码，
#include <bits/stdc++.h>
using namespace std;
#define enl 'n'
#define int long long
#define sz(s) (int)s.size()
#define all(v) (v).begin(),(v).end()
#define input(vec) for (auto &el : vec) cin >> el;
#define print(vec) for (auto &el : vec) cout << el << " "; cout << "n";
const int mod = 1e9+7;
const int inf = 1e18;
struct SegTree {
vector<pair<bool,int>>lazy;
vector<int>cnt;
SegTree () {}
SegTree(int n) {
lazy.assign(4*n,{false,0});
cnt.assign(4*n,0);
}
int query(int l,int r,int st,int en,int node) {
int mid = (st+en)/2;
if(st!=en and lazy[node].first) {
if(lazy[node].second) {
cnt[2*node] = mid - st + 1;
cnt[2*node+1] = en - mid;
}
else {
cnt[2*node] = cnt[2*node+1] = 0;
}
lazy[2*node] = lazy[2*node+1] = lazy[node];
lazy[node] = {false,0};
}
if(st>r or en<l) return 0;
if(st>=l and en<=r) return cnt[node];
return query(l,r,st,mid,2*node) + query(l,r,mid+1,en,2*node+1);
}
void update(int l,int r,int val,int st,int en,int node) {
int mid = (st+en)/2;
if(st!=en and lazy[node].first) {
if(lazy[node].second) {
cnt[2*node] = mid - st + 1;
cnt[2*node+1] = en - mid;
}
else {
cnt[2*node] = cnt[2*node+1] = 0;
}
lazy[2*node] = lazy[2*node+1] = lazy[node];
lazy[node] = {false,0};
}
if(st>r or en<l) return;
if(st>=l and en<=r) {
cnt[node] = (en - st + 1)*val;
lazy[node] = {true,val};
return;
}
update(l,r,val,st,mid,2*node);
update(l,r,val,mid+1,en,2*node+1);
cnt[node] = cnt[2*node] + cnt[2*node+1];
}
};
void solve() {
int n;
cin>>n;
string s;
cin>>s;
vector<SegTree>tr(26,SegTree(n));
for(int i=0;i<n;i++) {
tr[s[i]-'a'].update(i,i,1,0,n-1,1);
}
int q;
cin>>q;
while(q--) {
int l,r;
cin>>l>>r;
vector<int>cnt(26);
for(int i=0;i<26;i++) {
cnt[i] = tr[i].query(l,r,0,n-1,1);
}
int odd = 0;
for(auto u:cnt) odd += u%2;
if(odd>1) continue;
for(int i=0;i<26;i++) {
tr[i].update(l,r,0,0,n-1,1);
}
int x = l,y = r;
for(int i=0;i<26;i++) {
if(cnt[i]/2) {
tr[i].update(x,x+cnt[i]/2-1,1,0,n-1,1);
tr[i].update(y-cnt[i]/2+1,y,1,0,n-1,1);
x += cnt[i]/2;
y -= cnt[i]/2;
cnt[i]%=2;
}
}
for(int i=0;i<26;i++) {
if(cnt[i]) {
tr[i].update(x,x,1,0,n-1,1);
}
}
}
string ans(n,'a');
for(int i=0;i<26;i++) {
for(int j=0;j<n;j++) {
if(tr[i].query(j,j,0,n-1,1)) {
ans[j] = (char)('a'+i);
}
}
}
cout<<ans<<enl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int testcases = 1;
cin>>testcases;
while(testcases--) solve();
return 0;
}