题解 | #A Simple Task# 线段树

题解：
这种题之前做过一个类似的题目，也是关于选择区间然后给区间进行排序。
这种题用线段树把排序转换成区间修改区间求和即可。
类似的题目：https://vjudge.net/problem/HDU-5649

首先我们看到这个题是针对于字母进行排序的，区间操作很像线段树，那么如何把他转换成线段树呢？
我们考虑他只有26个字母，那么我们是否可以转换成维护这26个字母呢？
对于每一段区间，我们查询每个字母出现的个数。
然后按照题目要求（升序还是降序）然后从l到r依次填从小到大填入字母即可。
转换为了区间修改和区间查询操作。

#include <bits/stdc++.h>

//#define int long long
#define ll long long
const 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<r) update(node*2+1,mid+1,ends,l,r,val);
    push_up(node);
}
int ans[30];
void query(int node,int start,int ends,int l,int r){
    if(start>=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<r) query(node*2+1,mid+1,ends,l,r);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        a[i+1]=s[i]-'a'+1;
    }
    build(1,1,n);
    query(1,1,n,2,n);
    while(q--){
        int l,r,opt;
        cin>>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]--;
            }
        }
    }
}