学步园

今晚整理了一下主席树，拿这题试验模版，速度有些慢，是我写挫了么？

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <memory>
#include <complex>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

#pragma pack(4)

const double  eps = 1e-8;
const double   pi = acos(-1.0);
const int     inf = 0x7f7f7f7f;

#define loop(a,n)                            \
    for(int i=0;n>i;i++)                     \
        cout<<a[i]<<(i!=n-1?' ':'\n')
#define loop2(a,n,m)                         \
    for(int i=0;n>i;i++)                     \
        for(int j=0;m>j;j++)                 \
            cout<<a[i][j]<<(j!=m-1?' ':'\n')

#define   at(a,i) ((a)&(1<<(i)))
#define   nt(a,i) ((a)^(1<<(i)))
#define set1(a,i) ((a)|(1<<(i)))
#define set0(a,i) ((a)&(~(1<<(i))))

#define gret(a,b) (((a)-(b))>eps)
#define less(a,b) (((b)-(a))>eps)
#define greq(a,b) (((a)-(b))>-eps)
#define leeq(a,b) (((b)-(a))>-eps)
#define equl(a,b) (fabs((a)-(b))<eps)

#define lmax(a,b) ((a)>(b)?(a):(b))
#define lmin(a,b) ((a)<(b)?(a):(b))
#define fmax(a,b) (gret(a,b)?(a):(b))
#define fmin(a,b) (less(a,b)?(a):(b))

const int MAXV = 100002;

class CMT
{
private:
    struct node
    {
        int s;
        node *c[2];
        int ls(void)
        {
            return this?c[0]->size():0;
        }
        int rs(void)
        {
            return this?c[1]->size():0;
        }
        int size(void)
        {
            return this?s:0;
        }
    }pool[MAXV*40],*a[MAXV],*c[33],*d[33];
    int use,left,right,amount;

    node *malloc(node *root,int w)
    {
        node *now=&pool[use++];
        if(!root)
        {
            now->s=w;
            now->c[0]=NULL;
            now->c[1]=NULL;
        }
        else
        {
            now->s=w+root->s;
            now->c[0]=root->c[0];
            now->c[1]=root->c[1];
        }
        return now;
    }

    int query(int k,int lc,int ld,int l,int r)
    {
        if(l==r) return l;
        else
        {
            int sum=0;
            for(int i=0;lc>i;i++)
                if(c[i]) sum-=c[i]->ls();
            for(int i=0;ld>i;i++)
                if(d[i]) sum+=d[i]->ls();
            if(sum>=k)
            {
                for(int i=0;lc>i;i++)
                    if(c[i]) c[i]=c[i]->c[0];
                for(int i=0;ld>i;i++)
                    if(d[i]) d[i]=d[i]->c[0];
                return query(k,lc,ld,l,(l+r)/2);
            }
            else
            {
                for(int i=0;lc>i;i++)
                    if(c[i]) c[i]=c[i]->c[1];
                for(int i=0;ld>i;i++)
                    if(d[i]) d[i]=d[i]->c[1];
                return query(k-sum,lc,ld,(l+r)/2+1,r);
            }
        }
    }
    node *insert(node *root,int x,int w,int l,int r)
    {
        root=malloc(root,w);
        if(l!=r)
        {
            if(x<=(l+r)/2) root->c[0]=insert(root->c[0],x,w,l,(l+r)/2);
            if((l+r)/2<x) root->c[1]=insert(root->c[1],x,w,(l+r)/2+1,r);
        }
        return root;
    }

public:
    void clear(int n,int l,int r)
    {
        use=0;
        left=l;
        right=r;
        amount=n;
        for(int i=0;n>=i;i++) a[i]=NULL;
    }

    int query(int x,int y,int k)
    {
        int lc=0,ld=0;
        c[lc++]=a[x];
        d[ld++]=a[y];
        return query(k,lc,ld,left,right);
    }
    void insert(int i,int x,int w)
    {
        a[i]=insert(a[i-1],x,w,left,right);
    }
}cmt;

int n,m,x,y,k,a[MAXV],b[MAXV];

int rank(int val,int tot)
{
    return lower_bound(b,b+tot,val)-b;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("K-th Number.txt","r",stdin);
    #endif

    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int cnt=0,tot=1;
        for(int i=0;n>i;i++)
        {
            scanf("%d",&a[i]);
            b[cnt++]=a[i];
        }

        sort(b,b+cnt);
        for(int i=1;cnt>i;i++)
        {
            if(b[i]!=b[i-1]) b[tot++]=b[i];
        }

        cmt.clear(n,0,n-1);
        for(int i=0;n>i;i++)
        {
            cmt.insert(i+1,rank(a[i],tot),+1);
        }
        for(int i=0;m>i;i++)
        {
            scanf("%d %d %d",&x,&y,&k);
            printf("%d\n",b[cmt.query(x-1,y,k)]);
        }
    }

    return 0;
}