1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include<bits/stdc++.h>
#define ls id<<1 #define rs id<<1|1 #define mid (l+r)/2 using namespace std; const int N = 100005; int n, q, ans[N], a[N]; char s[N]; struct node { int num, laz = -1; } tree[30][400005];
void build(int id, int l, int r) { if (l == r) { tree[a[l]][id].num = 1; return; } build(ls, l, mid); build(rs, mid + 1, r); for (int i = 1; i <= 26; i++) { tree[i][id].num = tree[i][ls].num + tree[i][rs].num; } }
void pushdown(int id, int l, int r, int p) { if (tree[p][id].laz == -1) { return; } tree[p][ls].num = tree[p][id].laz * (mid - l + 1); tree[p][rs].num = tree[p][id].laz * (r - mid); tree[p][ls].laz = tree[p][rs].laz = tree[p][id].laz; tree[p][id].laz = -1; }
void update(int id, int l, int r, int x, int y, int p, int v) { if (x <= l && r <= y) { tree[p][id].num = v * (r - l + 1); tree[p][id].laz = v; return; } pushdown(id, l, r, p); if (x <= mid) update(ls, l, mid, x, y, p, v); if (y > mid) update(rs, mid + 1, r, x, y, p, v); tree[p][id].num = tree[p][ls].num + tree[p][rs].num; }
int query(int id, int l, int r, int x, int y, int p) { if (x <= l && r <= y) { return tree[p][id].num; } pushdown(id, l, r, p); int ans = 0; if (x <= mid) ans += query(ls, l, mid, x, y, p); if (y > mid) ans += query(rs, mid + 1, r, x, y, p); return ans; }
void out(int id, int l, int r) { if (l == r) { for (int i = 1; i <= 26; i++) { if (tree[i][id].num) { ans[l] = i;
break; } } return; } for (int i = 1; i <= 26; i++) { pushdown(id, l, r, i); } out(ls, l, mid); out(rs, mid + 1, r); }
int main() { ios::sync_with_stdio(false); cin >> n >> q >> s + 1;
for (int i = 1; i <= n; i++) { a[i] = s[i] - 'a' + 1; } build(1, 1, n);
for (int i = 1; i <= q; i++) { int x, y, op; cin >> x >> y >> op; int tmp = x; if (op == 1) { for (int j = 1; j <= 26; j++) { int cnt = query(1, 1, n, x, y, j); if (!cnt) continue; update(1, 1, n, x, y, j, 0); update(1, 1, n, tmp, tmp + cnt - 1, j, 1); tmp += cnt; } } else { for (int j = 26; j >= 1; j--) { int cnt = query(1, 1, n, x, y, j); if (!cnt) continue; update(1, 1, n, x, y, j, 0); update(1, 1, n, tmp, tmp + cnt - 1, j, 1); tmp += cnt; } } } out(1, 1, n); for (int i = 1; i <= n; i++) { char ch = ans[i] + 'a' - 1; cout << ch; } return 0; }
|