P1276 校门外的树(增强版)

感觉这题还可以,不像以前的模板题一样,貌似教会我一些其他的东西...2333贴个代码吧~

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int ans1=0,ans2=0;
struct Tree{
    int l,r,len,val;//1表示原来那颗大树,0表示没树苗,2表示有树苗,-1表示这个节点不能全部包括. 
}tr[N<<2];

void cut(int u,int l,int r)
{
    if(tr[u].l>r||tr[u].r<l)    return;
    if(tr[u].val!=-1)    tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
    if(l<=tr[u].l&&tr[u].r<=r&&tr[u].val!=-1)
    {
        if(tr[u].val==1)    tr[u].val=0;
        if(tr[u].val==2)
        {
            ans1-=tr[u].len;
            ans2+=tr[u].len;
            tr[u].val=0;
        }
        return;
    }
    cut(u<<1,l,r);
    cut(u<<1|1,l,r);
    if(tr[u<<1].val!=tr[u<<1|1].val) tr[u].val=-1;
    else tr[u].val=tr[u<<1].val;
}

void plant(int u,int l,int r)
{
    if(tr[u].l>r||tr[u].r<l)    return;
    if(tr[u].val!=-1)    tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
    if(l<=tr[u].l&&tr[u].r<=r&&tr[u].val!=-1)
    {
        if(tr[u].val==0)    ans1+=tr[u].len,tr[u].val=2;
        return;
    }
    plant(u<<1,l,r);
    plant(u<<1|1,l,r);
    if(tr[u<<1].val!=tr[u<<1|1].val) tr[u].val=-1;
    else tr[u].val=tr[u<<1].val;
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].val=1,tr[u].len=(r-l+1);
    if(l==r)    return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);n++;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        b++,c++;
        if(a==0)    cut(1,b,c);
        else        plant(1,b,c);
    }printf("%d\n%d\n",ans1,ans2);//校门外留下的树苗数目 种上又被拔掉的树苗数目
    return 0;
}