程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces Round #312 (Div. 2) E. A Simple Task 線段樹 延時標記

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

編輯:關於C++

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;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved