POJ 2104 - K-th Number http://poj.org/problem?id=2104

gen.cc

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

const int N = 100000;
const int M = 5000;
const int MOD = 100000000;

int A[N];

int main() {
    srand(time(NULL));
    printf("%d %d\n", N, M);

    for (int i = 0; i < N; ++ i)
        A[i] = i + 1;
    for (int i = 1; i < N; ++ i) {
        int j = rand() % i;
        int k = A[i]; A[i] = A[j]; A[j] = k;
    }

    for (int i = 0; i < N - 1; ++ i)
        printf("%d ", A[i]);
    printf("%d\n", A[N - 1]);

    for (int i = 0; i < M; ++ i) {
        int x = rand() % N + 1;
        int y = rand() % N + 1;
        if (x > y) {
            int k = x; x = y; y = k;
        }
        int rank = (rand() % (y - x + 1)) + 1;
        printf("%d %d %d\n", x, y, rank);
    }
    return 0;
}

kthA.cc

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

using namespace std;

#define MAXN    100000 + 1

int N;
int key[MAXN];

#define MAXDEPTH    20
int Tree[MAXDEPTH][MAXN];


void build_interval_tree(int depth, int left, int right) {
    if (left == right) {
        Tree[depth][left] = key[left];
        return;
    }
    int mid = (left + right) >> 1;

    build_interval_tree(depth + 1, left, mid);
    build_interval_tree(depth + 1, mid + 1, right);
    int x = left, y = mid + 1;
    int ptr = left;
    while (x <= mid && y <= right) {
        if (Tree[depth + 1][x] < Tree[depth + 1][y])
            Tree[depth][ptr ++] = Tree[depth + 1][x ++];
        else
            Tree[depth][ptr ++] = Tree[depth + 1][y ++];
    }
    while (x <= mid)
        Tree[depth][ptr ++] = Tree[depth + 1][x ++];
    while (y <= right)
        Tree[depth][ptr ++] = Tree[depth + 1][y ++];
}


// [left, right]
int rank_interval_tree(int depth, int left, int right, int l, int r, int K) {
    top:
    if (left == l && right == r) {
        // find all <= K
        if (K >= Tree[depth][right]) return (right + 1) - left;
        int low = left;
        int high = right;
        while (low < high) {
            int mid = (low + high) >> 1;
            if (Tree[depth][mid] <= K)
                low = mid + 1;
            else
                high = mid;
        }
        return low - left;
    }
    int mid = (left + right) >> 1;
    if (r <= mid) {
        ++ depth; right = mid; goto top;
    }
    if (l >= mid + 1) {
        ++ depth; left = mid + 1; goto top;
    }
    return rank_interval_tree(depth + 1, left, mid, l, mid, K) + rank_interval_tree(depth + 1, mid + 1, right, mid + 1, r, K);
}

int query(int x, int y, int rank) {
    int left = 1;
    int right = N;
    while (left < right) {
        int mid = (left + right) >> 1;
        int k = rank_interval_tree(0, 1, N, x, y, Tree[0][mid]);
        if (k == rank)
            right = mid;
        else if (k < rank)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return Tree[0][left];
}

int main() {
    int M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++ i)
        scanf("%d", &key[i]);

    build_interval_tree(0, 1, N);

    while (M --) {
        int x, y, rank;
        scanf("%d %d %d", &x, &y, &rank);
        printf("%d\n", query(x, y, rank));
    }

    return 0;
}

kthB.cc

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define MAXN    100000 + 1

int N;

int key[MAXN];

#define MAXDEPTH    20
int Tree[MAXDEPTH][MAXN];
int f[MAXDEPTH][MAXN];

void build_interval_tree(int depth, int left, int right) {
    if (left == right) return;

    int mid = (left + right) >> 1;
    int median = key[mid];

    int x = left; int y = mid + 1;
    for (int i = left; i <= right; ++ i) {
        f[depth][i] = (i == left ? 0 : f[depth][i - 1]);
        if (Tree[depth][i] <= median) {
            Tree[depth + 1][x ++] = Tree[depth][i]; ++ f[depth][i];
        }
        else
            Tree[depth + 1][y ++] = Tree[depth][i];
    }
    build_interval_tree(depth + 1, left, mid);
    build_interval_tree(depth + 1, mid + 1, right);
}


int rank_interval_tree(int depth, int left, int right, int l, int r, int K) {
    top:
    
    if (l == r) return Tree[depth][l];

    int mid = (left + right) >> 1;

    int leftL1 = (left == l ? 0 : f[depth][l - 1]);
    int leftR = f[depth][r];

    if (K <= leftR - leftL1) {
        l = left + leftL1;
        r = left + leftR - 1;
        right = mid;
        ++ depth; goto top;
    }
    else {
        K = K - (leftR - leftL1);
        l = mid + 1 + (l - left) - leftL1;
        r = mid + (r - left + 1) - leftR;
        left = mid + 1;
        ++ depth; goto top;
    }
}

