（线段树）Mayor's posters --poj -- 2528

链接：
覆盖问题，要从后往前找，如果已经被覆盖就不能再覆盖了，否则就可以覆盖
递归呀递归什么时候我才能吃透你
代码：
  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 using namespace std;
  6 
  7 #define Lson r<<1
  8 #define Rson r<<1|1
  9 
 10 const int N = 4*1e4+5;
 11 
 12 struct Node
 13 {
 14     int L, R;
 15 }s[N<<2];
 16 
 17 struct node
 18 {
 19     int L, R;
 20     bool isCover;
 21     int Mid()
 22     {
 23         return (L+R)>>1;
 24     }
 25 }a[N<<2];
 26 
 27 int Hash[N<<2];
 28 
 29 void UpDate(int r)
 30 {
 31     if(a[r].L!=a[r].R && (a[Lson].isCover && a[Rson].isCover))
 32         a[r].isCover=true;
 33 }
 34 void BuildTree(int r, int L, int R)
 35 {
 36     a[r].L = L, a[r].R = R;
 37     a[r].isCover = false;
 38 
 39     if(L==R)
 40         return ;
 41 
 42     BuildTree(Lson, L, a[r].Mid());
 43     BuildTree(Rson, a[r].Mid()+1, R);
 44 }
 45 bool Insert(int r, int L, int R)
 46 {
 47     if(a[r].isCover) return false;
 48 
 49     if(a[r].L==L && a[r].R==R)
 50     {
 51         a[r].isCover=true;
 52         return true;
 53     }
 54 
 55     bool ans;
 56 
 57     if(R<=a[r].Mid())
 58         ans = Insert(Lson, L, R);
 59     else if(L>a[r].Mid())
 60         ans = Insert(Rson, L, R);
 61     else
 62     {
 63         bool lson = Insert(Lson, L, a[r].Mid());
 64         bool rson = Insert(Rson, a[r].Mid()+1, R);
 65 
 66         ans = lson|rson;
 67     }
 68 
 69     UpDate(r);
 70 
 71     return ans;
 72 }
 73 
 74 
 75 int main()
 76 {
 77    int t;
 78    scanf("%d", &t);
 79    while(t--)
 80    {
 81        int n, nh=0;
 82        scanf("%d", &n);
 83        memset(s, 0, sizeof(s));
 84 
 85        for(int i=1; i<=n; i++)
 86        {
 87            scanf("%d%d", &s[i].L, &s[i].R);
 88            Hash[nh++] = s[i].L, Hash[nh++]=s[i].L-1;
 89            Hash[nh++] = s[i].R, Hash[nh++]=s[i].R+1;
 90        }
 91 
 92        sort(Hash, Hash+nh);
 93        nh = unique(Hash, Hash+nh) - Hash;
 94 
 95        BuildTree(1, 1, nh);
 96 
 97        int ans=0;
 98        for(int i=n; i>0; i--)
 99        {
100            int L = lower_bound(Hash, Hash+nh, s[i].L) - Hash; // 返回是s[i].L的下标
101            int R = lower_bound(Hash, Hash+nh, s[i].R) - Hash;
102 
103            if(Insert(1, L, R))
104             ans += 1;
105        }
106 
107        printf("%d
", ans);
108    }
109    return 0;
110 }
勿忘初心