hiho 學習日記：hiho一下第二十一周 （離散化）

http://hihocoder.com/contest/hiho21/problem/1

主要是線段樹離散化後節點表示的意義不同

AC代碼：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
#define LL long long

struct Edge{
    int l, r;
}edge[maxn];
int num[maxn << 1];

struct Tree{
    int l, r, w, lazy;
}tree[maxn << 1];

map<int, int> hm;


void build(int k, int ll, int rr) {
    tree[k].l = ll; tree[k].r = rr;
    tree[k].w = tree[k].lazy = 0;
    if(ll + 1 == rr) return ;
    int mm = (ll + rr) >> 1;
    build(k << 1, ll, mm);
    build(k << 1 | 1, mm, rr);
}

void pushDown(int k) {
    if(tree[k].w) {
        tree[k << 1].w = tree[k << 1 | 1].w = tree[k].w;
        tree[k].w = 0;
    }
}


void update(int k, int L, int R, int value) {
    if(tree[k].l >= L && tree[k].r <= R) {
        tree[k].w = value;
        return ;
    }
    if(tree[k].l == tree[k].r - 1) return ;
    pushDown(k);
    int mm = (tree[k].l + tree[k].r) >> 1;
    if(mm >= L) update(k << 1, L, R, value);
    if(mm < R) update(k << 1 | 1, L, R, value);
}

set<int> st;

void query(int k, int L, int R) {
    if(tree[k].l >= L && tree[k].r <= R) {
        if(tree[k].w) {
            st.insert(tree[k].w);
            return ;
        }
    }
    if(tree[k].l == tree[k].r - 1) return ;
    pushDown(k);
    int mm = (tree[k].l + tree[k].r) >> 1;
    if(mm >= L) query(k << 1, L, R);
    if(mm < R) query(k << 1 | 1, L, R);
}

int main()
{
    int n, L;
    st.clear();
    scanf("%d %d", &n, &L);
    int tx = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d", &edge[i].l, &edge[i].r);
        num[++tx] = edge[i].l;
        num[++tx] = edge[i].r;
    }
    sort(num + 1, num + 1 + tx);
    int len = unique(num + 1, num + 1 + tx) - num - 1;
    build(1, 1, len);
    for (int i = 1; i <= len; i ++)
        hm[num[i]] = i;
    for (int i = 1; i <= n; i ++) {
        update(1, hm[edge[i].l], hm[edge[i].r], i);
    }
    query(1, 1, len);
    cout << st.size() << endl;
    return 0;
}