hdu5412(动态区间第k大）

CRB and Queries

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 231    Accepted Submission(s): 41

Problem Description

There are N boys in CodeLand.
Boy i has his coding skill Ai.
CRB wants to know who has the suitable coding skill.
So you should treat the following two types of queries.
Query 1: 1 l v
The coding skill of Boy l has changed to v.
Query 2: 2 l r k
This is a report query which asks the k-th smallest value of coding skill between Boy l and Boy r(both inclusive).

Input

There are multiple test cases. 
The first line contains a single integer N.
Next line contains N space separated integers A1, A2, …, AN, where Ai denotes initial coding skill of Boy i.
Next line contains a single integer Q representing the number of queries.
Next Q lines contain queries which can be any of the two types.
1 ≤ N, Q ≤ 105
1 ≤ Ai, v ≤ 109
1 ≤ l ≤ r ≤ N
1 ≤ k ≤ r – l + 1

Output

For each query of type 2, output a single integer corresponding to the answer in a single line.

Sample Input

5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2

Sample Output

3
4

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

//动态空间第k大
#include <algorithm>
#include <cstdio>
#include <utility>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;

#define X first
#define Y second

const int MX = ;
const int INF = ;
struct Node;
typedef pair <Node*, Node*> Pair;
Node *null;

struct Node {
    int val, size;
    Node *left, *right;

    Node (int val, int size, Node *left, Node *right) :
        val(val), size(size), left(left), right(right) {}

    Node *Update() {
        size = left->size +  + right->size;
        return this;
    }

    int askLess(const int &x) {
        if (this == null) return ;
        if (val < x) return left->size +  + right->askLess(x);
        else return left->askLess(x);
    }
    Pair Split(int n, int type) {
        if (this == null)
            return make_pair(null, null);

        if (type ==  && val == n) {
            return make_pair(left, right);
        }

        if (!(val < n)) {
            Pair ret = left->Split(n, type);
            left = ret.Y;
            return make_pair(ret.X, this->Update());
        }

        Pair ret = right->Split(n, type);
        right = ret.X;
        return make_pair(this->Update(), ret.Y);
    }
};

struct BST {
    Node *root;

    inline int ran() {
        static int x = ;
        x += (x << ) + ;
        return x & ;
    }
    Node *Merge(Node *a, Node *b) {
        if (a == null) return b;
        if (b == null) return a;

        if (ran() % (a->size + b->size) < a->size) {
            a->right = Merge(a->right, b);
            return a->Update();
        }

        b->left = Merge(a, b->left);
        return b->Update();
    }

    void add(int b) {
        Pair ret = root->Split(b, );
        root = Merge(ret.X, Merge(new Node(b, , null, null), ret.Y));
    }
    void del(int b) {
        Pair ret = root->Split(b, );
        root = Merge(ret.X, ret.Y);
    }
    int getLess(int b) {
        return root->askLess(b);
    }

} tr[MX];

struct Query {
    int t, l, r, k;

    void in() {
        scanf("%d", &t);
        if (t == ) scanf("%d%d", &l, &k);
        else scanf("%d%d%d", &l, &r, &k);
    }

} q[MX];

int a[MX];
int p[MX], pn;
int L;

void add(int p, int v) {
    for (p++; p <= pn; p += p & -p) {
        tr[p].add(v);
    }
}
void del(int p, int v) {
    for (p++; p <= pn; p += p & -p) {
        tr[p].del(v);
    }
}

int calc(int l, int r, int k) {
    int cur = ;
    for (int i = L; i; i /= ) {
        int u = cur + i;
        if (u > pn) continue;

        int cnt = tr[u].getLess(r + ) - tr[u].getLess(l);
        if (cnt >= k) continue;
        cur = u, k -= cnt;
    }
    return cur + ;
}

int main() {
    int n, Q;
    int i;
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(scanf("%d", &n)!=EOF){

    for (i = ; i <= n; i++) {
        scanf("%d", a + i);
        p[pn++] = a[i];
    }

    scanf("%d", &Q);
    for (i = ; i <= Q; i++) {
        q[i].in();
        if (q[i].t == ) p[pn++] = q[i].k;
    }

    sort(p, p + pn);
    pn = unique(p, p + pn) - p;
    for (L = ; L <= pn; L *= );
    L /= ;

    null = new Node(, , NULL, NULL);
    for (i = ; i <= pn; i++)
        tr[i].root = null;

    for (i = ; i <= n; i++) {
        a[i] = lower_bound(p, p + pn, a[i]) - p;
        add(a[i], i);
    }

    for (i = ; i <= Q; i++)
        if (q[i].t == ) q[i].k = lower_bound(p, p + pn, q[i].k) - p;

    for (i = ; i <= Q; i++) {
        if (q[i].t == ) {
            int u = q[i].l;
            del(a[u], u);
            a[u] = q[i].k;
            add(a[u], u);

        } else {
            int u = calc(q[i].l, q[i].r, q[i].k);
            printf("%d\n", p[u - ]);
        }
    }
}
    return ;
}