本文共 2553 字，大约阅读时间需要 8 分钟。

题解：

首先我们看到这个题是针对于字母进行排序的，区间操作很像线段树，那么如何把他转换成线段树呢？

#include 
   
    //#define int long long#define ll long longconst int maxn=2e5+10;using namespace std;const int p=1e9+10;int sum[maxn*4][30];int a[maxn];int lazy[maxn];void push_up(int node){
       for(int i=1;i<=26;i++){
           sum[node][i]=sum[node*2][i]+sum[node*2+1][i];    }}void build(int node,int start,int ends){
       if(start==ends){
           sum[node][a[start]]++;        return ;    }    int mid=(start+ends)/2;    build(node*2,start,mid);    build(node*2+1,mid+1,ends);    push_up(node);}void push_down(int node,int start,int ends){
       if(lazy[node]){
           for(int i=0;i<=26;i++){
               sum[node*2][i]=sum[node*2+1][i]=0;        }        int mid=(start+ends)/2;        sum[node*2][lazy[node]]=mid-start+1;        sum[node*2+1][lazy[node]]=ends-mid;        lazy[node*2]=lazy[node*2+1]=lazy[node];    }    lazy[node]=0;}void update(int node,int start,int ends,int l,int r,int val){
       if(start>=l&&ends<=r){
           lazy[node]=val;        for(int i=1;i<=26;i++) sum[node][i]=0;        sum[node][val]=ends-start+1;        return ;    }    push_down(node,start,ends);    int mid=(start+ends)/2;    if(l<=mid) update(node*2,start,mid,l,r,val);    if(mid
    
     =l&&ends<=r){
           for(int i=1;i<=26;i++){
               ans[i]+=sum[node][i];        }        return ;    }    int mid=(start+ends)/2;    push_down(node,start,ends);    if(l<=mid) query(node*2,start,mid,l,r);    if(mid
     
      >n>>q;    string s;    cin>>s;    for(int i=0;i
      
       >l>>r>>opt;        memset(ans,0,sizeof ans);        if(opt==1){
               query(1,1,n,l,r);            int pos=l;            for(int i=1;i<=26;i++){
                   if(ans[i]){
                       update(1,1,n,pos,pos+ans[i]-1,i);                    pos=pos+ans[i];                }            }        }        else{
               query(1,1,n,l,r);            int pos=l;            for(int i=26;i>=1;i--){
                   if(ans[i]){
                       update(1,1,n,pos,pos+ans[i]-1,i);                    pos=pos+ans[i];                }            }        }    }    memset(ans,0,sizeof ans);    for(int i=1;i<=n;i++){
           query(1,1,n,i,i);        for(int i=1;i<=26;i++){
               if(ans[i]){
                   cout<<(char)(i+'a'-1);                ans[i]--;            }        }    }}
      
     
    
   

转载地址：https://blog.csdn.net/xxxxxiao123/article/details/115538696 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！