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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 50;
int n, q, tot, root;
struct {
int lc, rc, c, tag = -1;
#define lc(x) tr[x].lc
#define rc(x) tr[x].rc
#define c(x) tr[x].c
#define tag(x) tr[x].tag
} tr[50 * maxn];
void down(int p, int l, int r) {
int mid = l + (r - l) / 2;
if (!lc(p)) lc(p) = ++tot;
if (!rc(p)) rc(p) = ++tot;
if (tag(p) == -1) return;
if (tag(p) == 0) {
c(lc(p)) = mid - l + 1, c(rc(p)) = r - mid;
} else {
c(lc(p)) = c(rc(p)) = 0;
}
tag(lc(p)) = tag(rc(p)) = tag(p);
tag(p) = -1;
}
void update(int p, int l, int r, int L, int R, int opt) {
if (L <= l && r <= R) {
c(p) = opt == 0 ? r - l + 1 : 0;
tag(p) = opt;
return;
}
down(p, l, r);
int mid = l + (r - l) / 2;
if (L <= mid) update(lc(p), l, mid, L, R, opt);
if (R > mid) update(rc(p), mid + 1, r, L, R, opt);
c(p) = c(lc(p)) + c(rc(p));
}
int main() {
scanf("%d%d", &n, &q);
root = ++tot;
int l, r, opt;
while (q--) {
scanf("%d%d%d", &l, &r, &opt);
--opt;
update(root, 1, n, l, r, opt);
printf("%d\n", n - c(root));
}
return 0;
}
|