主席树-----动态开点，不hash

​​POJ - 2104 ​​

第k大

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


const int maxn = 100000 + 20;

struct Node {
    int L, R;
    int sum;
} seg[maxn << 5];

int T[maxn];

int tot;

int build(int L, int R) {
    int root = ++tot;
    seg[root].sum = 0;
    if (L < R) {
        int mid = (L + R) >> 1;
        seg[root].L = build(L, mid);
        seg[root].R = build(mid + 1, R);
    }
    return root;
}

int upDate(int version, int L, int R, int val) {
    int root = ++tot;
    seg[root] = seg[version];
    seg[root].sum = seg[version].sum + 1;
    if (L < R) {
        int mid = (L + R) >> 1;
        if (val <= mid) seg[root].L = upDate(seg[version].L, L, mid, val);
        else seg[root].R = upDate(seg[version].R, mid + 1, R, val);
    }
    return root;
}

int query(int u, int v, int L, int R, int k) {
    if (L >= R) return L;
    int num = seg[seg[v].L].sum - seg[seg[u].L].sum;
    int mid = (L + R) >> 1;
    if (num >= k) {
        return query(seg[u].L, seg[v].L, L, mid, k);
    } else return query(seg[u].R, seg[v].R, mid + 1, R, k - num);
}

int a[maxn];
vector<int> vc;

int getID(int val) {
    return lower_bound(vc.begin(), vc.end(), val) - vc.begin() + 1;
}


const int down = -1e9, up = 1e9;

void work() {
    tot = 0;
    vc.clear();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        vc.push_back(a[i]);
    }
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
//     for (int i = 0; i < vc.size(); ++i) {
//         printf("%d ", vc[i]);
//     }
    T[0] = build(up, down);
    for (int i = 1; i <= n; ++i) {
//        int id = getID(a[i]);
        T[i] = upDate(T[i - 1], down, up, a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int L, R, val;
        scanf("%d%d%d", &L, &R, &val);
//        val = (R - L + 1) - val + 1;
        int res = query(T[L - 1], T[R], down, up, val);
        printf("%d\n", res);
    }

}

int main() {
    #ifdef local
    freopen("data.txt", "r", stdin);
    #endif // local
//    int t;
//    scanf("%d", &t);
//    while (t--) work();
    work();
    return 0;
}

View Code

区间不同元素个数

​​https://vjudge.net/problem/SPOJ-DQUERY​​

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

const int maxn = 300000 + 20;

struct Node {
    int L, R;
    int sum;
} seg[maxn << 5];
int T[maxn], now;

int build(int L, int R) {
    ++now;
    seg[now].sum = 0;
    if (L < R) {
        int mid = (L + R) >> 1;
        seg[now].L = build(L, mid);
        seg[now].R = build(mid + 1, R);
    }
    return now;
}

int upDate(int version, int L, int R, int val, int xo) {
    int root = ++now;
    seg[root] = seg[version];
    seg[root].sum = seg[version].sum + xo;
    if (L < R) {
        int mid = (L + R) >> 1;
        if (val <= mid) {
            seg[root].L = upDate(seg[version].L, L, mid, val, xo);
        } else {
            seg[root].R = upDate(seg[version].R, mid + 1, R, val, xo);
        }
    }
    return root;
}

int query(int version1, int version2, int L, int R, int be, int en) {
    if (L > R) return 0;
    if (L >= be && R <= en) {
        return seg[version2].sum - seg[version1].sum;
    }
    int ans = 0;
    int mid = (L + R) >> 1;
    if (mid >= be) ans += query(seg[version1].L, seg[version2].L, L, mid, be, en);
    if (mid + 1 <= en) ans += query(seg[version1].R, seg[version2].R, mid + 1, R, be, en);
    return ans;
}

int pre[1000000 + 2];

int up = -1e9;
int en = 1e9;

void work() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        if (pre[x]) {
            int res = upDate(T[i - 1], up, en, pre[x], -1);
            T[i] = upDate(res, up, en, i, 1);
        } else T[i] = upDate(T[i - 1], up, en, i, 1);
        pre[x] = i;
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(T[l - 1], T[r], up, en, l, r));
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
#endif // local
    work();
    return 0;
}

View Code