「CODEVS1299」切水果
题目描述 Description
简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量
输入描述 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<=10^4
60%的数据满足N，M<=10^6
100% 的数据满足1<=L<=R<=N<=2*10^6，1<=M<=2*10^6
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<iostream> #include<cstdio> using namespace std; int n,m; struct data{ int l,r,sum; bool tag; }tr[8500001]; void build(int k,int s,int t) { tr[k].l=s;tr[k].r=t; if(s==t){tr[k].sum=1;return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } void del(int k,int x,int y) { if(tr[k].tag){tr[k].sum=0;tr[k<<1].tag=tr[k<<1|1].tag=1;return;} int l=tr[k].l,r=tr[k].r; if(x==l&&y==r){tr[k].sum=0;tr[k].tag=1;return;} int mid=(l+r)>>1; if(mid>=y)del(k<<1,x,y); else if(mid<x)del(k<<1|1,x,y); else {del(k<<1,x,mid);del(k<<1|1,mid+1,y);} tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } int main() { scanf("%d%d",&n,&m); build(1,1,n); int x,y; while(m--) { scanf("%d%d",&x,&y); del(1,x,y);printf("%d\n",tr[1].sum); } return 0; } |
Subscribe
计数器 9787464
OI 课件=>
OI 课件=>