题解 P1276 【校门外的树（增强版）】

chen_zhe · 2017-05-28 20:13:56 · 题解

这道题是可以用线段树做的，不过有点闲的没事干

#include <iostream>
#include <cstdio>

using namespace std;

struct Seg_Tree
{
    int left,right,value;//value表示：2为树苗 1为树木 0为没有树 -1为不能当做整体 可以省略一个标记 
}son[150000];

int l,n,ans1=0,ans2=0;

void Build(int id,int left,int right) //没什么好说的建树 
{
    son[id].left=left;
    son[id].right=right;
    son[id].value=1;
    if (left==right) return;
    Build(id<<1,left,(left+right)>>1);
    Build(id<<1|1,((left+right)>>1)+1,right);
}

void Update_Cut(int id,int left,int right) //砍树 
{
    int mid=(son[id].left+son[id].right)>>1; //计算分段的位置 
    if (son[id].value!=1 && son[id].value!=-1) son[id<<1].value=son[id<<1|1].value=son[id].value; //继承 
    if (left==son[id].left && right==son[id].right)
    {//此处代码可以优化到更短 
        if (son[id].value==0) return; //没有树可以不砍 
        if (son[id].value==1) son[id].value=0; //有树木直接砍掉 
        if (son[id].value==2)
        {
            son[id].value=0; //树苗也要砍 
            ans1+=(son[id].right-son[id].left)+1; //计算种上被砍掉的树苗 
            ans2=ans2-(son[id].right-son[id].left+1); //计算留下的树苗 
        }
        if (son[id].value==-1) //不能一起做就交给自己的左儿子和右儿子做 
        {
            son[id].value=0;
            Update_Cut(id<<1,left,(left+right)>>1);
            Update_Cut(id<<1|1,((left+right)>>1)+1,right);
        }
    }
    else
    {
        if (right<=mid) Update_Cut(id<<1,left,right);
        else if (left>mid) Update_Cut(id<<1|1,left,right);
        else
        {
            Update_Cut(id<<1,left,mid);
            Update_Cut(id<<1|1,mid+1,right);
        } //“三部曲”往下推 
        if (son[id<<1].value!=son[id<<1|1].value) son[id].value=-1;
            else son[id].value=son[id<<1].value; //判断左右儿子是否相等，确定是否要整体一起做 
    }
}

void Update_Plant(int id,int left,int right)
{
    int mid=(son[id].left+son[id].right)>>1;
    if (son[id].value!=1 && son[id].value!=-1) son[id<<1].value=son[id<<1|1].value=son[id].value; //同上 
    if (left==son[id].left && right==son[id].right)
    {
        if (son[id].value==1 || son[id].value==2) return; //树木不要种！ 
        if (son[id].value==0)
        {
            son[id].value=2;
            ans2+=(son[id].right-son[id].left)+1; //计算树苗的个数 
        }
        if (son[id].value==-1) //防止下面有树木，所以不要在这里做son[id].value=2 
        {
            Update_Plant(id<<1,left,(left+right)>>1);
            Update_Plant(id<<1|1,((left+right)>>1)+1,right);
        }
    }
    else
    {
        if (right<=mid) Update_Plant(id<<1,left,right);
        else if (left>mid) Update_Plant(id<<1|1,left,right);
        else
        {
            Update_Plant(id<<1,left,mid);
            Update_Plant(id<<1|1,mid+1,right);
        }
        if (son[id<<1].value!=son[id<<1|1].value) son[id].value=-1;
            else son[id].value=son[id<<1].value; //同上 
    }
}

int main()
{
    scanf("%d%d",&l,&n);
    Build(1,0,l);
    for (int i=1;i<=n;i++)
    {
        int c,a,b;
        scanf("%d%d%d",&c,&a,&b);
        if (a>b) swap(a,b); //防止a>b 
        if (c==0) Update_Cut(1,a,b);
            else Update_Plant(1,a,b);
    }
    printf("%d\n%d\n",ans2,ans1);
    return 0;
}