CF915E

一直 MLE，自认为和题解写的一样了

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+1;

int n, q, l, r, k;
int tot, root, sum[MAXN], lazy[MAXN], ls[MAXN], rs[MAXN];

inline void push_down(int now, int l, int r)
{
	if(~lazy[now])
	{
		int mid = l + r >> 1;
		
		if(!ls[now]) ls[now] = ++tot;
		sum[ls[now] ] = lazy[now] * (mid - l + 1);
		lazy[ls[now] ] = lazy[now];
		
		if(!rs[now]) rs[now] = ++tot;
		sum[rs[now] ] = lazy[now] * (r - mid);
		lazy[rs[now] ] = lazy[now];
		
		lazy[now]=-1;
	}
}

inline void update(int &now, int l, int r, int ql, int qr, int opt)
{
	if(!now) now = ++tot;
	if(ql <= l && r <= qr)
	{
		sum[now] = (r - l + 1) * opt;
		lazy[now] = opt;
		return;
	}
	
	push_down(now,l,r);
	
	int mid = l + r >> 1;
	
	if(l <= mid) update(ls[now], l, mid, ql, qr, opt);
	if(mid < r) update(rs[now], mid+1, r, ql, qr, opt);
	
	sum[now] = sum[ls[now] ] + sum[rs[now] ];
}

int main()
{
	scanf("%d%d", &n, &q);
	memset(lazy, -1, sizeof lazy);
	
	update(root, 1, n, 1, n, 0);

	while(q--)
	{
		scanf("%d%d%d", &l, &r, &k);
		update(root, 1, n, l, r, 2 - k);
		printf("%d\n", n - sum[1]);
	}
	
	return 0;
}