POJ

题意：

给定一个高度为1，长度为$1e7$的黑板报，现在要做黑板报上依次贴广告，问最后能够看到多少张广告（漏出来一点都算看到）。

思路：

一开始一直正向的做，感觉特别的麻烦，于是可以倒着想，，从最后一张开始贴，若当前要贴的广告的区间已经被覆盖了，则这个广告对答案就没有贡献，否则就能看见。

当然离散化方法有很多种，这里只用了比较节约时间的一种。

 1 /*
 2 *  Author: windystreet
 3 *  Date  : 2018-08-14 15:46:02
 4 *  Motto : Think twice, code once.
 5 */
 6 #include<stdio.h>
 7 #include<algorithm>
 8 #include<string.h>
 9 #include<stdlib.h>
10 
11 using namespace std;
12 
13 #define X first
14 #define Y second
15 #define eps  1e-5
16 #define gcd __gcd
17 #define pb push_back
18 #define PI acos(-1.0)
19 #define lowbit(x) (x)&(-x)
20 #define bug printf("!!!!!
");
21 #define mem(x,y) memset(x,y,sizeof(x))
22 
23 typedef long long LL;
24 typedef long double LD;
25 typedef pair<int,int> pii;
26 typedef unsigned long long uLL;
27 
28 const int maxn = 1e4+7;
29 const int INF  = 1<<30;
30 const int mod  = 1e9+7;
31 
32 struct Tree
33 {
34     int l,r,v;           // v 是否被覆盖
35 }tree[maxn<<3];
36 int ml[maxn],mr[maxn],mm[maxn*2];
37 int cut[10000009];
38 void build(int rt ,int l,int r){
39     tree[rt].l = l;tree[rt].r = r;tree[rt].v = 0;
40     if(l==r)return;
41     int mid = (l+r)>>1;
42     build(rt<<1,l,mid);
43     build(rt<<1|1,mid+1,r);
44 }
45 
46 int update(int rt,int L,int R,int l,int r){
47     if(tree[rt].v == 1)return 0;                           // 如果当前区间被覆盖了，那么对答案就没有贡献
48     if(l<=L&&R<=r){
49         tree[rt].v = 1;return 1;
50     }
51     int res = 0;
52     int mid = (L + R) >>1;
53     if(l<=mid) res|=update(rt<<1,L,mid,l,r);
54     if(r>mid)  res|=update(rt<<1|1,mid+1,R,l,r);
55     if(tree[rt<<1].v&&tree[rt<<1|1].v)tree[rt].v = 1;      // 如果当前节点的左右节点都被覆盖了，则更新
56     return res;                                            // 若其中有一个区间没有被覆盖，则对答案有贡献
57 }
58 
59 void solve(){
60     int n,ans = 0,k=0;
61     scanf("%d",&n);
62 
63     for(int i=1;i<=n;i++)scanf("%d%d",&ml[i],&mr[i]);
64     for(int i=1;i<=n;i++){
65         mm[++k] = ml[i];mm[++k] = mr[i];
66     }
67     sort(mm+1,mm+1+k);
68     k = unique(mm+1,mm+1+k)-mm-1;                         // 去重
69     for(int i=1;i<=k;i++)cut[mm[i]] = i;                  // 离散化
70     build(1,1,k);
71     for(int i=n;i>=1;i--){                                // 倒着推
72         ans += update(1,1,k,cut[ml[i]],cut[mr[i]]);
73     }
74     printf("%d
",ans);
75     
76     return;
77 }
78 
79 int main()
80 {
81 //    freopen("F:\in.txt","r",stdin);
82 //    freopen("out.txt","w",stdout);
83 //    ios::sync_with_stdio(false);
84     int t = 1;
85     scanf("%d",&t);
86     while(t--){
87     //    printf("Case %d: ",cas++);
88         solve();
89     }
90     return 0;
91 }