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
| #include <iostream>
#include <set>
#include <algorithm>
using namespace std;
struct Node {
int l, r;
mutable int v;
Node(int l, int r, int v) : l(l), r(r), v(v) {}
bool operator <(const Node &o) const {
return l < o.l;
}
};
int n, q, s;
set<Node> tree;
set<Node>::iterator split(int pos) {
auto it = tree.lower_bound({pos, 0, 0});
if (it != tree.end() && it->l == pos)
return it;
--it;
auto [l, r, v] = *it;
tree.erase(it);
tree.insert({l, pos - 1, v});
return tree.insert({pos, r, v}).first;
}
void assign(int l, int r, int v) {
auto end = split(r + 1), begin = split(l);
int tot = 0, len = 0;
for (auto it = begin; it != end; ++it) {
len += (it->r - it->l + 1);
tot += it->v * (it->r - it->l + 1);
}
tree.erase(begin, end);
tree.insert({l, r, v});
if (v) s += (len - tot);
else s -= tot;
}
int main(void) {
scanf("%d%d", &n, &q);
tree.insert({1, n, 1});
s = n;
while (q--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
assign(l, r, k != 1);
printf("%d\n", s);
}
return 0;
}
|