题目描述 Description
简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量
数据已重新装配，不会出现OLE错误
时限和数据范围适当修改，避免数据包过大而浪费空间资源
输入描述 Input Description
第1行共包括2个正整数，分别为N,M。
接下来m行每行两个正整数L,R
输出描述 Output Description
一共输出M行,每行输出切完之后剩下水果数量
样例输入 Sample Input
10 3
3 5
2 8
1 5
样例输出 Sample Output
7
3
2
数据范围及提示 Data Size & Hint
30%的数据满足N，M<=5,000
60%的数据满足N，M<=100,000
100% 的数据满足1<=L<=R<=N<=500,000，1<=M<=500,000
题意：n个水果排成一排 m次查询 每次删除[L,R]区间内的水果 并输出剩下的水果的数量
题解：线段树处理 题目数据有问题 存在L<0 R>N的数据
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<queue>
#define ll __int64
using namespace std;
struct node
{
int l,r;
int w;
int add;
}tree[];
void buildtree(int root,int left,int right)
{
tree[root].l=left;
tree[root].r=right;
tree[root].add=;
if(left==right)
{
tree[root].w=;
return ;
}
int mid=(left+right)>>;
buildtree(root<<,left,mid);
buildtree(root<<|,mid+,right);
tree[root].w=tree[root<<].w+tree[root<<|].w;
}
void pushdown(int root)
{
if(tree[root].add==) return;
tree[root<<].add=;
tree[root<<|].add=;
tree[root].add=;
tree[root<<].w=;
tree[root<<|].w=;
}
void updata(int root,int left,int right,int c)
{
if(tree[root].l==left&&tree[root].r==right)
{
tree[root].add=c;
tree[root].w=;
return ;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
{
updata(root<<,left,right,c);
}
else
{
if(left>mid)
updata(root<<|,left,right,c);
else
{
updata(root<<,left,mid,c);
updata(root<<|,mid+,right,c);
}
}
tree[root].w=tree[root<<].w+tree[root<<|].w;
}
int query(int root ,int left,int right)
{
if(tree[root].l==left&&tree[root].r==right)
{
return tree[root].w;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(mid<=right)
return query(root<<,left,right);
else
{
if(left>mid)
return query(root<<|,left,right);
else
return query(root<<,left,mid)+query(root<<|,mid+,right);
}
}
int n,m;
int le,ri;
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
buildtree(,,n);
for(int i=;i<=m;i++)
{
scanf("%d %d",&le,&ri);
updata(,max(,le),min(n,ri),);
printf("%d\n",query(,,n));
}
}
return ;
}