题解 P1276 【校门外的树（增强版）】
chen_zhe
2017-05-28 20:13:56
这道题是可以用线段树做的，不过有点闲的没事干
```cpp
#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;
}
```