2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle（ 主席树求区间第k大）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 300000;
int sum[maxn*20+5];//sum为森林的不同根结点
struct E {
    ll num;
    int l,r;
} t[maxn*20+5]; //t为tree树
int n,sz,m,cnt;
ll a[maxn],b[maxn];
int build(int l,int r) {
    int now = ++cnt;
    int mid = (l+r)>>1;
    if(l<r) {
        t[now].l = build(l,mid);
        t[now].r = build(mid+1,r);
    }
    return now;
}
int update(int l,int r,int last,int p) {
    int now = ++cnt;
    t[now].num = t[last].num+1;
    t[now].l = t[last].l;
    t[now].r = t[last].r;
    int mid = (l + r)>>1;
    if(l<r) {
        if(p<=mid)t[now].l = update(l,mid,t[last].l,p);
        else t[now].r = update(mid+1,r,t[last].r,p);
    }
    return now;
}
ll query(int u,int v,int l,int r,int k) {
    if(l==r)return l;
    // v 左孩子包含点个数减去 u 左孩子包含点的个数
    int tmp = t[t[v].l].num - t[t[u].l].num;
    int mid = (l+r)>>1;
    if(k<=tmp)return query(t[u].l,t[v].l,l,mid,k);
    else return query(t[u].r,t[v].r,mid+1,r,k - tmp);
}
bool judge(ll x,ll y,ll z){
    if(y+z>x){
        return true;
    }
    return false;
}
int main() {
    ll t1,t2,t3;
    while(scanf("%d %d",&n,&m)==2) {
        for(int i=1; i<=n; i++)scanf("%lld",&a[i]),b[i]=a[i];
        sort(b+1,b+n+1);
        sz = unique(b+1,b+n+1) - (b+1);
        cnt = 0;
        sum[0] = build(1,sz);//建立空树
        for(int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+sz+1,a[i]) - b;
        for(int i=1; i<=n; i++) sum[i] = update(1,sz,sum[i-1],a[i]);
        while(m--) {
            int u,v,k = 4,flag=0;
            scanf("%d %d",&u,&v);
            if(v-u+1<3){
                printf("-1\n");
                continue;
            }
            int len = v - u  + 1;
            t1 = query(sum[u-1],sum[v],1,sz,len-1+1);    t1 = b[t1];
            t2 = query(sum[u-1],sum[v],1,sz,len - 2+1);    t2 = b[t2];
            t3 = query(sum[u-1],sum[v],1,sz,len-3+1);    t3 = b[t3];
            
            while(1){
                if(judge(t1,t2,t3)){
                    flag = 1;
                    break;
                }
                if(k>len)break;
                t1 = t2;    t2 = t3;
                t3 = query(sum[u-1],sum[v],1,sz,len-k+1);    t3 = b[t3];
                k++;    
            }
            if(flag)printf("%lld\n",t1+t2+t3);
            else     printf("-1\n");
        }
    }
    return 0;
}