Description

Input

Output

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample Input

1
5
1 4
2 6
8 10
3 4
7 10

Sample Output

4

Source

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeofa());
#define in1(a) scanf("%d" ,&a);
#define in2(a, b) scanf("%d%d", &a, &b);
#define out1(n) printf("%d\n", n);
using namespace std;
typedef pair<long long, int> par;
const int mod = 1e9+7;
const int INF = 1e9+7;
const int N = 1000010;
const double pi = 3.1415926;

int T, n;
int x[10010], y[10010], a[40010], b[40010], vis[40010];
char str[10];

struct node
{
    int l;
    int r;
    int lazy;
    int num;
}e[40010*4];

void push(int k)
{
    if(e[k].lazy) {
        e[2*k].num = e[k].lazy;
        e[2*k+1].num  = e[k].lazy;
        e[2*k].lazy = e[k].lazy;
        e[2*k+1].lazy = e[k].lazy;
        e[k].lazy = 0;
    }
}

void build(int l, int r, int k)
{
    e[k].l = l;
    e[k].r = r;
    e[k].lazy = 0;
    if(l == r) {
        e[k].num = 0;
        return;
    }
    int mid = (l+r)/2;
    build(l, mid, 2*k);
    build(mid+1, r, 2*k+1);
}

void updata(int l ,int r, int add, int k)
{
    if(l == e[k].l && r == e[k].r) {
        e[k].num = add;
        e[k].lazy = add;
        return;
    }
    push(k);
    int mid = (e[k].l+e[k].r)/2;
    if(r <= mid) updata(l, r, add, 2*k);
    else if(l >= mid+1) updata(l, r, add, 2*k+1);
    else {
        updata(l ,mid, add, 2*k);
        updata(mid+1, r, add, 2*k+1);
    }
}

int quary(int l, int r, int k)
{
    if(e[k].l == l && e[k].r == r) {
        return e[k].num;
    }
    push(k);
    int mid = (e[k].l + e[k].r)/2;
    if(r <= mid) return quary(l ,r, 2*k);
    else if(l+1 >= mid) return quary(l, r, 2*k+1);
}

int main()
{
    in1(T);
    while(T --) {
        in1(n);
        int k = 0, ans = 0;
        mem0(vis);
        for(int i = 0; i < n; i ++) {
            in2(x[i], y[i]);
            a[k ++] = x[i];
            a[k ++] = y[i];
        }
        sort(a, a+k);
        int s = 1;
        b[0] = a[0];
        //离散化坐标
        for(int i = 1; i < k; i ++) {
            if(a[i] != a[i-1]) {
                b[s ++] = a[i];
                if(a[i] - a[i-1] >= 2)
                    b[s ++] = a[i-1]+1;
            }
        }
        sort(b, b+s);
        build(1, s, 1);
        k = 1;
        for(int i = 0; i < n; i ++) {
            int l = upper_bound(b, b+s, x[i]) - b; //查找角标(也就是新的区间跨度)
            int r = upper_bound(b, b+s, y[i]) - b;
            updata(l, r, k++, 1);
        }
        for(int i = 1; i <= s; i ++) { //查找广告种类
            if(!vis[quary(i, i, 1)] && quary(i, i, 1)) {
                ans ++;
                vis[quary(i, i, 1)] = 1;
            }
        }
        out1(ans);
    }
    return 0;
}