线段树练习题一
Time Limit:10000MS
Memory Limit:65536K
Total Submit:263
Accepted:93
Case Time Limit:1000MS

Description

桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

Sample Input

20 //桌面总宽度
4 //盒子数量
1 5
3 8
7 10
13 19

Sample Output

15

Hint

数据范围
1<=n<=100000,1<=m<=100000,保证坐标范围为[1,n].

线段树模板：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
#define LL long long
using namespace std;

const int N=1e5*4+100,M=1010;
int n,m,x,y,ans;
bool cover[N];
void add (int x,int y,int l,int r,int wz)
{
	int mid=(r+l)/2;
	if ((x==l&&y==r)||cover[wz]) {cover[wz]=1;return;}
	if (y<=mid) add (x,y,l,mid,wz*2);
	else if (x>=mid)
	{
		add (x,y,mid,r,wz*2+1);       //因为要求的是一段区间中是否有数，所以可以用"<=" 
	}
	else add (x,mid,l,mid,wz*2),add (mid,y,mid,r,wz*2+1);
}
void find (int l,int r,int wz)
{
	if (cover[wz]) {ans+=(r-l);return;}
	if (r-l<=1) return;
	int mid=(r+l)/2;
	find (l,mid,wz*2);
	find (mid,r,wz*2+1);
}

int main ()
{
	scanf ("%d %d",&m,&n);
	for (int i=1;i<=n;i++) scanf ("%d %d",&x,&y),add (x,y,1,m,1);
	find (1,m,1);
	printf ("%d",ans);
	return 0;
}