fork(13) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <vector>
  10. #include <map>
  11. #include <sstream>
  12. #include <cmath>
  13. #include <limits>
  14. #include <utility>
  15. #include <iomanip>
  16. #include <set>
  17. #include <numeric>
  18. #include <cassert>
  19. #include <ctime>
  20.  
  21. #define INF_MAX 2147483647
  22. #define INF_MIN -2147483647
  23. #define INF_LL 9223372036854775807LL
  24. #define INF 2000000000
  25. #define PI acos(-1.0)
  26. #define EPS 1e-8
  27. #define LL long long
  28. #define mod 1000000007
  29. #define pb push_back
  30. #define mp make_pair
  31. #define f first
  32. #define s second
  33. #define setzero(a) memset(a,0,sizeof(a))
  34. #define setdp(a) memset(a,-1,sizeof(a))
  35. #define bits(a) __builtin_popcount(a)
  36.  
  37. using namespace std;
  38.  
  39. int tree[400005][27], lazy[400005][27];
  40. char s[100005];
  41.  
  42. void build(int i,int L,int R)
  43. {
  44.   if(L == R)
  45.   {
  46.     tree[i][s[L] - 'a'] = 1;
  47.     for(int j=0;j<26;j++)
  48.       lazy[i][j] = -1;
  49.     return ;
  50.   }
  51.   build(i*2 + 1, L, (L + R) / 2);
  52.   build(i*2 + 2, (L + R) / 2 + 1, R);
  53.   for(int j=0;j<26;j++)
  54.   {
  55.     lazy[i][j] = -1;
  56.     tree[i][j] = tree[i*2 + 1][j] + tree[i*2 + 2][j];
  57.   }
  58. }
  59.  
  60. void update(int i, int L, int R, int x, int y, int val, int j)
  61. {
  62.   if(lazy[i][j] != -1)
  63.   {
  64.     tree[i][j] = lazy[i][j] * (R - L + 1);
  65.     if(L != R)
  66.     {
  67.       lazy[i*2+1][j] = lazy[i][j];
  68.       lazy[i*2+2][j] = lazy[i][j];
  69.     }
  70.     lazy[i][j] = -1;
  71.   }
  72.   if(L >= x && R <= y)
  73.   {
  74.     lazy[i][j] = val;
  75.     tree[i][j] = lazy[i][j] * (R - L + 1);
  76.     if(L != R)
  77.     {
  78.       lazy[i*2+1][j] = lazy[i][j];
  79.       lazy[i*2+2][j] = lazy[i][j];
  80.     }
  81.     lazy[i][j] = -1;
  82.     return;
  83.   }
  84.   if(L > y || R < x)
  85.     return;
  86.   update(i*2 + 1, L, (L + R) / 2, x, y, val, j);
  87.   update(i*2 + 2, (L + R) / 2 + 1, R, x, y, val, j);
  88.   tree[i][j] = tree[i*2 + 1][j] + tree[i*2 + 2][j];
  89. }
  90.  
  91. int query(int i, int L, int R, int x, int y, int j)
  92. {
  93.   if(lazy[i][j] != -1)
  94.   {
  95.     tree[i][j] = lazy[i][j] * (R - L + 1);
  96.     if(L != R)
  97.     {
  98.       lazy[i*2+1][j] = lazy[i][j];
  99.       lazy[i*2+2][j] = lazy[i][j];
  100.     }
  101.     lazy[i][j] = -1;
  102.   }
  103.   if(L >= x && R <= y)
  104.     return tree[i][j];
  105.   if(L > y || R < x)
  106.     return 0;
  107.   return query(i*2 + 1, L, (L + R) / 2, x, y, j) + query(i*2 + 2, (L + R) / 2 + 1, R, x, y, j);
  108. }
  109.  
  110. void get(int i, int L, int R, int j)
  111. {
  112.   if(lazy[i][j] != -1)
  113.   {
  114.     tree[i][j] = lazy[i][j] * (R - L + 1);
  115.     if(L != R)
  116.     {
  117.       lazy[i*2+1][j] = lazy[i][j];
  118.       lazy[i*2+2][j] = lazy[i][j];
  119.     }
  120.     lazy[i][j] = -1;
  121.   }
  122.   if(!tree[i][j])
  123.     return ;
  124.   if(L == R)
  125.   {
  126.     s[L] = j + 'a';
  127.     return;
  128.   }
  129.   get(i*2 + 1, L, (L + R) / 2, j);
  130.   get(i*2 + 2, (L + R) / 2 + 1, R, j);
  131. }
  132.  
  133. int cnt[26];
  134.  
  135. int main()
  136. {
  137.   //ios_base::sync_with_stdio(0);
  138.   //freopen("test0.txt", "r", stdin);
  139.   //freopen("lca.out", "w", stdout);
  140.   int n, q, x, y, up;
  141.   scanf("%d %d", &n, &q);
  142.   scanf("%s", s);
  143.   build(0, 0, n - 1);
  144.   for(int i=0;i<q;i++)
  145.   {
  146.     scanf("%d %d %d", &x, &y, &up);
  147.     x--, y--;
  148.     for(int j=0;j<26;j++)
  149.       cnt[j] = query(0, 0, n - 1, x, y, j);
  150.     int curr = x;
  151.     if(!up) curr = y;
  152.     for(int j=0;j<26;j++)
  153.     {
  154.       if(!cnt[j]) continue;
  155.       update(0, 0, n - 1, x, y, 0, j);
  156.       if(up)
  157.       {
  158.         update(0, 0, n - 1, curr, curr + cnt[j] - 1, 1, j);
  159.         curr+=cnt[j];
  160.       }
  161.       else
  162.       {
  163.         update(0, 0, n - 1, curr - cnt[j] + 1, curr, 1, j);
  164.         curr-=cnt[j];
  165.       }
  166.     }
  167.   }
  168.   for(int i=0;i<26;i++)
  169.     get(0, 0, n - 1, i);
  170.   printf("%s", s);
  171.   return 0;
  172. }
Success #stdin #stdout 0s 87616KB
comments (?)
stdin
copy 
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
stdout
copy 
cbcaaaabdd
https://ideone.com/wHwvnU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!