Mayor's posters 線段樹+離散化+桶

簡單說下題意：就是在一個寬1e7牆上面貼n張海報，第i張海報的起點是li，終點是ri，顯然海報會覆寫别的海報。問依次貼完n張海報之後最後能看見幾張海報。

題目要求最後能看見多少張海報，那麼我們将每張海報都分别标上序号1，2，3…n。然後線段樹修改區間，最後看線段樹最底層有多少種數字即可。

需要注意的幾點：

• 海報終點可能到1e7，我們要做的區間修改以及最後桶排計數工作量就會非常大，但是隻有20000張海報，我們可以進行離散化，這樣最多40000個資料。

• 由于這裡的區間修改是

  完全覆寫原區間

  ，是以我們更新區間的時候隻需更新懶标即可。最後更新完所有區間之後，周遊整棵樹，下傳所有懶标，再數最底層的不同數字有多少即可。

AC代碼：

//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define MAX 100010
#define mod 1000000007
struct node
{
    int l, r, val, k, lazy;
} tr[MAX * 4];
struct node2
{
    int l, r;
} p1[MAX];
int p2[MAX * 2];
int ct2 = 1, ct3 = 1;
void build(int k, int l, int r)
{
    tr[k].l = l;
    tr[k].r = r;
    if (l == r)
    {
        tr[k].val = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(k * 2, l, mid);
    build(k * 2 + 1, mid + 1, r);
}
void pushdown(int k)
{
    if (tr[k].l == tr[k].r)
    {
        tr[k].lazy = 0;
        return;
    }
    if (tr[k].lazy)
    {
        tr[k * 2].lazy = tr[k].lazy;
        tr[k * 2 + 1].lazy = tr[k].lazy;
        tr[k].lazy = 0;
        return;
    }
}
void change(int k, int l, int r, int y)
{
    if (tr[k].l == l && tr[k].r == r)
    {
        tr[k].lazy = y;
        return;
    }
    pushdown(k);
    int mid = (tr[k].l + tr[k].r) >> 1;
    if (r <= mid)
        change(k * 2, l, r, y);
    else if (l > mid)
        change(k * 2 + 1, l, r, y);
    else
    {
        change(k * 2, l, mid, y);
        change(k * 2 + 1, mid + 1, r, y);
    }
}
int tong[MAX * 2];
void updateans(int k)
{
    if (tr[k].lazy)
    {
        tr[k].val = tr[k].lazy;
        tr[k * 2].lazy = tr[k].lazy;
        tr[k * 2 + 1].lazy = tr[k].lazy;
    }
    if (tr[k].l == tr[k].r)
    {
        tong[tr[k].val] = 1;
        return;
    }
    updateans(k * 2);
    updateans(k * 2 + 1);
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ct2 = 1, ct3 = 1;
        fill(tong, tong + MAX, 0);
        fill(p2, p2 + MAX, 0);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &p1[i].l, &p1[i].r);
            p2[ct2++] = p1[i].l;
            p2[ct2++] = p1[i].r;
        }
        sort(p2 + 1, p2 + ct2);
        int new_end = unique(p2 + 1, p2 + ct2) - p2;
        int maxx = 0;
        for (int i = 1; i <= n; i++)
        {
            p1[i].l = lower_bound(p2 + 1, p2 + new_end, p1[i].l) - p2;
            p1[i].r = lower_bound(p2 + 1, p2 + new_end, p1[i].r) - p2;
            maxx = max(maxx, max(p1[i].l, p1[i].r));
        }
        build(1, 1, maxx);
        int cot = 1;
        for (int i = 1; i <= n; i++)
            change(1, p1[i].l, p1[i].r, cot++);
        updateans(1);
        int anss = 0;
        for (int i = 1; i <= maxx; i++)
            if (tong[i])
                anss++;
        cout << anss << endl;
    }
    return 0;
}