#include using namespace std; typedef long long LL; LL sum; // 柯朵莉树模板 struct Node { int l, r; // l和r表示这一段的起点和终点 mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改 bool operator<(const Node &b) const { return l < b.l; // 规定按照每段的左端点排序 } }; set s; // 柯朵莉树的区间集合 // 分裂:[l,x-1],[x,r] set::iterator split(int x) { auto it = s.lower_bound({x}); if (it != s.end() && it->l == x) return it; // 一击命中 it--; // 没有找到就减1个继续找 if (it->r < x) return s.end(); // 真的没找到,返回s.end() int l = it->l, r = it->r, v = it->v; // 没有被返回,说明找到了,记录下来,防止后面删除时被破坏 s.erase(it); // 删除整个区间 s.insert({l, x - 1, v}); //[l,x-1]拆分 // insert函数返回pair,其中的first是新插入结点的迭代器 return s.insert({x, r, v}).first; //[x,r]拆分 } // 区间加 void add(int l, int r, int v) { // 必须先计算itr,后计算itl auto R = split(r + 1), L = split(l); for (auto it = L; it != R; it++) it->v += v; } // 区间赋值 void assign(int l, int r, int v) { auto R = split(r + 1), L = split(l); // 趁着没删除掉,赶快计算 int res = 0; for (auto it = L; it != R; it++) if (it->v != v) res += it->r - it->l + 1; // 一共有多少值会变 s.erase(L, R); // 按迭代器开始删除中部的所有块 s.insert({l, r, v}); // 插入新构建的整个的块 sum += (LL)((v == 0) ? -res : res); // 是加还是减 } int n, q; // 529 ms int main() { #ifndef ONLINE_JUDGE freopen("CF915E.in", "r", stdin); #endif // 加快读入 ios::sync_with_stdio(false), cin.tie(0); // 只有加上读入优化才能AC,否则会挂第16个点 cin >> n >> q; // 柯朵莉树插入最初始的块,值为1 s.insert({1, n, 1}); sum = n; while (q--) { int l, r; cin >> l >> r; int op; cin >> op; if (op == 1) { assign(l, r, 0); printf("%lld\n", sum); } else { assign(l, r, 1); printf("%lld\n", sum); } } return 0; }