给出长度为n的字符串，m个操作。

每一个操作有三个值 l,r,op。

op==1，表示将字符串中[ l ,r ]的部分依照升序排列。

op==0，表示将字符串中[ l ,r ]的部分依照降序排列。

输出终于的字符串

按小写字母建26颗线段树

对于每次改动，先记录[l,r]区间内各个字母出现的次数，并对对应区间清空，然后依照升序或者降序从新更新

#include "stdio.h"

#include "string.h"

char str[100010];

int n,temp;

struct node

{

    int l,r,x,lazy;

}data[30][400010];

void build(int l,int r,int k,int op)

{

    int mid;

    data[op][k].l=l;

    data[op][k].r=r;

    data[op][k].x=0;

    data[op][k].lazy=-1;

    if (l==r)

        return ;

    mid=(l+r)/2;

    build(l,mid,k*2,op);

    build(mid+1,r,k*2+1,op);

}

void Pushdown(int k,int op)

{

    if (data[op][k].lazy==-1) return ;

    if (data[op][k].l==data[op][k].r) return ;

    if (data[op][k].lazy==0)

    {

        data[op][k*2].x=data[op][k*2].lazy=0;

        data[op][k*2+1].x=data[op][k*2+1].lazy=0;

    }

    else

    {

        data[op][k*2].x=data[op][k*2].r-data[op][k*2].l+1;

        data[op][k*2+1].x=data[op][k*2+1].r-data[op][k*2+1].l+1;

        data[op][k*2].lazy=data[op][k*2+1].lazy=1;

    }

    data[op][k].lazy=-1;

}

void updata(int l,int r,int k,int op)

{

    int mid;

    if (data[op][k].l==l && data[op][k].r==r)

    {

        data[op][k].x=data[op][k].r-data[op][k].l+1;

        data[op][k].lazy=1;

        return;

    }

    Pushdown(k,op);

    mid=(data[op][k].l+data[op][k].r)/2;

    if (r<=mid) updata(l,r,k*2,op);

    else

        if (l>mid) updata(l,r,k*2+1,op);

    else

    {

        updata(l,mid,k*2,op);

        updata(mid+1,r,k*2+1,op);

    }

    data[op][k].x=data[op][k*2].x+data[op][k*2+1].x;

}

void  search(int l,int r,int k,int op)

{

    int mid;

    if (data[op][k].l==l && data[op][k].r==r)

    {

        temp+=data[op][k].x;

        data[op][k].x=0;

        data[op][k].lazy=0;

        return ;

    }

    Pushdown(k,op);

    mid=(data[op][k].l+data[op][k].r)/2;

    if (r<=mid) search(l,r,k*2,op);

    else if (l>mid)  search(l,r,k*2+1,op);

    else

    {

        search(l,mid,k*2,op);

        search(mid+1,r,k*2+1,op);

    }

    data[op][k].x=data[op][k*2].x+data[op][k*2+1].x;

}

void init()

{

    int i;

    scanf("%s",str);

    for (i=0;i<26;i++)

        build(1,n,1,i);

    for (i=0;i<n;i++)

        updata(i+1,i+1,1,str[i]-'a');

}

int main()

{

    int m,a,b,c,i,j,k;

    int mark[30];

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        init();

        while (m--)

        {

            scanf("%d%d%d",&a,&b,&c);

            memset(mark,0,sizeof(mark));

            for (i=0;i<26;i++)

            {

                temp=0;

                search(a,b,1,i); // 查找区间内i字母出现的次数，并清空

                mark[i]+=temp;

            }

            if (c==0)

            {

                k=a;

                for (i=25;i>=0;i--)

                    if (mark[i]!=0)

                    {

                        updata(k,k+mark[i]-1,1,i); // 更新区间字母

                        k+=mark[i];

                    }

            }

            else

            {

                k=a;

                for (i=0;i<26;i++)

                    if (mark[i]!=0)

                    {

                        updata(k,k+mark[i]-1,1,i);

                        k+=mark[i];

                    }

            }

        }

        for (i=1;i<=n;i++)

        {

            for (j=0;j<26;j++)

            {

                temp=0;

                search(i,i,1,j);

                if (temp!=0)

                {

                    printf("%c",j+'a');

                    break;

                }

            }

        }

        printf("\n");

    }

    return 0;

}