HDU2665（可持久化线段树板子）

1.题意有坑，实际要求第k小。

2.没学过动态开点也没学过主席树，看一下博主思路然后妄想自己实现的后果就是拿命去调bug。

const int maxn = 1e5 + 5;

int test, n, m, tot;

int a[maxn], b[maxn];

namespace Seg {

    #define ls(p) t[p].l

    #define rs(p) t[p].r

    int sz, root[maxn];

    struct Node {

        int sum, l, r;

    }t[maxn * 20];

    int Build(int l, int r) {

        int p = ++sz;

        if (l == r) {

            t[p].sum = t[p].l = t[p].r = 0;

            return sz;

        }

        int mid = (l + r) >> 1;

        t[p].l = Build(l, mid);

        t[p].r = Build(mid + 1, r);

        t[p].sum = t[ls(p)].sum + t[rs(p)].sum;

        return p;

    }

    int Update(int l, int r, int last, int k) {

        int p = ++sz;

        t[p].l = t[last].l, t[p].r = t[last].r, t[p].sum = 0;

        if (l == r) {

            t[p].sum = t[last].sum + 1;

            return p;

        }

        int mid = (l + r) >> 1;

        if (k <= mid)   t[p].l = Update(l, mid, ls(last), k);

        else    t[p].r = Update(mid + 1, r, rs(last), k);

        t[p].sum = t[ls(p)].sum + t[rs(p)].sum;

        return p;

    }

    int Query(int l, int r, int last, int p, int k) {

        if (l == r) return b[l];

        int res = t[ls(p)].sum - t[ls(last)].sum;

        int mid = (l + r) >> 1;

        if (res >= k)    return Query(l, mid, ls(last), ls(p), k);

        else    return Query(mid + 1, r, rs(last), rs(p), k - res);

    }

};

int main() {

    for (read(test); test--; ) {

        read(n), read(m);

        rep(i, 1, n)    read(a[i]), b[i] = a[i];

        sort(b + 1, b + 1 + n);

        tot = unique(b + 1, b + 1 + n) - b - 1;

        rep(i, 1, n)    a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;

        Seg::sz = 0;

        Seg::root[0] = Seg::Build(1, tot);

        rep(i, 1, n)    Seg::root[i] = Seg::Update(1, tot, Seg::root[i - 1], a[i]);

        while (m--) {

            int l, r, k;

            read(l), read(r), read(k);

            writeln(Seg::Query(1, tot, Seg::root[l - 1], Seg::root[r], k));

        }

    }

    return 0;

}