icontofig | 发布于 2019-08-01 11:29:45 | 阅读量 128 | 主席树
发布于 2019-08-01 11:29:45 | 主席树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 2e5+5;
struct tree{
    int l,r;
    tree *lc,*rc;
    int sum;    
}pool[maxn<<5],*root[maxn],*null;
int cnt = 0;
void init(){
    null = pool;
    null->sum = 0;
    null->lc = null->rc = null; 
    null->l = null->r = 0;
    return;
}
tree *new_node(){
    tree *node = pool + ++cnt;
    node->lc = node->rc = null;
    node->sum = 0;
    node->l = node->r = 0;
    return node;
}
tree *build(int l,int r){
    tree *node = new_node();
    node->l = l;
    node->r = r;
    if(l == r)return node;
    int mid = (l + r) >> 1;
    node->lc = build(l,mid);
    node->rc = build(mid+1,r);
    return node;
}
tree *update(tree *pre,int x){
    tree *now = new_node();
    now->lc = pre->lc;
    now->rc = pre->rc;
    now->l = pre->l;
    now->r = pre->r;
    now->sum = pre->sum + 1;
    if(now->lc == now->rc)
        return now;
    int mid = (now->l + now->r) >> 1;
    if(x <= mid)
        now->lc = update(pre->lc,x);
    else now->rc = update(pre->rc,x);
    return now;
}
int query(tree *ll,tree *rr,int k){
    if(ll->l == ll->r)return ll->l;
    int x = rr->lc->sum - ll->lc->sum;
    if(x >= k){
        return query(ll->lc,rr->lc,k);
    }
    else return query(ll->rc,rr->rc,k - x);
}
int a[maxn];
int b[maxn];
int n,q;
int tot = 0;
int l,r,k,p,x;
int main(){
    init();
    n = get_num();
    cnt = 0;
    q = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
        b[i] = a[i];
    }
    sort(b+1,b+n+1);
    tot = unique(b+1,b+n+1) - b - 1;
    root[0] = build(1,tot);
    for(int i = 1;i <= n;++i){
        int t = lower_bound(b+1,b+tot+1,a[i]) - b;
        root[i] = update(root[i-1],t);
    }
    while(q--){
        l = get_num();
        r = get_num();
        k = get_num();
        int ans = query(root[l-1],root[r],k);
        printf("%d\n",b[ans]);
    }
    return 0;
}

 


内容更新于: 2019-08-01 11:29:45
链接地址: http://blog.leanote.com/post/icontofig/714ffdf5c645

上一篇: 2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树(主席树)

下一篇: 2019 Multi-University Training Contest 3 Game 经典NIM博弈SG函数 + 带修改莫队

128 人读过
立即登录, 发表评论.
没有帐号? 立即注册
1 条评论
文档导航