HDU2528 Mayor's Posters（Dec. 20th, 2018）

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r
#define N 100005
using namespace std;
struct lune{
    int s, id;
} a[N << 1];
int t[N << 2], vis[N];
void build(int u, int l, int r){
    if(l == r) return;
    int mid = l + r >> 1;
    build(lson);
    build(rson);
}
void update(int u, int l, int r, int a, int b, int c){
    if(a <= l && r <= b){
        t[u] = c;
        return;
    }
    if(t[u]){
        t[u << 1] = t[u << 1 | 1] = t[u];
        t[u] = 0;
    }
    int mid = l + r >> 1;
    if(a <= mid)
        update(lson, a, b, c);
    if(b > mid)
        update(rson, a, b, c);
}
void query(int u, int l, int r){
    if(l == r && !t[u])
        return;
    if(t[u]){
        vis[t[u]] = 1;
        return;
    }
    if(t[u]){
        t[u << 1] = t[u << 1 | 1] = t[u];
        t[u] = 0;
    }
    int mid = l + r >> 1; 
    query(lson);
    query(rson);
}
bool ctrl(lune x, lune y){
    return x. s < y. s;
}
int main(){
    int T, n, m;
    scanf("%d", &T);
    int b[N << 1];
    while(T--){
        scanf("%d", &m);
        memset(t, 0, sizeof(t));
        memset(vis, 0, sizeof(vis));
        int dm = m << 1;
        for(int i = 1; i <= dm; i += 2){
            scanf("%d %d", &b[i], &b[i + 1]);
            a[i] = (lune){b[i], i};
            a[i + 1] = (lune){b[i + 1], i + 1};
        }
        sort(a + 1, a + dm + 1, ctrl);
        for(int i = 1; i <= dm; i++){
            b[a[i]. id] = b[a[i - 1]. id] + 1;
            if(a[i]. s == a[i - 1]. s) b[a[i]. id]--;
            n = b[a[i]. id];
        }
        build(1, 1, n);
        for(int i = 1; i <= dm; i += 2)
            update(1, 1, n, b[i], b[i + 1], i / 2 + 1);
        query(1, 1, n);
        int ans = 0;
        for(int i = 1; i <= n; i++)
            ans += vis[i];
        printf("%d\n", ans);
    }
    return 0;
}