POJ - 2528 Mayor's posters（區間覆寫，離散化）

​​POJ - 2528 Mayor’s posters​​

題目

給出 n 段區間，區間按給出的順序會覆寫掉前面的區間，問最後能看到多少不同的區間。

分析

這題隻需要用到懶惰标記即可，線段樹沒有維護什麼東西，有懶惰标記 c 代表這個區間被 c 覆寫了。

隻不過要用到離散化，題目給出的資料我們隻在乎他們的相對大小，相對大小才會影響到區間覆寫的結果 。

通常離散化的時侯是離散到連續的區間，但是有問題，比如資料：

1 - 10

1 - 4

6 - 10

普通的離散為

1 -> 1

4 -> 2

6 -> 3

10 -> 4

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 9999991;
const int N = 2e5 + 10;

int t, n, cnt, m, ans;
int a[N], b[N];         //左右區間
int tmp[N];             //離散化數組
int tr[N << 2];         // 線段樹什麼也不維護，隻用到懶惰标記
set<int> s;             // 映射關系 

void pushdown(int rt){
    if(tr[rt] != -1){
        tr[rt << 1] = tr[rt << 1 | 1] = tr[rt];
        tr[rt] = -1;
    }
}

void update(int l, int r, int rt, int L, int R, int c){
    if(L <= l && r <= R){
        tr[rt] = c;
        return;
    }
    pushdown(rt);
    int m = l + r >> 1;
    if(L <= m)
        update(lson, L, R, c);
    if(m < R)
        update(rson, L, R, c);
}

void query(int l, int r, int rt){
    if(tr[rt] != -1){
        if(!s.count(tr[rt])){
            ans++;
            s.insert(tr[rt]);
        }
        return;
    }
    if(l == r)
        return;
    int m = l + r >> 1;
    query(lson);
    query(rson);
}

int bi(int key, int n, int *tmp){
    int l = 0, r = n - 1;
    while(l <= r){
        int m = l + r >> 1;
        if(tmp[m] == key){
            return m;
        }
        if(tmp[m] < key){
            l = m + 1;
        }else{
            r = m - 1;
        }
    }
    return -1;
}


int main()
{
    cin >> t;
    while(t--){
        cnt = 0;
        memset(tr, -1, sizeof(tr));     //開始都沒被染色
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d%d", &a[i], &b[i]);
            tmp[cnt++] = a[i];
            tmp[cnt++] = b[i];
        }
        sort(tmp, tmp + cnt);
        m = 1;                         
        for(int i = 1; i < cnt; i++){   //去重
            if(tmp[i] != tmp[i-1]){
                tmp[m++] = tmp[i];
            }
        }
        for(int i = m-1; i > 0; i--){
            if(tmp[i] != tmp[i-1]+1){
                tmp[m++] = tmp[i - 1] + 1;
            }
        }
        sort(tmp, tmp + m);
        // for(int i = 0; i < m; i++){
        //     cout << tmp[i] << endl;
        // }
        for (int i = 0; i < n; i++){
            int l = bi(a[i], m, tmp);
            int r = bi(b[i], m, tmp);
            // printf("%d %d\n", l, r);
            update(0, m, 1, l, r, i);
        }
        ans = 0;
        s.clear();
        query(0, m, 1);
        printf("%d\n", ans);
    }
    return 0;
}