题目

开始给出一个长度为\(n\)的小写字母串，\(m\)次操作，每次选一个区间，把这个区间进行升序或降序排序。最后输出所有操作结束后的串。

\(n\le 10^5,m\le 5\times 10^4\)

分析

神思路！！

其实主要是要注意到这个字母表为26非常小，所以可以考虑使用基数排序！事实上排序也可以看成统计每种数有多少个按顺序输出的过程。

二十六颗线段树，维护区间中每种字母的出现次数。排序的时候遍历所有的字母，把该排在前面的全部移到前面。这可以用一个支持区间求和，区间加法，区间清零的线段树来做，写的时候标记可以用一个二元组来表示，\(x=a_0*x+a_1*len\)。

总而言之用每个字母的位置来刻画这个序列。

其实很多字符串问题都是基于字母表比较小来做的。

代码

#include<cstdio> #include<cctype> #include<cstring> #include<utility> #include<algorithm> using namespace std; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1e5+1; const int maxc=26; int n,m; char s[maxn]; pair<int,int> operator + (pair<int,int> a,pair<int,int> b) { return make_pair(a.first*b.first,a.second*b.first+b.second); } struct SGT { int t[maxn<<2]; pair<int,int> tag[maxn<<2]; void build(int x,int l,int r) { if (l==r) return; t[x]=0,tag[x]=make_pair(1,0); int mid=(l+r)>>1; build(x<<1,l,mid),build(x<<1|1,mid+1,r); } void doit(int x,int l,int r,pair<int,int> d) { t[x]=t[x]*d.first+(r-l+1)*d.second; tag[x]=tag[x]+d; } void pushdown(int x,int l,int mid,int r) { doit(x<<1,l,mid,tag[x]); doit(x<<1|1,mid+1,r,tag[x]); tag[x]=make_pair(1,0); } void modify(int x,int L,int R,int l,int r,pair<int,int> d) { if (L==l && R==r) { doit(x,L,R,d); return; } int mid=(L+R)>>1; pushdown(x,L,mid,R); if (r<=mid) modify(x<<1,L,mid,l,r,d); else if (l>mid) modify(x<<1|1,mid+1,R,l,r,d); else modify(x<<1,L,mid,l,mid,d),modify(x<<1|1,mid+1,R,mid+1,r,d); t[x]=t[x<<1]+t[x<<1|1]; } void clear(int l,int r) { if (l>r) return; modify(1,1,n,l,r,make_pair(0,0)); } void inc(int l,int r) { if (l>r) return; modify(1,1,n,l,r,make_pair(1,1)); } int query(int x,int L,int R,int l,int r) { if (L==l && R==r) return t[x]; int mid=(L+R)>>1; pushdown(x,L,mid,R); if (r<=mid) return query(x<<1,L,mid,l,r); if (l>mid) return query(x<<1|1,mid+1,R,l,r); return query(x<<1,L,mid,l,mid)+query(x<<1|1,mid+1,R,mid+1,r); } int query(int l,int r) { if (l>r) return 0; return query(1,1,n,l,r); } } sgt[maxc]; int main() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif n=read(),m=read(); scanf("%s",s+1); for (int i=0;i<maxc;++i) sgt[i].build(1,1,n); for (int i=1;i<=n;++i) sgt[s[i]-'a'].inc(i,i); while (m--) { int l=read(),r=read(),o=read(); if (o) { int alr=0; for (int i=0;i<maxc;++i) { int tmp=sgt[i].query(l,r); sgt[i].clear(l,r); sgt[i].inc(l+alr,l+alr+tmp-1); alr+=tmp; } } else { int alr=0; for (int i=maxc-1;i>=0;--i) { int tmp=sgt[i].query(l,r); sgt[i].clear(l,r); sgt[i].inc(l+alr,l+alr+tmp-1); alr+=tmp; } } } for (int i=1,j;i<=n;++i) { for (j=0;j<maxc;++j) if (sgt[j].query(i,i)) { putchar('a'+j); break; } } puts(""); return 0; }

转载于:https://www.cnblogs.com/owenyu/p/7155598.html