题目链接：

http://codeforces.com/problemset/problem/558/E

E. A Simple Task

time limit per test5 seconds
memory limit per test512 megabytes
#### 问题描述
> This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.
>
> Output the final string after applying the queries.

输入

The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).

输出

Output one line, the string S after applying the queries.

样例输入

10 5

abacdabcda

7 10 0

5 8 1

1 4 0

3 6 0

7 10 1

样例输出

cbcaaaabdd

题意

给你一个长度为n的字符串（只有小写字母），m个更新操作（l,r,type）要么对区间里面的字符串升序排，要么降序排，问m个更新之后最后的字符串是什么

题解

首先，只有26个字母，可以考虑计数排序，其次，当然是要用线段树来维护了，可以开26颗线段树，支持区间更新，区间查询。

对于更新区间先查询一下各个字母多少个，然后再按排完序的结果，26个字母（对应26颗线段树）全部干一发区间更新。

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef __int64 LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=1e5+10;

int sumv[26][maxn<<2],setv[26][maxn<<2];

int n,m;

char str[maxn];

void maintain(int id,int o) {

    sumv[id][o]=sumv[id][lson]+sumv[id][rson];

}

void pushdown(int id,int o,int l,int r) {

    if(setv[id][o]<0) return;

    sumv[id][lson]=(mid-l+1)*setv[id][o];

    sumv[id][rson]=(r-mid)*setv[id][o];

    setv[id][lson]=setv[id][rson]=setv[id][o];

    setv[id][o]=-1;

}

void build(int id,int o,int l,int r) {

    if(l==r) {

        int idx=str[l]-'a';

        if(id==idx) sumv[id][o]=1;

        else sumv[id][o]=0;

    } else {

        build(id,lson,l,mid);

        build(id,rson,mid+1,r);

        maintain(id,o);

    }

}

int ul,ur,uv;

void update(int id,int o,int l,int r) {

    if(ul<=l&&r<=ur) {

        sumv[id][o]=(r-l+1)*uv;

        setv[id][o]=uv;

    } else {

        pushdown(id,o,l,r);

        if(ul<=mid) update(id,lson,l,mid);

        if(ur>mid) update(id,rson,mid+1,r);

        maintain(id,o);

    }

}

int ql,qr,qv;

void query(int id,int o,int l,int r) {

    if(ql<=l&&r<=qr) {

        qv+=sumv[id][o];

    } else {

        pushdown(id,o,l,r);

        if(ql<=mid) query(id,lson,l,mid);

        if(qr>mid) query(id,rson,mid+1,r);

        maintain(id,o);

    }

}

void init() {

    clr(sumv,0);

    clr(setv,-1);

}

int main() {

    init();

    scf("%d%d",&n,&m);

    scf("%s",str+1);

    rep(i,0,26) build(i,1,1,n);

    rep(i,0,m) {

        int l,r,type;

        scf("%d%d%d",&l,&r,&type);

        int lef=l;

        if(type==1) {

            rep(i,0,26) {

                ql=l,qr=r,qv=0;

                query(i,1,1,n);

                ul=l,ur=r,uv=0;

                update(i,1,1,n);

                ul=lef,ur=lef+qv-1,uv=1;

                if(ul<=ur) update(i,1,1,n);

                lef+=qv;

            }

        } else {

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

                ql=l,qr=r,qv=0;

                query(i,1,1,n);

                ul=l,ur=r,uv=0;

                update(i,1,1,n);

                ul=lef,ur=lef+qv-1,uv=1;

                if(ul<=ur){

//                    prf("(%d,%d),id:%d\n",ul,ur,i);

                    update(i,1,1,n);

                }

                lef+=qv;

            }

        }

    }

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

        rep(j,0,26){

            ql=i,qr=i,qv=0;

            query(j,1,1,n);

            if(qv>0){

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

                break;

            }

        }

    }

    puts("");

    return 0;

}

//end-----------------------------------------------------------------------

/*

10 1

abacdabcda

7 10 0

*/

Notes

以后需要建多颗线段树的时候最好把它们所有的操作都独立开，不要放在一起！因为放在一起反而有可能变麻烦。

巴特西

Codeforces Round #312 (Div. 2) E. A Simple Task 线段树+计数排序

题目链接：

E. A Simple Task

输入

输出

样例输入

样例输出

题意

题解

代码

Notes

最新文章

热门文章