题意
Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！
Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：
从现在到学期结束还有 \(n\) 天(从 \(1\) 到 \(n\) 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 \(q\) 个指令，每个指令可以用三个参数 \(l,r,k\) 描述：
-
如果 \(k=1\)，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成非工作日。
-
如果 \(k=2\)，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成工作日。
帮助Alex统计每个指令下发后，剩余的工作日天数。
\(1\le n\le 10^9,\;1\le q\le 3\cdot 10^5\)
Translated by 小粉兔
思路
\(n \le 1e9\)，大受震撼。
正解是珂朵莉树，然而为什么不选择会蹦会跳的小动态开点线段树呢？
直接整一个动态开点线段树维护区间赋值就完事了
……吗？
本题中动态开点的空间复杂度大约为 \(O(q\log n)\)，如果使用指针的动态开点方式将当场去世。因为一个指针和一个 long long 是等长的。压都压不动。
所以只能屈辱地选择数组式动态开点，搭配各类奇技淫巧卡常。
代码
寄在 #18 MLE 的指针代码。一路走好。
#define mid ((l+r)>>1)
struct node{
node *ls,*rs;
ll val;
bool g;
node(){
ls=0,rs=0;
val=0,g=0;
}
void upd(){
val=ls->val+rs->val;
}
void push_down(ll l,ll r){
ls->g=1;
ls->val=(val?1:0)*(mid-l+1);
rs->g=1;
rs->val=(val?1:0)*(r-mid);
g=0;
}
};
node *rt;
void modify(node *x,ll l,ll r,ll ls,ll rs,ll ty){
if(ls<=l&&r<=rs){
x->val=ty*(r-l+1);
x->g=1;
return ;
}
if(!x->ls)x->ls=new node;
if(!x->rs)x->rs=new node;
if(x->g)x->push_down(l,r);
if(ls<=mid)modify(x->ls,l,mid,ls,rs,ty);
if(rs>mid)modify(x->rs,mid+1,r,ls,rs,ty);
x->upd();
}
ll n,m;
signed main(){
scanf("%d%d",&n,&m);
rt=new node;
ll l,r,ty;
while(m--){
scanf("%d%d%d",&l,&r,&ty);
ty&=1;
modify(rt,1,n,l,r,ty);
printf("%d\n",n-rt->val);
}
return 0;
}
AC 代码：
const ll maxn=1.5e7+10;
ll t[maxn],ls[maxn],rs[maxn];
bool g[maxn];
ll tot=1;
ll n,m;
#define mid ((l+r)>>1)
void upd(ll x){
t[x]=t[ls[x]]+t[rs[x]];
}
void push_down(ll x,ll l,ll r){
g[ls[x]]=g[rs[x]]=1;
t[ls[x]]=t[x]?(mid-l+1):0;
t[rs[x]]=t[x]?(r-mid):0;
g[x]=0;
}
void modify(ll x,ll l,ll r,ll L,ll R,ll ty){
if(L<=l&&r<=R){
t[x]=ty?(r-l+1):0;
g[x]=1;
return ;
}
if(!ls[x])ls[x]=++tot;
if(!rs[x])rs[x]=++tot;
if(g[x])push_down(x,l,r);
if(L<=mid)modify(ls[x],l,mid,L,R,ty);
if(R>mid)modify(rs[x],mid+1,r,L,R,ty);
upd(x);
}
signed main(){
scanf("%d%d",&n,&m);
ll l,r,ty;
while(m--){
scanf("%d%d%d",&l,&r,&ty);
ty&=1;
modify(1,1,n,l,r,ty);
printf("%d\n",n-t[1]);
}
return 0;
}