C48 线段树+动态开点 CF915E Physical Education Lessons

#include <bits/stdc++.h> //线段树+动态开点 qlogn
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l + r) >> 1)
const int N = 3e5 + 10;
struct node{int ls, rs, s, laz;} tr[N * 50];int trlen,rt;
// s:区间和
void pushup(int p) { tr[p].s = tr[lc(p)].s + tr[rc(p)].s; }

void pushdown(int p, int l, int r)
{
	if(tr[p].laz==-1)return;
	if(!lc(p)) {lc(p)=++trlen;tr[lc(p)]={0,0,0,-1};}
	if(!rc(p)) {rc(p)=++trlen;tr[rc(p)]={0,0,0,-1};}
	
	tr[lc(p)].s=tr[p].laz*(mid-l+1);
	tr[lc(p)].laz=tr[p].laz;

	tr[rc(p)].s=tr[p].laz*(r-mid);
	tr[rc(p)].laz=tr[p].laz;

	tr[p].laz=-1;
}
void change(int &p, int l, int r, int x, int y, int k)// 区修
{ 
	if (!p)
	{
		p= ++trlen; // 动态开点
		tr[p]={0,0,0,-1};
	}
	if (x <= l && r <= y)
	{
		tr[p].s = k * (r - l + 1);
		tr[p].laz = k;
		return;
	}
	pushdown(p, l, r);
	if (x <= mid)change(lc(p), l,     mid, x, y, k);
	if (y > mid) change(rc(p), mid + 1, r, x, y, k);
	pushup(p);
}
int main()
{
	int n,q;scanf("%d%d", &n, &q);
	trlen=0;rt=0;
	for (int i = 1, l, r, opt; i <= q; i++)
	{
		scanf("%d%d%d", &opt, &l, &r);
		if (opt == 0)change(rt, 1, n, l, r, 0);
		else         change(rt, 1, n, l, r, 1);
		printf("%d\n", tr[rt].s);
	}
	return 0;
}