传送门 A Simple Task

题目大意，给你一个字符串，然后给你m个操作，每个操作都是对区间进行升序或者逆序排列
由于只有26个小写字母，所以我们可以维护26棵树

26棵树分别维护每一棵数的是否在区间是否有该字母

• 结构数组里面包含，l ，r， 和flag（lazy）来判断当前区间是否是一整个相同的状态，是否都有值，或者都没有值，和一个sum代表整个区间是什么值。
• pushdown操作，如果当前区间flag是1，，那么左儿子和右儿子的状态都等于当前区间，并把当前区间的flag置为0
• pushup操作，如果左右儿子的flag都等于，并且状态相同，那么当前节点的状态等于左儿子的状态，flag置为1
• modify操作，当 tr[u].l <= l && tr[u].r >= r ,将区间l~r都改为0，那么flag = 1 ，sum = 0 ，如果都该1 那么，flag= 1 ，sum = 1
• query操作，返回当前区间的和

在进行每一步操作的时候

1. 在进行升序操作的时候， 操作是 l，r，k
   可以先使用 last 记录 当前到哪里了这里 last = l
   那么 从0 ~ 25 遍历树，其实就是按照字典升序来遍历，
   先记录sum = 当前区间l ~ r中出现过多少个该字母
   然后，将该区间都置为0
   然后从last开始，到last + sum - 1 这sum个值就应该是该字母排完序所在的地方
   所以将last ~ last + sum - 1置为1，代表这个字母在当前区间有值

那么进行逆序操作类似
遍历时逆字典序遍历即可

参考代码

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 2e5 + 100, M = 26 ;

int n,m;
char str[N] ;
struct node
{
    int l,r,sum,flag ;
}tr[26][N * 4];       //26个树

void pushdown(node tr[],int u){   //pushdown操作，如果该节点flag = 1 ，将状态传递给左右儿子，然后左右儿子flag = 1 ，该节点flag = 0
    node & root = tr[u] , & left = tr[u << 1] ,  & right = tr[u << 1| 1] ;
    if(root.flag){
        left.flag = right.flag = 1; 
        left.sum = right.sum = root.sum ;
        root.flag = 0 ;
    }
}

void pushup(node tr[],int u){    //pushup操作，如果左右儿子flag都是1，并且状态相同，将左右儿子状态更新当前区间
    node & root = tr[u] , & left = tr[u << 1] ,  & right = tr[u << 1| 1] ;
    if(left.flag == 1 && right.flag == 1  && left.sum == right.sum){
        root.flag = 1; 
        root.sum = left.sum ;
    }
}

void build( node tr[] ,int u,int l,int r){  //初始化
    tr[u] = {l,r,0,0} ;     //刚开始状态和flag都是0
    if(l != r){
        int mid = l + r >> 1 ;
        build(tr,u << 1,l , mid ) , build(tr,u << 1 | 1, mid + 1 ,r) ;
    }
}

void modify(node tr[],int u,int l,int r,int x){   
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].flag = 1 ;
        if(x == 1){               //如果是1，则将sum置为1，这里不写if，else可以，直接写tr[u].sum = x 
            tr[u].sum = 1 ;          //这样写是为了表述清楚
        }
        else if(x == 0){
            tr[u].sum = 0 ; 
        }
    }
    else{
        pushdown(tr,u) ;
        int mid = tr[u].l + tr[u].r >> 1 ;
        if(l <= mid) modify(tr,u << 1 ,l,r,x) ;
        if(r >= mid + 1 )modify(tr,u << 1 | 1,l,r,x ) ;
        pushup(tr,u) ;
    }
}

int query(node tr[],int u,int l,int r){     //求出当前区间个数
    if(tr[u].flag){
        return tr[u].sum * (r - l + 1) ;
    }

    if(tr[u].l == tr[u].r && tr[u].l == l && l == r){
        return tr[u].sum ;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    int ans = 0 ;
    if(r <= mid ) ans = query(tr,u <<1 ,l,r) ;
    else if(l >= mid + 1) ans = query(tr,u << 1 | 1,l,r) ;
    else{
        ans += query(tr,u << 1 ,l ,mid) ;
        ans += query(tr,u << 1 | 1,mid + 1 ,r) ;
    } 
    return ans ;
}

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;

    cin >> n >> m ;
    cin >> (str + 1) ;

    for(int i = 0 ; i < M ; i++){
        build(tr[i],1,1,n) ;          //初始化26颗树
    }

    for(int i = 1 ; i <= n ; i++){
        modify(tr[str[i]-'a'],1,i,i,1) ;  //将初始字符串初始化树
    }

    while(m--){
        int x , y , k ;
        cin >> x >> y >> k ;
        if(k){                        //递增序
            int last = x ;
            for(int i = 0 ; i < M ; i++){
                int sum = query(tr[i],1,x,y);
                modify(tr[i],1,x,y,0) ;
                modify(tr[i],1,last,last + sum - 1 , 1) ;
                last += sum ;
            }
        }
        else{                      //递降序
            int last = x ;
            for(int i = M - 1 ; i >= 0 ; i--){
                int sum = query(tr[i],1,x,y);
                modify(tr[i],1,x,y,0) ;
                modify(tr[i],1,last,last + sum - 1 , 1) ;
                last += sum ;
            }
        }
    }


    for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j < M ; j++){         //暴力枚举每个点的字母是什么，找到了输出，break
            if(query(tr[j],1,i,i)){
                cout << (char)('a' + j) ;
                break ;
            }
        }
    }
    cout << "\n" ;
    return 0;
}

参考博客 111
222