poj 2528 Mayor's posters

Description Input Output Sample Input Sample Output

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 111111;
int li[maxn], ri[maxn], x[maxn*3], col[maxn<<4], cnt;
bool hash[maxn];
void PushDown(int rt){
  if (col[rt] != -1){
    col[rt<<1] = col[rt<<1|1] = col[rt];
    col[rt] = -1;
  }
}
void update(int L,int R, int c, int l, int r, int rt){
  if (L <= l && R >= r){col[rt] = c; return;}
  PushDown(rt);
  int m = (l + r) >> 1; 
  if (L <= m) update(L, R, c, lson); if (R > m) update(L, R, c, rson);
}
void query(int l, int r, int rt){
  if (col[rt] != -1){
    if (!hash[col[rt]]) cnt++;
    hash[col[rt]] = true; return;
  }
  if (l == r) return; 
  int m = (l + r) >> 1;
  query(lson); query(rson);
}
int bin(int key, int n, int a[]){
  int l = 0, r = n - 1;
  while (l <= r){
    int m = (l + r) >> 1;
    if (a[m] == key) return m;
    if (a[m] < key) l = m + 1; else r = m - 1;
  }
  return -1;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2528.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  while (t--){
    int n; scanf("%d",&n); int k = 0;
    for (int i = 0; i < n; ++i){
      scanf("%d%d", li+i, ri+i); x[k++] = li[i]; x[k++] = ri[i];
    }
    sort(x, x + k); 
    int m = 1;
    for (int i = 1; i < k; ++i){
      if (x[i] != x[i-1]) x[m++] = x[i];
    }
    for (int i = m - 1; i > 0; --i){
      if (x[i] != x[i-1] + 1) x[m++] = x[i-1] + 1;
    }
    sort(x, x + m);
    memset(col, -1, sizeof(col));
    for (int i = 0; i < n; ++i){
      int l = bin(li[i], m, x);
      int r = bin(ri[i], m, x);
      update(l, r, i, 0, m, 1);
    }
    cnt = 0; memset(hash, false, sizeof(hash));
    query(0, m, 1); printf("%d\n", cnt);
  }
  return 0;
}

膜拜一下NotOnlySuccess神犇……