P1276 校门外的树（增强版）（线段树）（校门三部曲）难度⭐⭐⭐

校门三部曲，总算完结了！完结散花！
难度呈阶梯状，都可以用线段树解决。
第一部
P1047 校门外的树（线段树优化）难度⭐⭐
第二部
P1276 校门外的树（增强版）（线段树）校门三部曲难度⭐⭐⭐
第三部
P5568 [SDOI2008]校门外的区间（离散数学应用+线段树+开闭区间处理）难度⭐⭐⭐⭐★

本题题目链接

因为本题只需要最后询问一次即可，所以不需要一直更新答案
建两棵线段树（两颗最好用结构体建树比较方便）
种树只在第一棵树种，第一棵树是树和苗的总和，第二颗树只有树
tree[0].ans是砍去的树和树苗的总和
tree[1].ans是砍去的树
对于第一问，留下的树苗数等于：留下的（树与树苗）总数减去留下的（树）的总数。
对于第二问，种上又被拔掉的树苗数等于：被砍掉的（树与树苗）总数减去被砍掉的（树）的总数。

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;

typedef long long ll;
const ll N=1e4+7;
ll n,m;

struct segment
{
    ll lz[N<<2];
    ll sum[N<<2];
    ll ans;
    segment()
    {
        ans=0;
        memset(lz,0,sizeof lz);
        memset(sum,0,sizeof sum);
    }
    void build(ll p,ll l,ll r)
    {
        if(l==r)
        {
            sum[p]=1;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        sum[p]=sum[ls]+sum[rs];
    }
    void push_down(ll p,ll l,ll r)
    {
        if(lz[p]==1)//种
        {
            lz[ls]=lz[rs]=1;
            sum[ls]=mid-l+1;
            sum[rs]=r-mid;
        }
        if(lz[p]==-1)//砍
        {
            lz[ls]=lz[rs]=-1;
            sum[ls]=sum[rs]=0;
        }
        lz[p]=0;
    }

    void plant(ll p,ll l,ll r,ll L,ll R)
    {
        if(L<=l&&r<=R)
        {
            lz[p]=1;
            sum[p]=r-l+1;
            return;
        }
        push_down(p,l,r);
        if(L<=mid)plant(ls,l,mid,L,R);
        if(mid+1<=R)plant(rs,mid+1,r,L,R);
        sum[p]=sum[ls]+sum[rs];
    }
    void cut(ll p,ll l,ll r,ll L,ll R)
    {
        if(L<=l&&r<=R)
        {
            lz[p]=-1;
            ans+=sum[p];//先加上
            sum[p]=0;//再砍掉
            return ;
        }
        push_down(p,l,r);//因为上面是没有往下操作的所以必须push_down往下更新
        if(L<=mid)cut(ls,l,mid,L,R);
        if(mid+1<=R)cut(rs,mid+1,r,L,R);
        sum[p]=sum[ls]+sum[rs];
    }
}tree[2];
#undef mid
int main()
{
    scanf("%lld %lld",&n,&m);
    n++;
    tree[0].build(1,1,n);
    tree[1].build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        ll p,l,r;
        scanf("%lld %lld %lld",&p,&l,&r);
        l++,r++;
        if(p==0)tree[0].cut(1,1,n,l,r),tree[1].cut(1,1,n,l,r);
        if(p==1)tree[0].plant(1,1,n,l,r);//只种第一棵树
    }
    printf("%lld\n",tree[0].sum[1]-tree[1].sum[1]);
    printf("%lld\n",tree[0].ans-tree[1].ans);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