5168. [HAOI2014]贴海报【线段树】

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define N (1000000+100)
 6 using namespace std;
 7 
 8 int Segt[N<<2];
 9 int n,m,x[N],y[N],id[N],cnt,num,ans;
10 bool vis[N];
11 
12 void Pushdown(int now)
13 {
14     if (Segt[now])
15     {
16         Segt[now<<1]=Segt[now];
17         Segt[now<<1|1]=Segt[now];
18         Segt[now]=0;
19     }
20 }
21 
22 void Update(int now,int l,int r,int l1,int r1,int k)
23 {
24     if (l>r1 || r<l1) return;
25     if (l1<=l && r<=r1){Segt[now]=k; return;}
26     Pushdown(now);
27     int mid=(l+r)>>1;
28     Update(now<<1,l,mid,l1,r1,k);
29     Update(now<<1|1,mid+1,r,l1,r1,k);
30 }
31 
32 int Query(int now,int l,int r,int x)
33 {
34     if (l==r) return Segt[now];
35     Pushdown(now);
36     int mid=(l+r)>>1;
37     if (x<=mid) return Query(now<<1,l,mid,x);
38     else return Query(now<<1|1,mid+1,r,x);
39 }
40 
41 int getid(int x)
42 {
43     int l=1,r=num;
44     while (l<=r)
45     {
46         int mid=(l+r)>>1;
47         if (id[mid]==x) return mid;
48         if (x<id[mid]) r=mid-1;
49         else l=mid+1;
50     }
51 }
52 
53 int main()
54 {
55     scanf("%d%d",&n,&m);
56     for (int i=1; i<=m; ++i)
57     {
58         scanf("%d%d",&x[i],&y[i]);
59         id[++cnt]=x[i], id[++cnt]=y[i];
60         id[++cnt]=x[i]+1,id[++cnt]=y[i]+1;//离散化的时候加入一个点两边的位置 
61         id[++cnt]=x[i]-1,id[++cnt]=y[i]-1;//不这样会挂 
62     }
63     sort(id+1,id+cnt+1);
64     num=unique(id+1,id+cnt+1)-id-1;
65     for (int i=1; i<=m; ++i)
66     {
67         int xx=getid(x[i]),yy=getid(y[i]);
68         Update(1,1,num,xx,yy,i);
69     }
70     for (int i=1; i<=num; ++i)
71     {
72         int t=Query(1,1,num,i);
73         if (t && !vis[t]) ans++;
74         vis[t]=true;
75     }
76     printf("%d",ans);
77 }