(Relax 线段树1.2)POJ 2528 Mayor's posters(计算可见线段)

 
/* 
 * POJ_2528.cpp 
 * 
 *  Created on: 2013年11月25日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
  
#define maxn 10010  
#define Fup(i, s, t) for (int i = s; i <= t; i ++)  
  
using namespace std;  
  
bool tab[maxn];  
int l[maxn], r[maxn], x[maxn * 3], num[maxn * 3], tree[maxn * 12];  
int c, n;  
  
int binary_search(int sum) {  
    int l = 1, r = 3 * n;  
    while (r >= l) {  
        int mid = (l + r) / 2;  
        if (x[mid] <= sum)  
            l = mid + 1;  
        else  
            r = mid - 1;  
    }  
    return num[r];  
}  
  
void update(int i) {  
    if (!tree[i])  
        return;  
    tree[i + i] = tree[i + i + 1] = tree[i];  
    tree[i] = 0;  
}  
  
void change(int tl, int tr, int l, int r, int i, int co) {  
    if (tr < l || tl > r)  
        return;  
    if (tl <= l && r <= tr) {  
        tree[i] = co;  
        return;  
    }  
    update(i);  
    int mid = (l + r) / 2;  
    change(tl, tr, l, mid, i + i, co);  
    change(tl, tr, mid + 1, r, i + i + 1, co);  
}  
  
int require(int l, int r, int i) {  
    int mid = (l + r) / 2;  
    if (tree[i]) {  
        if (!tab[tree[i]]) {  
            tab[tree[i]] = 1;  
            return 1;  
        }  
        return 0;  
    }  
    if (l == r)  
        return 0;  
    return require(l, mid, i + i) + require(mid + 1, r, i + i + 1);  
}  
  
void init() {  
    scanf("%d", &n);  
    Fup(i, 1, n)  
    {  
        scanf("%d%d", l + i, r + i);  
        x[i + i + i - 2] = l[i];  
        x[i + i + i - 1] = r[i];  
        x[i + i + i] = (l[i] + r[i]) / 2;  
    }  
    sort(x + 1, x + 3 * n + 1);  
    memset(num, 0, sizeof(num));  
    Fup(i, 1, 3 * n)  
    {  
        num[i] = num[i - 1];  
        if (x[i] != x[i - 1])  
            num[i]++;  
    }  
    Fup(i, 1, n)  
    {  
        l[i] = binary_search(l[i]);  
        r[i] = binary_search(r[i]);  
    }  
}  
  
void solve(){  
    memset(tree,0,sizeof(tree));  
    memset(tab,0,sizeof(tab));  
  
    int i;  
    for(i = 1 ; i <= n ; ++i){  
        change(l[i],r[i],1,3*n,1,i);  
    }  
  
    int ans = require(1,3*n,1);  
  
    printf("%d\n",ans);  
}  
  
  
int main(){  
    scanf("%d",&c);  
    while(c--){  
        init();  
        solve();  
    }  
  
    return 0;  
}