Codeforces 588E. A Simple Task (线段树+计数排序思想)

题目链接：http://codeforces.com/contest/558/problem/E

题意：有一串字符串，有两个操作：1操作是将l到r的字符串升序排序，0操作是降序排序。

题解：建立26棵线段树，类似计数排序思想。

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 1e5 + ;

 struct SegTree {

     int lazy[], sum[], l, r;

 }T[N << ];

 int a[][N];

 void pushup(int p, int c) {

     T[p].sum[c] = T[p << ].sum[c] + T[(p << )|].sum[c];

 }

 void pushdown(int p, int c) {

     if(T[p].lazy[c] != -) {

         T[p << ].sum[c] = T[p].lazy[c]*(T[p << ].r - T[p << ].l + );

         T[(p << )|].sum[c] = T[p].lazy[c]*(T[(p << )|].r - T[(p << )|].l + );

         T[p << ].lazy[c] = T[(p << )|].lazy[c] = T[p].lazy[c];

         T[p].lazy[c] = -;

     }

 }

 void build(int p, int c, int l, int r) {

     int mid = (l + r) >> ;

     T[p].l = l, T[p].r = r, T[p].lazy[c] = -;

     if(l == r) {

         T[p].sum[c] = a[c][l];

         return ;

     }

     build(p << , c, l, mid);

     build((p << )|, c, mid + , r);

     pushup(p, c);

 }

 int query(int p, int c, int l, int r) {

     int mid = (T[p].l + T[p].r) >> ;

     if(T[p].l == l && T[p].r == r) {

         return T[p].sum[c];

     }

     pushdown(p, c);

     if(r <= mid) {

         return query(p << , c, l, r);

     } else if(l > mid) {

         return query((p << )|, c, l, r);

     } else {

         return query(p << , c, l, mid) + query((p << )|, c, mid + , r);

     }

     pushup(p, c);

 }

 void update(int p, int c, int l, int r, int val) {

     int mid = (T[p].l + T[p].r) >> ;

     if(T[p].l == l && T[p].r == r) {

         T[p].lazy[c] = val;

         T[p].sum[c] = val * (r - l + );

         return ;

     }

     pushdown(p, c);

     if(r <= mid) {

         update(p << , c, l, r, val);

     } else if(l > mid) {

         update((p << )|, c, l, r, val);

     } else {

         update(p << , c, l, mid, val), update((p << )|, c, mid + , r, val);

     }

     pushup(p, c);

 }

 char str[N];

 int main()

 {

     int n, m;

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

     scanf("%s", str);

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

         a[str[i] - 'a'][i + ] = ;

     }

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

         build(, i, , n);

     }

     while(m--) {

         int l, r, c;

         scanf("%d %d %d", &l, &r, &c);

         if(c) {

             int x = l, y = r;

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

                 if(x > y)

                     break;

                 int num = query(, i, l, r);

                 if(!num)

                     continue;

                 update(, i, l, r, );

                 update(, i, x, x + num - , );

                 x = x + num;

             }

         } else {

             int x = l, y = r;

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

                if(x > y)

                     break;

                 int num = query(, i, l, r);

                 if(!num)

                     continue;

                 update(, i, l, r, );

                 update(, i, x, x + num - , );

                 x = x + num;

             }

         }

     }

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

         for(int j = ; j < ; ++j) {

             if(query(, j, i, i)) {

                 putchar(char(j + 'a'));

                 break;

             }

         }

     }

     putchar('\n');

     return ;

 }

巴特西

Codeforces 588E. A Simple Task (线段树+计数排序思想)

最新文章

热门文章