主席树入门——询问区间第k大pos2104，询问区间<=k的元素个数hdu4417

poj2104找了个板子。。,但是各种IO还可以进行优化

/*

找区间[l,r]第k大的数

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 100005

struct Node{int lc,rc,sum;}t[maxn*];

int n,q,a[maxn],b[maxn],m,rt[maxn],size;

int build(int l,int r){

    int now=++size;

    t[now].lc=t[now].rc=t[now].sum=;

    if(l==r)return now;

    int mid=l+r>>;

    t[now].lc=build(l,mid);

    t[now].rc=build(mid+,r);

    return now;

}

int update(int last,int l,int r,int pos){//更新到pos点

    int now=++size;

     t[now]=t[last];t[now].sum++;

     if(l==r)return now;

     int mid=l+r>>;

     if(pos<=mid)t[now].lc=update(t[last].lc,l,mid,pos);

     else t[now].rc=update(t[last].rc,mid+,r,pos);

     return now;

}

int query(int st,int ed,int l,int r,int k){

    if(l==r)return l;

    int mid=l+r>>;

    int sum=t[t[ed].lc].sum-t[t[st].lc].sum;

    if(k<=sum)return query(t[st].lc,t[ed].lc,l,mid,k);

    else return query(t[st].rc,t[ed].rc,mid+,r,k-sum);

}

void debug(int x){

    cout<<t[t[rt[]].lc].sum-t[t[rt[]].lc].sum;

}

int main(){

    cin>>n>>q;

    for(int i=;i<=n;i++)cin>>a[i],b[i]=a[i];

    sort(b+,b++n);

    m=unique(b+,b++n)-(b+);

    rt[]=build(,m);

    for(int i=;i<=n;i++){

        int pos=lower_bound(b+,b++m,a[i])-b;

        rt[i]=update(rt[i-],,m,pos);

    }

    while(q--){

        int l,r,k;

        cin>>l>>r>>k;

        cout<<b[query(rt[l-],rt[r],,m,k)]<<'\n';

    }

}

hdu4417 用vector会莫名MLE，以后就用数组来进行离散化吧。另外，unique(a+1,a+1+n)函数对a数组去重，然后返回去重数组的下一位下标

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

struct Node{int lc,rc,v;}t[maxn*];

int m,tot,a[maxn],b[maxn],n,rt[maxn];

int update(int last, int l, int r, int pos){

    int now = ++ tot;

    t[now] = t[last];

    t[now].v ++;

    if(l == r) return now;

    int mid = (l + r) >> ;

    if(pos <= mid) t[now].lc = update(t[last].lc, l, mid, pos);

    else t[now].rc = update(t[last].rc, mid+, r, pos);

    return now;

}

int query(int st, int ed, int L, int R, int l, int r){

    if(L <= l && r <= R) return t[ed].v - t[st].v;

    int mid = (l + r) >> ;

    int res = ;

    if(L <= mid) res += query(t[st].lc, t[ed].lc, L, R, l, mid);

    if(R > mid) res += query(t[st].rc, t[ed].rc, L, R, mid+, r);

    return res;

}

int build(int l,int r){

    int now=++tot;

    t[now].lc=t[now].rc=t[now].v=;

    if(l==r)return now;

    int mid=l+r>>;

    t[now].lc=build(l,mid);

    t[now].rc=build(mid+,r);

    return now;

}

int main(){

    int T, Case = ;

    scanf("%d", &T);

    int n, q;

    while(T --) {

        scanf("%d %d", &n, &q);

        for(int i = ;i <= n;i ++) {

            scanf("%d", &a[i]);

            b[i] = a[i];

        }

        sort(b+, b++n);

        int m = unique(b+, b++n) - (b+);

        for(int i = ;i <= n;i ++) a[i] = lower_bound(b+, b++m, a[i]) - b;

        tot = ;

        rt[] = build(, m);

        for(int i = ;i <= n;i ++) rt[i] = update(rt[i-], , m, a[i]);

        printf("Case %d:\n", ++Case);

        while(q --) {

            int l, r, H;

            scanf("%d %d %d", &l, &r, &H);

            l ++, r ++;

            int pos = upper_bound(b+, b++m, H) - b;

            pos --;

            if(!pos) {

                puts("");

                continue;

            } else {

                printf("%d\n", query( rt[l-], rt[r], , pos, , m ) );

            }

        }

    }

    return ;

}