一.题目链接：

POJ-2528

二.题目大意：

墙的长度 ≤ 1e7，海报个数 ≤ 1e4.

按时间顺序，给一堵墙贴海报.

每次给出海报贴到墙上的区间，求最后能看到几张海报.

三.分析：

典型的线段树求区间问题

可是墙太长，直接求会 TLE.

观察到 n 只有 1e4，那么最多会有 2e4 个点

所以先进行离散化处理，再用线段树更改区间.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)1e4;

struct node1
{
    int l;
    int r;
    int w;
} tree[2 * M * 4 + 5];

struct node2
{
    int point;
    int pos;
} s[M * 2 + 5];

set <int> st;
int inter[M + 5][2];

bool cmp(node2 a, node2 b)
{
    return a.point < b.point;
}

void lisan(int loc, int cnt)
{
    if(s[loc].pos < 0)
        inter[-s[loc].pos - 1][0] = cnt;
    else
        inter[s[loc].pos - 1][1] = cnt;
}

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

void push(int k)
{
    tree[k * 2].w = tree[k * 2 + 1].w = tree[k].w;
    tree[k].w = 0;
}

void interver(int k, int l, int r, int a, int b, int c)
{
    if(tree[k].l >= a && tree[k].r <= b)
    {
        tree[k].w = c;
        return;
    }
    if(tree[k].w)
        push(k);
    int mid = (tree[k].l + tree[k].r) / 2;
    if(a <= mid)
        interver(k * 2, l, mid, a, b, c);
    if(mid < b)
        interver(k * 2 + 1, mid + 1, r, a, b, c);
}

void query(int k, int l, int r)
{
    if(tree[k].w)
    {
        st.insert(tree[k].w);
        return;
    }
    if(tree[k].w)
        push(k);
    int mid = (tree[k].l + tree[k].r) / 2;
    query(k * 2, l, mid);
    query(k * 2 + 1, mid + 1, r);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        st.clear();
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d", &s[i * 2].point, &s[i * 2 + 1].point);
            s[i * 2].pos = -(i + 1);///记录时间位置
            s[i *2 + 1].pos = i + 1;
        }
        sort(s, s + 2 * n, cmp);///按端点排序
        int cnt = 1;
        int tmp = s[0].point;
        for(int i = 0; i < 2 * n; ++i)
        {
            if(tmp != s[i].point)
            {
                tmp = s[i].point;
                cnt++;
            }
            lisan(i, cnt);///重新给端点编号
        }
        build(1, 1, cnt);
        for(int i = 0; i < n; ++i)
            interver(1, 1, cnt, inter[i][0], inter[i][1], i + 1);
        query(1, 1, cnt);
        printf("%d\n", st.size());
    }
    return 0;
}