时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一条数轴上有N个点,分别是1~N。一开始所有的点都被染成黑色。接着 我们进行M次操作,第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后 剩余黑色点的个数。
输入描述 Input Description
输入一行为N和M。下面M行每行两个数Li、Ri
输出描述 Output Description
输出M行,为每次操作后剩余黑色点的个数。
样例输入 Sample Input
10 3 3 3 5 7 2 8
样例输出 Sample Output
9 6 3
数据范围及提示 Data Size & Hint
数据限制 对30%的数据有1<=N<=2000,1<=M<=2000 对100%数据有1<=Li<=Ri<=N<=200000,1<=M<=200000
裸的线段树。
一定要记住如果整个区间都是0了一定要return
啊啊啊啊啊啊啊啊啊啊
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=200001;
7 void read(int & n)
8 {
9 char c='+';int x=0;int flag=0;
10 while(c<'0'||c>'9')
11 { if(c=='-') flag=1; c=getchar(); }
12 while(c>='0'&&c<='9')
13 { x=x*10+(c-48); c=getchar();}
14 flag==1?n=-x:n=x;
15 }
16 int n,m;
17 struct node
18 {
19 int l,r,w;
20 }tree[MAXN*4];
21 void update(int k)
22 {
23 tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
24 }
25 void build_tree(int ll,int rr,int k)
26 {
27
28 tree[k].l=ll;tree[k].r=rr;
29 if(ll==rr)
30 {
31 tree[k].w=1;
32 return ;
33 }
34 int mid=(ll+rr)>>1;
35 build_tree(ll,mid,k<<1);
36 build_tree(mid+1,rr,k<<1|1);
37 update(k);
38 }
39 void interval_change(int k,int ql,int qr)
40 {
41 if(tree[k].w==0)
42 return ;
43 if(ql<=tree[k].l&&qr>=tree[k].r)
44 {
45 tree[k].w=0;
46 return ;
47 }
48 int mid=(tree[k].l+tree[k].r)>>1;
49 if(ql<=mid)
50 interval_change(k<<1,ql,qr);
51 if(qr>mid)
52 interval_change(k<<1|1,ql,qr);
53 update(k);
54 }
55 int main()
56 {
57 read(n);read(m);
58 build_tree(1,n,1);
59 for(int i=1;i<=m;i++)
60 {
61 int x,y;
62 read(x);read(y);
63 interval_change(1,x,y);
64 printf("%d\n",tree[1].w);
65 }
66 return 0;
67 }