线段树 区间离散化

/*
离散化思路 和一般的离散化不同 多了个中间加点操作
具体为啥要加点
1-10 1-4 6-10
这三个区间离散化后 5 这个点会丢掉。
加点防止丢点。。。。。。。hhhh




总结  排序 去重 中间加点 再排序


*/


2528 -- Mayor's posters (poj.org)

#include
#include
#include
using namespace std;
const int maxn = 1e6 + 10;
#define ls (u<<1)
#define rs (u<<1|1)
struct node
{
    int l, r;
}e[maxn];
struct sgt
{
    int l, r;
    int co;
}tr[maxn*20];
int a[maxn], la;
int find(int x)
{
    return lower_bound(a + 1, a + 1 + la, x) - a;
}
int t, n, m;
bool vis[maxn];
void build(int u, int l, int r)
{
    tr[u].l=l;tr[u].r=r;tr[u].co=0;
    if (l == r)return;
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void pushdown(int u)
{
    if (tr[u].co > 0)
    {
        tr[ls].co = tr[rs].co = tr[u].co;

        tr[u].co = 0;
    }
}
void modify(int u, int ql, int qr,int v)
{
    if (ql <= tr[u].l && tr[u].r <= qr)
    {
        tr[u].co = v;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) / 2;
    if (ql <= mid)modify(ls, ql, qr, v);
    if (mid < qr)modify(rs, ql, qr, v);
}

void ask(int u, int& ans)
{
    if (tr[u].co != 0 && vis[tr[u].co] == false)ans++, vis[tr[u].co] = true;
    if (tr[u].l == tr[u].r)return;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) / 2;
    ask(ls, ans); ask(rs, ans);
}

void solve()
{
    la = 0;


    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d%d", &e[i].l, &e[i].r), a[++la] = e[i].l, a[++la] = e[i].r;
    sort(a + 1, a + 1 + la);//排序
    la = unique(a + 1, a + 1 + la) - a - 1;//去重
    for (int i = la; i > 1; i--)if (a[i] - a[i - 1] > 1)a[++la] = a[i-1] +1;//中间加点

    sort(a + 1, a + 1 + la);//排序


    build(1, 1, la);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++)
    {
        int l = find(e[i].l), r = find(e[i].r);

        modify(1, l, r, i);

    }
    int ans = 0;
    ask(1, ans);
    printf("%d\n", ans);
}
int main()
{
    scanf("%d", &t);
    while (t--)solve();
    return 0;
}