1.前言

这里专门写一篇动态开点,因为上次学习点分树的时候很难受,这里专门写一篇动态开点,来记录一下...
所谓的动态开点,就是指你的线段树没必要建成满二叉树的形式,因为有些节点的访问根本用不到,类似lazy吧,但是lazy是时间上的节省,体现在后面查询时,而动态开点是在前面建树,对于空间的节省.

2.引例

CF915E Physical Education Lessons
这个题很容易想到就是线段树的区间修改和区间查询,但是它的一个难点就是n<=1e9.这可咋办?但是我们可以注意到q<=3e5.也就是说它访问的区间还是不超过6e5个点.如此我们是不是可以在更新的时候建树,顺带查询答案呢?显然是可以的,这就是动态开点.

3.代码

讲了这么多(少?)总觉得有点小小的抽象,那么下面就看看代码吧~:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5e6;
int lazy[N],ls[N],rs[N],sum[N],root,cnt;//线段树节点u的左右两个端点.以及这个端点的权值.
void pushdown(int u,int l,int r)
{
    if(~lazy[u])
    {
        if(!ls[u])    ls[u]=++cnt;
        if(!rs[u])    rs[u]=++cnt;
        int mid=(l+r)>>1;
        sum[ls[u]]=(mid-l+1)*lazy[u];
        sum[rs[u]]=(r-mid)*lazy[u];
        lazy[ls[u]]=lazy[rs[u]]=lazy[u];
        lazy[u]=-1;
    }
}

void modify(int &u,int l,int r,int L,int R,int val)
{
    if(!u)    u=++cnt;
    if(L<=l&&r<=R)
    {
        sum[u]=val*(r-l+1);
        lazy[u]=val;
        return;
    }int mid=(l+r)>>1;
    pushdown(u,l,r);
    if(L<=mid)    modify(ls[u],l,mid,L,R,val);
    if(R>mid)    modify(rs[u],mid+1,r,L,R,val);
    sum[u]=sum[ls[u]]+sum[rs[u]];
}

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    //我们假设工作日为0,非工作日为1.这样比较方便.
    memset(lazy,-1,sizeof lazy);
    modify(root,1,n,1,n,0);
    while(q--)
    {
        int L,R,k;
        scanf("%d%d%d",&L,&R,&k);
        modify(root,1,n,L,R,2-k);//区间修改成2-k.
        printf("%d\n",n-sum[1]);//输出答案.
    }
    return 0;
}