competitive-programming/codeforces/558/E.cpp at master · fricai/competitive-programming · GitHub

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
115
#include <iostream>
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;

const int S = 26;
struct node {
	int f[S];
	node() { }
	node(int c, int x = 1) {
		rep(i, 0, S) f[i] = 0;
		f[c] = x;
	}
	node operator+(node a) {
		node res;
		rep(i, 0, S) res.f[i] = f[i] + a.f[i];
		return res;
	}
};

int n;
const int N = 1 << 17;
node t[N << 1];
int u[N << 1];

void build(int v = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		char c; cin >> c;
		t[v] = node(c - 'a');
	} else {
		int m = (l + r) >> 1;
		build(v << 1, l, m);
		build(v << 1|1, m + 1, r);
		t[v] = t[v << 1] + t[v << 1|1];
	}
}

void apply(int v, int sz, int x) {
	t[v] = node(x, sz);
	u[v] = x;
}

void push(int v, int l, int r) {
	if (u[v] != -1) {
		int m = (l + r) >> 1;
		apply(v << 1, m - l + 1, u[v]);
		apply(v << 1 | 1, r - m, u[v]);
		u[v] = -1;
	}
}

node freq(int lo, int hi, int v = 1, int l = 0, int r = n - 1)  {
	if (l == lo && r == hi) return t[v];
	push(v, l, r);
	int m = (l + r) >> 1;
	if (hi <= m) return freq(lo, hi, v << 1, l, m);
	if (lo  > m) return freq(lo, hi, v << 1|1, m + 1, r);
	return freq(lo, m, v << 1, l, m) + freq(m + 1, hi, v << 1|1, m + 1, r);
}

void upd(int lo, int hi, int val, int v = 1, int l = 0, int r = n - 1) {
	if (lo == l && hi == r) apply(v, r - l + 1, val);
	else {
		push(v, l, r);
		int m = (l + r) >> 1;
		if (hi <= m) upd(lo, hi, val, v << 1, l, m);
		else if (lo > m) upd(lo, hi, val, v << 1|1, m + 1, r);
		else {
			upd(lo, m, val, v << 1, l, m);
			upd(m + 1, hi, val, v << 1|1, m + 1, r);
		}
		t[v] = t[v << 1] + t[v << 1|1];
	}
}

char get(int p, int v = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		rep(c, 0, S) if (t[v].f[c]) return c + 'a';
	}
	push(v, l, r);
	int m = (l + r) >> 1;
	if (p <= m) return get(p, v << 1, l, m);
	else return get(p, v << 1|1, m + 1, r);
}

void opt(int l, int r, bool k) {
	node x = freq(l, r);
	if (k) {
		int prev = l;
		rep(c, 0, S) {
			if (x.f[c]) {
				upd(prev, prev + x.f[c] - 1, c);
				prev += x.f[c];
			}
		}
	} else {
		int nxt = r;
		rep(c, 0, S) {
			if (x.f[c]) {
				upd(nxt - x.f[c] + 1, nxt, c);
				nxt -= x.f[c];
			}
		}
	}
}

signed main() {
	rep(i, 0, N << 1) u[i] = -1;
	int q; cin >> n >> q;
	build();
	while (q--) {
		int i, j, k; cin >> i >> j >> k; --i, --j;
		opt(i, j, k);
	}
	rep(i, 0, n) cout << get(i);
}