11114: 【原1114】Problem A

题目

题目描述

author: Zheyi Pan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1114

Description

给定n个数a[1], a[2], ..., a[n]，m个询问(l, r, k)，询问a[l], a[l+1], ..., a[r]中第k小的数是多少。保证0<=k<=r–l+1。

Input Format

第一行一个正整数n。

第二行n个数，表示a[i]。

接下来一个正整数m。

以下m行每行三个整数l, r, k。

Output Format

输出共m行，每行一个数表示a[l], a[l+1], ..., a[r]中的第k小数。

Sample Input

Sample Output

2
1
5

Restrictions

60%： n, m <= 1000。

80%：数据满足询问区间互相不包含。

100%：n, m <= 300000，|a[i]| <= 10^9。

内存限制：512MB

时间限制：2000ms

FineArtz's solution

/* Problem A */
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 300005;

class Node{
public:
    int sum = 0, l = 0, r = 0;
};

int a[MAXN], s[MAXN], root[MAXN] = {0};
int cnt = 0;
Node tree[MAXN << 5];

int createNode(int sum, int l, int r){
    tree[++cnt].sum  = sum;
    tree[cnt].l = l;
    tree[cnt].r = r;
    return cnt;
}

void insert(int &root, int preroot, int pos, int l, int r){
    root = createNode(tree[preroot].sum + 1, tree[preroot].l, tree[preroot].r);
    if (l == r)
        return;
    int mid = (l + r) / 2;
    if (pos <= mid)
        insert(tree[root].l, tree[preroot].l, pos, l, mid);
    else
        insert(tree[root].r, tree[preroot].r, pos, mid + 1, r);
}

int query(int left, int right, int k, int l, int r){
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    int sum = tree[tree[right].l].sum - tree[tree[left].l].sum;
    if (k <= sum)
        return query(tree[left].l, tree[right].l, k, l, mid);
    else
        return query(tree[left].r, tree[right].r, k - sum, mid + 1, r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        s[i] = a[i];
    }
    sort(s + 1, s + n + 1);
    int num = unique(s + 1, s + n + 1) - (s + 1);
    for (int i = 1; i <= n; ++i){
        int pos = lower_bound(s + 1, s + num + 1, a[i]) - s;
        insert(root[i], root[i - 1], pos, 1, num);
    }
    cin >> m;
    while (m--){
        int x, y, k;
        cin >> x >> y >> k;
        int t = query(root[x - 1], root[y], k, 1, num);
        cout << s[t] << '\n';
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#define MAX 300010
using namespace std;
const int INF = 0xFFFFFFF;
int nums[MAX], sorted[MAX], root[MAX];
int cnt;
struct TMD {
    int sum, L_son, R_son;
} Tree[MAX << 5];

inline int CreateNode(int _sum, int _L_son, int _R_son) {

    int idx = ++cnt;
    Tree[idx].sum = _sum;
    Tree[idx].L_son = _L_son;
    Tree[idx].R_son = _R_son;
    return idx;
}

void Insert(int & root, int pre_rt, int pos, int L, int R) {

    root = CreateNode(Tree[pre_rt].sum + 1, Tree[pre_rt].L_son, Tree[pre_rt].R_son);
    if (L == R) return;
    int M = (L + R) >> 1;
    if (pos <= M)
        Insert(Tree[root].L_son, Tree[pre_rt].L_son, pos, L, M);
    else
        Insert(Tree[root].R_son, Tree[pre_rt].R_son, pos, M + 1, R);
}

int Query(int S, int E, int L, int R, int K) {

    if (L == R) return L;
    int M = (L + R) >> 1;
    int sum = Tree[Tree[E].L_son].sum - Tree[Tree[S].L_son].sum;
    if (K <= sum)
        return Query(Tree[S].L_son, Tree[E].L_son, L, M, K);
    else
        return Query(Tree[S].R_son, Tree[E].R_son, M + 1, R, K - sum);
}

int main() {

    int n, m, num, pos, T;
    scanf("%d", &n);
    cnt = 0; root[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &nums[i]);
        sorted[i] = nums[i];
    }
    sort(sorted + 1, sorted + 1 + n);
    num = unique(sorted + 1, sorted + n + 1) - (sorted + 1);
    for (int i = 1; i <= n; ++i) {
        pos = lower_bound(sorted + 1, sorted + num + 1, nums[i]) - sorted;
        Insert(root[i], root[i - 1], pos, 1, num);
    }
    scanf("%d", &m);
    int l, r, k;
    while (m--) {
        scanf("%d %d %d", &l, &r, &k);
        pos = Query(root[l - 1], root[r], 1, num, k);
        printf("%d\n", sorted[pos]);
    }
    return 0;
}