校门外的树（线段树做法）

校门外马路上本来从编号0到L，每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树，就连树苗也不放过（记 0 A B ，含A和B）；幸运的是还有植树者每次从编号C到D 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含C和D）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

输入格式
第一行L和N,表示校园外原来有L+1棵树，并有N次砍树或种树的操作。

以下N行，砍树或植树的标记和范围，每行3个整数。

L（1 <= L <= 10000）和 N（1 <= N <= 100）

输出格式
共两行。第1行校门外留下的树苗数目，第2行种上又被拔掉的树苗数目。

输入输出样例
输入 #1复制
10 3
0 2 6
1 1 8
0 5 7
输出 #1复制
3
2

解题报告：这道题由于数据量小可以暴力做，但是为了训练，学点线段树的懒标记也好，在学长的帮助我才完成了这道题，维护三个信息，一个是种子数量，一个是树的数量，一个是懒标记。要注意的是下放懒标记的时候，他的儿子节点可能也会有懒标记，当他的懒标记是cut的时候要让它也要pushdown，所以要多开两倍空间。同时开一个cnt来记录删去的树种子值，他不是状态量是全局量所以可以写外面。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=10010;
struct node{
	int l;
	int r;
	int sum;
	int seed;
	int lazy;
}tr[N*8];
int cut;
void pushup(int u)
{
	tr[u].seed=tr[u<<1].seed+tr[u<<1|1].seed;
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int	u)
{
	if(tr[u].lazy)
	{
	if(tr[u].lazy==1)
	{
		tr[u<<1].seed=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
		tr[u<<1|1].seed=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
		if(tr[u<<1].lazy==-1)
		pushdown(u<<1);
		if(tr[u<<1|1].lazy==-1)
		pushdown(u<<1|1);
	}
	else	if(tr[u].lazy==-1)
	{
		tr[u<<1].seed=0;
		tr[u<<1|1].seed=0;
		tr[u<<1].sum=0;
		tr[u<<1|1].sum=0;
	}
	tr[u<<1].lazy=tr[u].lazy;
	tr[u<<1|1].lazy=tr[u].lazy;
	tr[u].lazy=0;
		}
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		tr[u]={l,r,1,0,0};
		return;
	}
	else
	{
		tr[u]={l,r,0,0,0};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int l,int r,int d)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		if(d==1)
		{
			tr[u].seed=tr[u].r-tr[u].l+1-tr[u].sum;	
			if(tr[u].lazy==-1) pushdown(u);
			tr[u].lazy=1;	
		}
		else
		{
			cut+=tr[u].seed;
			tr[u].seed=0;
			tr[u].sum=0;
		//	if(tr[u].lazy==1)
		//	pushdown(u);
			tr[u].lazy=-1; 
		}
		return ;
	}
	else
	{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)	modify(u<<1,l,r,d);
		if(r>mid)	modify(u<<1|1,l,r,d);
		pushup(u);
	}
}
int main()
{
	int n;
	int m;
	cin>>n>>m;
	build(1,0,n);
	while(m--)
	{
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1)
		{
			modify(1,l,r,1);
		}
		else
		{
			modify(1,l,r,-1);
		}
	}
	cout<<tr[1].seed<<endl;
	cout<<cut<<endl;
    return 0;
}