int main() {
    int M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++ i)
        scanf("%d", &key[i]);


    for (int i = 1; i <= N; ++ i)
        Tree[0][i] = key[i];

    sort(key + 1, key + 1 + N);

    build_interval_tree(0, 1, N);

    while (M --) {
        int x, y, rank;
        scanf("%d %d %d", &x, &y, &rank);
        printf("%d\n", rank_interval_tree(0, 1, N, x, y, rank));
    }

    return 0;
}

kthC_ptr.cc

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define MAXN    100000 + 1

int N;

int key[MAXN];

struct IntervalTree {
    IntervalTree *left_tree, *right_tree;
    int size;
};

IntervalTree pool[(MAXN) * 25];
int pool_ptr;

IntervalTree *insert(IntervalTree *node, int left, int right, int K) {
    IntervalTree *new_node = &pool[pool_ptr]; ++ pool_ptr;
    //printf("%d\n", pool_ptr);
    new_node->left_tree = node->left_tree;
    new_node->right_tree = node->right_tree;
    new_node->size = node->size + 1;
    if (left == right) return new_node;
    int mid = (left + right) >> 1;
    if (K <= mid)
        new_node->left_tree = insert(new_node->left_tree, left, mid, K);
    else
        new_node->right_tree = insert(new_node->right_tree, mid + 1, right, K);
    return new_node;
}

int query(IntervalTree *x, IntervalTree *y, int left, int right, int K) {
    top:
    if (left == right) return left;
    int mid = (left + right) >> 1;
    //printf("%x %x\n", x, y);
    int delta = y->left_tree->size - x->left_tree->size;
    //printf("delta = %d\n", delta);
    if (K <= delta) {
        x = x->left_tree; y = y->left_tree; right = mid;
        goto top;
        //return query(x->left_tree, y->left_tree, left, mid, K);
    }
    else {
        x = x->right_tree; y = y->right_tree; left = mid + 1; K = K - delta;
        goto top;
        //return query(x->right_tree, y->right_tree, mid + 1, right, K - delta);
    }
}

bool cmp(const int x, const int y) {
    return key[x] < key[y];
}

int id[MAXN];
int f[MAXN];

IntervalTree *root[MAXN];

IntervalTree *nullnode;

int main() {
    int M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++ i) {
        scanf("%d", &key[i]);
        id[i] = i;
    }

    sort(id + 1, id + N + 1, cmp);

    for (int i = 1; i <= N; ++ i)
        f[id[i]] = i;
    /*
    for (int i = 1; i <= N; ++ i) {
        printf("%d %d\n", key[i], f[i]);
    }
    */

    nullnode = (IntervalTree *)malloc(sizeof(IntervalTree));
    nullnode->size = 0;
    nullnode->left_tree = nullnode->right_tree = nullnode;

    pool_ptr = 0;

    root[0] = nullnode;
    for (int i = 1; i <= N; ++ i)
        root[i] = insert(root[i - 1], 1, N, f[i]);

    while (M --) {
        int x, y, rank;
        scanf("%d %d %d", &x, &y, &rank);
        int k = query(root[x - 1], root[y], 1, N, rank);
        printf("%d\n", key[id[k]]);
    }

    return 0;
}

kthC_ptr_tle.cc

// TLE
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define MAXN    100000 + 1

int N;

int key[MAXN];

struct IntervalTree {
    IntervalTree *left_tree, *right_tree;
    int size;
};

IntervalTree *insert(IntervalTree *node, int left, int right, int K) {
    IntervalTree *new_node = (IntervalTree *)malloc(sizeof(IntervalTree));
    new_node->left_tree = node->left_tree;
    new_node->right_tree = node->right_tree;
    new_node->size = node->size + 1;
    if (left == right) return new_node;
    int mid = (left + right) >> 1;
    if (K <= mid)
        new_node->left_tree = insert(new_node->left_tree, left, mid, K);
    else
        new_node->right_tree = insert(new_node->right_tree, mid + 1, right, K);
    return new_node;
}

int query(IntervalTree *x, IntervalTree *y, int left, int right, int K) {
    if (left == right) return left;
    int mid = (left + right) >> 1;
    //printf("%x %x\n", x, y);
    int delta = y->left_tree->size - x->left_tree->size;
    //printf("delta = %d\n", delta);
    if (K <= delta)
        return query(x->left_tree, y->left_tree, left, mid, K);
    else
        return query(x->right_tree, y->right_tree, mid + 1, right, K - delta);
}

