【codevs1191】数轴染色
题目描述 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
<:SECTION id=statistics>
题解
只要tr【1】.v的结果
代码
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <ctime> 5 #include <iostream> 6 #include <algorithm> 7 #include <set> 8 #include <vector> 9 #include <queue> 10 #include <typeinfo> 11 #include <map> 12 #include <stack> 13 typedef long long ll; 14 using namespace std; 15 inline ll read() 16 { 17 ll x=0,f=1; 18 char ch=getchar(); 19 while(ch<'0'||ch>'9') 20 { 21 if(ch=='-')f=-1; 22 ch=getchar(); 23 } 24 while(ch>='0'&&ch<='9') 25 { 26 x=x*10+ch-'0'; 27 ch=getchar(); 28 } 29 return x*f; 30 } 31 //************************************************************************************** 32 int ans,hash[200005]; 33 struct ss 34 { 35 int l,r,v; 36 }tr[200000*5]; 37 int n,m; 38 void build(int k,int s,int t) 39 { 40 tr[k].l=s; 41 tr[k].r=t; 42 if(s==t){ 43 tr[k].v=1; 44 return; 45 } 46 int mid=(s+t)>>1; 47 build(k<<1,s,mid); 48 build(k<<1|1,mid+1,t); 49 tr[k].v=tr[k<<1].v+tr[k<<1|1].v; 50 } 51 void update(int k,int s,int t) 52 { 53 if(tr[k].v==0)return; 54 if(s==tr[k].l&&t==tr[k].r) 55 { 56 tr[k].v=0; 57 return ; 58 } 59 int mid=(tr[k].l+tr[k].r)>>1; 60 if(t<=mid) update(k<<1,s,t); 61 else if(s>mid)update(k<<1|1,s,t); 62 else { 63 update(k<<1,s,mid); 64 update(k<<1|1,mid+1,t); 65 } 66 tr[k].v=tr[k<<1].v+tr[k<<1|1].v; 67 } 68 int main() 69 { 70 71 72 scanf("%d%d",&n,&m); 73 build(1,1,n); 74 int a,b; 75 for(int i=1;i<=m;i++) 76 { 77 scanf("%d%d",&a,&b); 78 ans=0; 79 update(1,a,b); 80 printf("%d ",tr[1].v); 81 } 82 return 0; 83 }