hdu2665,poj2104,51nod1175

链接:51nod
链接:poj
链接:hdu
链接:luogu

题解

  • 主席树(划分树)入门

    主席树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e5+7;
    typedef pair<int,int> q;
    int rt[N*20],root[N],rk[N],lson[N*20],rson[N*20],cnt=1,n,m,T;
    q nm[N];
    inline void update(int &o,int l,int r,int num){
    rt[cnt]=rt[o];lson[cnt]=lson[o];rson[cnt++]=rson[o];o=cnt-1;rt[o]++;
    if(l==r)return ;
    int mid=l+r>>1;
    if(num<=mid)update(lson[o],l,mid,num);
    else update(rson[o],mid+1,r,num);
    }
    inline int query(int i,int j,int l,int r,int k){
    int t=rt[lson[j]]-rt[lson[i]];
    if(l==r)return l;
    int mid=l+r>>1;
    if(k<=t)return query(lson[i],lson[j],l,mid,k);
    else return query(rson[i],rson[j],mid+1,r,k-t);
    }
    int main(){
    scanf("%d",&n);
    rep(i,1,n){
    int x;
    scanf("%d",&x);
    nm[i]=q(x,i);
    }
    scanf("%d",&m);
    sort(nm+1,nm+n+1);
    rep(i,1,n)rk[nm[i].second]=i;
    rep(i,1,n){root[i]=root[i-1];update(root[i],1,n,rk[i]);}
    while(m--){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    a++;b++;
    c=b-a+2-c;
    printf("%d\n",nm[query(root[a-1],root[b],1,n,c)].first);
    }
    return 0;
    }