bool cmp(const int x, const int y) {
    return key[x] < key[y];
}

int id[MAXN];
int f[MAXN];

IntervalTree *root[MAXN];

IntervalTree *nullnode;

int main() {
    int M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++ i) {
        scanf("%d", &key[i]);
        id[i] = i;
    }

    sort(id + 1, id + N + 1, cmp);

    for (int i = 1; i <= N; ++ i)
        f[id[i]] = i;
    /*
    for (int i = 1; i <= N; ++ i) {
        printf("%d %d\n", key[i], f[i]);
    }
    */

    nullnode = (IntervalTree *)malloc(sizeof(IntervalTree));
    nullnode->size = 0;
    nullnode->left_tree = nullnode->right_tree = nullnode;

    root[0] = nullnode;
    for (int i = 1; i <= N; ++ i)
        root[i] = insert(root[i - 1], 1, N, f[i]);

    //printf("here!\n");

    while (M --) {
        int x, y, rank;
        scanf("%d %d %d", &x, &y, &rank);
        int k = query(root[x - 1], root[y], 1, N, rank);
        printf("%d\n", key[id[k]]);
    }

    return 0;
}

kthD.cc

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN    100000 + 1
#define MAXM    5000

int N;

int key[MAXN];

bool cmp(const int x, const int y) {
    return key[x] < key[y];
}

int id[MAXN];
int f[MAXN];


struct bitree {
    int tree[MAXN];
    int A[MAXN];
    int n;
    
    bitree() {}
    bitree(int n) {
        initialize(n);
    }

    void initialize(int n) {
        this->n = n;
        memset(tree, 0, sizeof(tree));
        memset(A, 0, sizeof(A));
    }

    int getsum(int k) {
        int ret = 0;
        while (k) {
            ret += tree[k];
            k -= k & (-k);
        }
        return ret;
    }

    void update(int k, int val) {
        A[k] += val;
        while (k <= n) {
            tree[k] += val;
            k += k & (-k);
        }
    }

    int rank_k(int k, int all, int base) {
        vector<int> bits;
        while (all) {
            int lowbit = all & (-all);
            bits.push_back(lowbit);
            all -= lowbit;
        }
        for (int i = bits.size() - 1; i >= 0; -- i) {
            int count = tree[base + bits[i]];
            if (k == count && A[base + bits[i]] == 1) return base + bits[i];
            if (k <= count) return rank_k(k, bits[i] - 1, base);
            k -= count;
            base += bits[i];
        }
        return -1; // cannot touch here
    }

    int rank(int k) {
        return rank_k(k, n, 0);
    }
};

struct query_type {
    int x, y, rank;
    int id;
} query[MAXM];

int answer[MAXM];

int sqrtN;
int L, R;

bool cmp_mo(const query_type &A, const query_type &B) {
    if (A.x / sqrtN < B.x / sqrtN) return true;
    if (A.x / sqrtN > B.x / sqrtN) return false;
    return A.y < B.y;
}

bitree BIT;


int mo(int k) {
    if (L == 0 && R == 0) {
        L = query[k].x; R = query[k].y;
        for (int i = L; i <= R; ++ i)
            BIT.update(f[i], 1);
    }
    while (L < query[k].x) {
        BIT.update(f[L], -1);
        ++ L;
    }
    while (L > query[k].x) {
        -- L;
        BIT.update(f[L], 1);
    }
    while (R < query[k].y) {
        ++ R;
        BIT.update(f[R], 1);
    }
    while (R > query[k].y) {
        BIT.update(f[R], -1);
        -- R;
    }
    return BIT.rank(query[k].rank);

}

int main() {
    int M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++ i) {
        scanf("%d", &key[i]);
        id[i] = i;
    }

    sort(id + 1, id + N + 1, cmp);

    for (int i = 1; i <= N; ++ i)
        f[id[i]] = i;

    for (int i = 0; i < M; ++ i) {
        scanf("%d %d %d", &query[i].x, &query[i].y, &query[i].rank);
        query[i].id = i;
    }


    sqrtN = (int)sqrt(N);
    sort(query, query + M, cmp_mo);
    L = 0; R = 0;
    BIT.initialize(N);

    for (int i = 0; i < M; ++ i)
        answer[query[i].id] = key[id[mo(i)]];

    for (int i = 0; i < M; ++ i)
        printf("%d\n", answer[i]);

/*
    BIT.initialize(10);
    BIT.update(3, 1);
    BIT.update(5, 1);
    BIT.update(7, 1);
    BIT.update(9, 1);

    cout << BIT.rank(1) << endl;
*/

    return 0;
}