Codeforces Round #312 (Div. 2) E. A Simple Task 線段樹 延時標記

Codeforces Round #312 (Div. 2) E. A Simple Task 線段樹 延時標記

E. A Simple Task
time limit per test5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
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.

Input
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
Output one line, the string S after applying the queries.

Sample test(s)
input
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
output
cbcaaaabdd
input
10 1
agjucbvdfk
1 10 1
output
abcdfgjkuv
Note
First sample test explanation:
題意，給一段字符串，然後一系列修改i,j之間的字符串從小到大排序，或從大到小排序，維護26的線段樹，i,j修改，只需要查詢一個a - z的個數，按計數排序的原理，更新一下線段樹就可以了，總的復雜度為o(26 * q * log(n));速度有點慢，用伸展樹應該快些。因為是成段更新，所以要用延時標記，記-1不更新，0全置0，1全置1，只有這點小技巧就可以了！

#define N 100005
#define M 100005
#define maxn 205
#define SZ 26
#define MOD 1000000000000000007
#define lson (now<<1)
#define rson (now<<1|1)
int n,q,ss,ee,k,num[SZ];
char str[N];
struct node{
    int c,sum,l,r;
};
node tree[SZ][N*4];
void pushDown(int tn,int now){
    if(tree[tn][now].c != -1){
        tree[tn][lson].c = tree[tn][rson].c = tree[tn][now].c;
        tree[tn][lson].sum = tree[tn][lson].c*(tree[tn][lson].r-tree[tn][lson].l + 1);
        tree[tn][rson].sum = tree[tn][rson].c*(tree[tn][rson].r-tree[tn][rson].l + 1);
        tree[tn][now].c = -1;
    }
}
void pushUp(int tn,int now){
    tree[tn][now].sum = tree[tn][lson].sum + tree[tn][rson].sum ;
}
void buildTree(int l,int r,int now){
    FI(SZ)
        tree[i][now].c = -1,tree[i][now].l = l,tree[i][now].r = r,tree[i][now].sum = 0;
    if(l >= r){
        return ;
    }
    int mid = (l+r)>>1;
    buildTree(l,mid,lson);
    buildTree(mid+1,r,rson);
}
void updateTree(int l,int r,int now,int s,int e,int tn,int c){
    if(s <= l && e>= r){
        tree[tn][now].c = c;
        tree[tn][now].sum = tree[tn][now].c*(tree[tn][now].r - tree[tn][now].l + 1);
        return ;
    }
    pushDown(tn,now);
    int mid = (l+r)>>1;
    if(s <= mid) updateTree(l,mid,lson,s,e,tn,c);
    if(e > mid) updateTree(mid+1,r,rson,s,e,tn,c);
    pushUp(tn,now);
}
int queryTree(int l,int r,int now,int s,int e,int tn){
    if(s <= l && e>= r){
        return tree[tn][now].sum;
    }
    pushDown(tn,now);
    int mid = (l+r)>>1;
    int ans = 0;
    if(s <= mid) ans += queryTree(l,mid,lson,s,e,tn);
    if(e > mid) ans += queryTree(mid+1,r,rson,s,e,tn);
    pushUp(tn,now);
    return ans;
}
void outputStr(){
     FI(n){
        FJ(SZ){
            if(queryTree(1,n,1,i+1,i+1,j)){
                printf(%c,j+'a');
                break;
            }
        }
    }
    printf(
);
}
int main()
{
    while(S2(n,q)!=EOF)
    {
        SS(str);
        buildTree(1,n,1);
        FI(n){
            updateTree(1,n,1,i+1,i+1,str[i] - 'a',1);
        }
        FI(q){
            S2(ss,ee);S(k);
            FJ(SZ)
                num[j] = queryTree(1,n,1,ss,ee,j);
            FJ(SZ)
                updateTree(1,n,1,ss,ee,j,0);
            if(k){
                int sum = 0;
                FJ(SZ){
                    if(num[j])
                        updateTree(1,n,1,ss + sum,ss + sum + num[j] - 1,j,1);
                    sum += num[j];
                }
            }
            else {
                int sum = 0;
                for(int j = SZ - 1;j>=0;j--){
                    if(num[j])
                        updateTree(1,n,1,ss + sum,ss + sum + num[j] - 1,j,1);
                    sum += num[j];
                }
            }
        }
        outputStr();
    }
    return 0;
}