动态开点线段树
题目链接
题目暗示了区间修改，所以我们自然想到了用线段树来维护非工作日的天数。
然而我们再看一下数据范围，天数n的范围是(1 le n le 10^9)，像普通线段树一样预处理显然会爆空间。
天无绝人之路，我们看一下修改个数，$1le q le 3 cdot 10^5 $， 比天数少很多，这也意味着，我们预先处理好的线段树有些节点并没有用
能否优化呢？答案是肯定的，这就是动态开点线段树，顾名思义，我们只要到用某个节点的时候，才分配一个点给它。这样使得我们使用的空间大大减少。其余的与普通线段树大致是相同的。
最后再说一下，本题的数组要开大一些，否则会疯狂(RE)
代码奉上~
#include<bits/stdc++.h>
using namespace std;
int tree[15001000],lson[15001000],rson[15001000],tag[15001000],d;
long long n,q,l,r,k;
void freelazy(int x,int l,int r)
{
int mid=(l+r)/2;
if (tree[x])
{
tree[lson[x]]=(mid-l+1);
tree[rson[x]]=(r-(mid+1)+1);
}
else
{
tree[lson[x]]=0;
tree[rson[x]]=0;
}
tag[lson[x]]=1;
tag[rson[x]]=1;
tag[x]=0;
//正常的懒标记下放操作
}
void add(int x,int l,int r,int ql,int qr,int sd)
{
if (ql<=l&&qr>=r)
{
tree[x]=(r-l+1)*sd;tag[x]=1;
return ;
}
if (!lson[x])
{
d++;
lson[x]=d;
}
if (!rson[x])
{
d++;
rson[x]=d;
}//要用就开点
//上面要记得记录左右儿子
if (tag[x]) freelazy(x,l,r);
int mid=(l+r)/2;
if (ql>mid)
{
add(rson[x],mid+1,r,ql,qr,sd);
}
else
if (qr<=mid)
{
add(lson[x],l,mid,ql,qr,sd);
}
else
{
add(lson[x],l,mid,ql,mid,sd);
add(rson[x],mid+1,r,mid+1,qr,sd);
}
tree[x]=tree[lson[x]]+tree[rson[x]];
//正常的线段树操作
}
int main()
{
cin>>n>>q;d=1;
for (int i=1;i<=q;i++)
{
scanf("%d%d%d",&l,&r,&k);//本题用cin、cout会有超时风险
if (l>r) swap(l,r);
if (k==1)
{
add(1,1,n,l,r,k);
}
else
{
add(1,1,n,l,r,0);
}
printf("%d
",n-tree[1]);
}
return 0;
}