题目链接

CF915E Physical Education Lessons

题解

动态开点线段树

代码

/* 动态开点线段树 */ #include<cstdio> #include<cstring> #include<algorithm> inline int read() { int x = 0,f = 1; char c = getchar() ; while(c < '0' || c > '9')c = getchar(); while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); return x * f; } const int maxn = 500007 * 30; int rt = 0; struct Segtree { int tot ; int ls[maxn],rs[maxn],tag[maxn],sum[maxn]; void pushdown(int x,int l,int r) { int mid = l + r >> 1; if(l != r) { if(!ls[x]) ls[x] = ++ tot; //记得开点这里 if(!rs[x]) rs[x] = ++ tot; sum[ls[x]] = (mid - l + 1) * tag[x]; sum[rs[x]] = (r - mid) * tag[x]; tag[ls[x]] = tag[x]; tag[rs[x]] = tag[x]; } tag[x] = -1; } void modify(int &x,int l,int r,int L,int R,int w) { if(!x) x = ++ tot; if(l >= L && r <= R) { sum[x] = (r - l + 1) * w; tag[x] = w; return; } if(tag[x] >= 0) pushdown(x,l,r); int mid = l + r >> 1; if(L <= mid) modify(ls[x],l,mid,L,R,w); if(R > mid) modify(rs[x],mid + 1,r,L,R,w); sum[x] = sum[ls[x]] + sum[rs[x]]; } } t; int main() { int n = read(); int m = read(); memset(t.tag,-1,sizeof t.tag); for(int type,l,r,i = 1;i <= m;++ i) { l = read(),r = read(),type = read(); if(type == 1) t.modify(rt,1,n,l,r,1); else t.modify(rt,1,n,l,r,0); printf("%d\n",n - t.sum[1]); } return 0; }

转载于:https://www.cnblogs.com/sssy/p/9525727.html