主席树轻松过

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100010
#define MAXN maxn*18

using namespace std;
typedef long long llg;

int n,m,le[MAXN],ri[MAXN],sumv[MAXN],sz;
int a[maxn],b[maxn],c[maxn],rot[maxn],L;

int getint(){
    int w=0,q=0;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') q=1,c=getchar();
    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}

int build(int u,int l,int r,int k){
    int now=++sz;
    le[now]=le[u];ri[now]=ri[u];
    sumv[now]=sumv[u]+1;
    if(l!=r){
        int mid=l+r>>1;
        if(k<=mid) le[now]=build(le[u],l,mid,k);
        else ri[now]=build(ri[u],mid+1,r,k);
    }
    return now;
}

int find(int u1,int u2,int l,int r,int k){
    while(l!=r){
        int now=sumv[le[u2]]-sumv[le[u1]],mid=l+r>>1;
        if(k<=now) u1=le[u1],u2=le[u2],r=mid;
        else u1=ri[u1],u2=ri[u2],l=mid+1,k-=now;
    }
    return l;
}

int main(){
    n=getint();m=getint();
    for(int i=1;i<=n;i++) a[i]=b[i]=getint();
    sort(b+1,b+n+1);L=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int l=1,r=L,mid;
        while(l!=r){
            mid=l+r>>1;
            if(b[mid]>=a[i]) r=mid;
            else l=mid+1;
        }
        c[i]=l;
    }
    for(int i=1;i<=n;i++) rot[i]=build(rot[i-1],1,L,c[i]);
    for(int i=1;i<=m;i++){
        int l=getint(),r=getint();
        printf("%d\n",b[find(rot[l-1],rot[r],1,L,getint())]);
    }
    return 0;
}

L打成1 查了半天QAQ

主席树 教程

本题是区间k大问题，给你l,r,k，求出[l,r]中从小到大第k个数字的值

假如请求的区间只有一个，是[1,n]
那么一个简单的做法就是用STL排序，直接输出新数组的第k个数字即可

还有一种看上去比较傻的方法就是对排序好的数字进行去重，
这样每个数字都是独一无二的，记录它们在原数组中出现的次数，视为它们的权重
然后我们可以用二分的方法，先看左半边的数列，它们的权重和是否<=k，如果是这样
那么第k小数字一定是左半边的，否则位于右半边，如此下去可以用O(logn)的时间发现第k小数字

相比较直接输出的O(1)，这个方法好像多此一举

但是对于多个查询的方法，二分就显示了它的优越性

每个询问区间我们都排序一遍是吃不消的

而二分法我们需要用到的仅仅是某段区间和，而它可以通过别的区间作差来表示

因此我们只需要对每个i=1~n，把[1,i]视为一个独立的问题像上面说的那样求出各个数字的权重数组，
比如说 原数组
2 3 4 2 5 6 3

排序去重后只剩下数字
2 3 4 5 6
它们在数组中的下标
1 2 3 4 5

对于[1,7] 权重数组 就是

下标 1 2 3 4 5
数值 2 2 1 1 1
（意义：下标1对应的数字是2，数值代表它出现了2次，其他类似）

对于[1,6] 权重数组 就是

下标 1 2 3 4 5
数值 2 1 1 1 1
（意义：不再包含原数组中最后一个数字3了）

假如说查询的是[l,r]，那么我们二分的时候需要区间和的时候，
可以通过[1,l-1]和[1,r]中的区间和作差来表示
这样就解决问题了

等等，怎么求所有[1,i]的权重数组呢？
注意到i每变化一次，新的权重数组只会在某个位置上比原来的权重数组多1，因此我们不需要每次都重新求一遍
我们对权重数组的二分过程可以视为在一棵线段树上不断向子节点走，
所以我们只需要新建一个节点把它的左右儿子链接到已经求好的节点上就可以实现复用了
（有点指针的思想）
每次只会走一条树路径所以每次修改O(logn)

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int LOG=20;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,m;
int a[N];
int b[N];
int num;
struct data {
    int l,r,sum;
} node[N*LOG];
int root[N];
int cnt;
void build(int l,int r,int &rt) {
    rt=++cnt;
    node[rt].l=node[rt].r=node[rt].sum=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,node[rt].l);
    build(mid+1,r,node[rt].r);
}
void update(int l,int r,int v,int &rt,int pre) {
    rt=++cnt;
    node[rt]=node[pre];
    ++node[rt].sum;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (v<=mid) {
        update(l,mid,v,node[rt].l,node[pre].l);
    } else {
        update(mid+1,r,v,node[rt].r,node[pre].r);
    }
}
int query(int l,int r,int v,int rt1,int rt2) {
    if (l==r) return l;
    int l_sum=node[node[rt2].l].sum-node[node[rt1].l].sum;
    int mid=(l+r)>>1;
    if (v<=l_sum) {
        return query(l,mid,v,node[rt1].l,node[rt2].l);
    } else {
        return query(mid+1,r,v-l_sum,node[rt1].r,node[rt2].r);
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,n) cin>>a[i];
    
    FOR(i,n) b[i]=a[i];
    sort(b+1,b+1+n);
    num=unique(b+1,b+1+n)-(b+1);
    build(1,num,root[0]);
    
    FOR(i,n) {
        int pos=lower_bound(b+1,b+1+num,a[i])-b;
        update(1,num,pos,root[i],root[i-1]);
    }
    
    FOR(i,m) {
        int l,r,k;
        cin>>l>>r>>k;
        int pos=query(1,num,k,root[l-1],root[r]);
        cout<<b[pos]<<endl;
    }
    return 0;
}

划分树：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

int ai_sort[100005],tree_ai[25][100005],sum[25][100005];

void build(int floor,int l,int r){
if(r-l<2) {
tree_ai[floor][l] = tree_ai[floor-1][l];
return;
}
int mid = (l+r)/2,i,ki = l,kj = mid,same = 0;
for(i = mid-1;i>=l&&ai_sort[i] == ai_sort[mid];i--) same++;
for(i = l;i<r;i++) {
if(tree_ai[floor-1][i] < ai_sort[mid] || (same>0&&tree_ai[floor-1][i] == ai_sort[mid])) {
tree_ai[floor][ki] = tree_ai[floor-1][i];
ki++;
if(i == l) sum[floor][i] = 1;
else sum[floor][i] = sum[floor][i-1]+1;
if(tree_ai[floor-1][i] == ai_sort[mid]) same--;
}
else {
tree_ai[floor][kj] = tree_ai[floor-1][i];
kj++;
if(i == l) sum[floor][i] = 0;
else sum[floor][i] = sum[floor][i-1];
}
}
build(floor+1,l,mid);
build(floor+1,mid,r);
}

int inquiry(int a,int b,int k,int floor,int l,int r){
if(r-l<2) return tree_ai[floor][l];
int mid = (r+l)/2,c,tmp,tmp2;
if(a==l) tmp = tmp2 = 0;
else {
tmp = sum[floor][a-1];
tmp2 = a-l - sum[floor][a-1];
}
c = sum[floor][b] - tmp;
if(k<=c) {
return inquiry(l+tmp,l+tmp+c-1,k,floor+1,l,mid);
}
else {
return inquiry(mid+tmp2,mid+tmp2+b-a+1-c-1,k-c,floor+1,mid,r);
}
}

int main(){
int i,j,m,n;
scanf("%d%d",&n,&m);
for(i = 1;i<=n;i++){
scanf("%d",&tree_ai[1][i]);
ai_sort[i] = tree_ai[1][i];
}
sort(ai_sort+1,ai_sort+1+n);
build(2,1,1+n);
int a,b,k;
for(i = 1;i<=m;i++) {
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",inquiry(a,b,k,2,1,1+n));
}
return 0;
}

函数式线段树
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

int countn,head[100005],sort_ai[100005];

struct Node{
int right,left,data;
};
Node node[2000005];

struct D{
int ai,id,size;
};
D d[100005];

bool cmp1(const D &a,const D &b){
return a.ai<b.ai;
}

bool cmp2(const D &a,const D &b){
return a.id<b.id;
}

int build_first_tree(int l,int r){
countn++;
int n = countn;
if(r-l < 2) return n;
node[n].left = build_first_tree(l,(r+l)/2);
node[n].right = build_first_tree((r+l)/2,r);
return n;
}

int add_node(int nodeN,int last_tree,int l,int r){
countn++;
int n = countn,mid = (l+r)/2;
node[n].data = node[last_tree].data+1;
if(r-l < 2) return n;
if(d[nodeN].size<mid){
node[n].left = add_node(nodeN,node[last_tree].left,l,mid);
node[n].right = node[last_tree].right;
}
else {
node[n].left = node[last_tree].left;
node[n].right = add_node(nodeN,node[last_tree].right,mid,r);
}
return n;
}

int inquiry(int a,int b,int k,int l,int r){
if(r-l < 2) return l;
int c = node[node[b].left].data - node[node[a].left].data,mid = (l+r)/2;
if(k<=c) {
return inquiry(node[a].left,node[b].left,k,l,mid);
}
else {
return inquiry(node[a].right,node[b].right,k-c,mid,r);
}
}

int main(){
int i,j,m,n;
scanf("%d%d",&n,&m);
for(i = 1;i<=n;i++){
scanf("%d",&d[i].ai);
d[i].id = i;
}
memset(node,0,sizeof(node));
sort(d+1,d+1+n,cmp1);
for(i = 1;i<=n;i++) {
d[i].size = i;
sort_ai[i] = d[i].ai;
}
sort(d+1,d+1+n,cmp2);
countn = 0;
head[0] = build_first_tree(1,n+1);
for(i = 1;i<=n;i++) {
head[i] = add_node(i,head[i-1],1,n+1);
}
int a,b,k;
for(i = 1;i<=m;i++) {
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",sort_ai[inquiry(head[a-1],head[b],k,1,1+n)]);
}
return 0;
}

注意：存在相同能力值。
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

struct Node {
Node *ch[2];
int v, sz, r;

Node(int v):v(v) { sz = 1; r = rand(); ch[0] = ch[1] = NULL; }

int cmp(int x) const {
if (x == v) return -1;
return x < v ? 0 : 1;
}

void push_up() {
sz = 1;
if (ch[0] != NULL) sz += ch[0]->sz;
if (ch[1] != NULL) sz += ch[1]->sz;
}
};

Node *root;

void rotate(Node* &rt, int d) {
Node *k = rt->ch[d ^ 1];
rt->ch[d ^ 1] = k->ch[d];
k->ch[d] = rt;
rt->push_up();
k->push_up();
rt = k;
}

void Insert(Node* &rt, int v) {
if (rt == NULL) rt = new Node(v);
else {
int d = (v < rt->v ? 0 : 1);
Insert(rt->ch[d], v);
if (rt->ch[d]->r > rt->r) rotate(rt, d ^ 1);
}
rt->push_up();
}

void Delete(Node* &rt, int v) {
int d = rt->cmp(v);
if (d == -1) {
if (rt->ch[0] != NULL && rt->ch[1] != NULL) {
int d2 = (rt->ch[0]->r > rt->ch[1]->r ? 1 : 0);
rotate(rt, d2); Delete(rt->ch[d2], v);
} else {
Node *u = rt;
if (rt->ch[0] == NULL) rt = rt->ch[1]; else rt = rt->ch[0];
delete u;
}
} else Delete(rt->ch[d], v);
if (rt != NULL) rt->push_up();
}

int kth(Node *rt, int k) {
//if (rt == NULL || k <= 0 || k > rt->sz) return 0;
int s = (rt->ch[0] == NULL ? 0 : rt->ch[0]->sz);
if (k == s + 1) return rt->v;
else if (k <= s) return kth(rt->ch[0], k);
else return kth(rt->ch[1], k - s - 1);
}

typedef pair<int, int> PII;
const int N = 100000 + 5, M = 50000 + 5;

int n, m, a[N];

struct Interval {
int l, r, k, id;
bool operator < (const Interval& rhs) const {
return l < rhs.l || (l == rhs.l && r < rhs.r);
}
} itv[M];

PII ans[M];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &itv[i].l, &itv[i].r, &itv[i].k);
itv[i].id = i;
}
sort(itv + 1, itv + m + 1);
int l = 0, r = 0;
for (int i = 1; i <= m; i++) {
if (r < itv[i].l) {
for (int j = itv[i].l; j <= itv[i].r; j++) Insert(root, a[j]);
} else {
for (int j = l; j < itv[i].l; j++) Delete(root, a[j]);
for (int j = r + 1; j <= itv[i].r; j++) Insert(root, a[j]);
}
l = itv[i].l, r = itv[i].r;
ans[i].first = itv[i].id;
ans[i].second = kth(root, itv[i].k);
}
sort(ans + 1, ans + m + 1);
for (int i = 1; i <= m; i++) printf("%d\n", ans[i].second);
return 0;
}

什么主席树（朱熹输），不会~~~~~~~
树上莫队赛高！！！！
```c++
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

#define INF 1<<29
#define eps 1e-8
#define A system("pause")
#define rep(i,h,n) for(int i=(h);i<=(n);i++)
#define ms(a,b) memset((a),(b),sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
#define mod 100000000
const int maxn=100000+5;
const int maxm=100+10;
struct Node
{
Node* ch[2];//定义左右子树；
int r,v;//每个结点的随机优先级及value；
int s;//结点总数；
Node(int v):v(v)
{
ch[0]=ch[1]=NULL;
r=rand();
s=1;
}
bool operator <(const Node& rhs)const
{
return r<rhs.r;
}
int cmp(int x) const
{
if(x==v) return -1;
return x<v?0:1;
}
void maintain()//维护结点信息；
{
s=1;
if(ch[0]!=NULL) s+=ch[0]->s;
if(ch[1]!=NULL) s+=ch[1]->s;
}
};

inline void rotate(Node* &o,int d)//d==0表示左旋，d==1表示右旋；
{
Node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}

inline void insert(Node* &o,int x)//先是普通插入，if(x_v<o_v)插入左子树，在比较优先级进行旋转操作；
{
if(o==NULL) o=new Node(x);
else
{
int d=(x<o->v?0:1);//不要用cmp函数，可能会有相同结点；
insert(o->ch[d],x);//插入新结点，比较优先级进行旋转；
if(o->ch[d]->r>o->r) rotate(o,d^1);
}
o->maintain();//维护结点o的信息；
}

inline void remove(Node* &o,int x)
{
int d=o->cmp(x);
if(d==-1)
{
Node* u=o;
if(o->ch[0]!=NULL && o->ch[1]!=NULL)
{
int d2=(o->ch[0]->r>o->ch[1]->r?1:0);
rotate(o,d2);
remove(o->ch[d2],x);
}
else
{
if(o->ch[0]==NULL) o=o->ch[1];
else o=o->ch[0];
delete u;
}
}
else
remove (o->ch[d],x);
if(o!=NULL) o->maintain();
}
//查找区间第k大数；
inline int kth(Node* o,int k)
{
if(o==NULL || k<=0 || k>o->s) return 0;
int s=(o->ch[0]==NULL? 0:o->ch[0]->s);
if(k==s+1) return o->v;
else if(k<=s) return kth(o->ch[0],k);
else return kth(o->ch[1],k-s-1);
}

struct Q
{
int l,r,k,id;
bool operator<(const Q& B)const
{
return l<B.l;
}
}q[maxn];
int n,m,a[maxn],ret[maxn];

int main()
{
Node* rt=NULL;
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,m)
{
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
q[i].id=i;
}
sort(q+1,q+m+1);
int left=q[1].l,right=q[1].l;
rep(i,1,m)
{
while(right>q[i].r)
{
right--;
remove(rt,a[right]);

}
while(left<q[i].l)
{
remove(rt,a[left]);
left++;
}
while(right<=q[i].r)
{
insert(rt,a[right]);
right++;
}

ret[q[i].id]=kth(rt,q[i].k);
}
rep(i,1,m) printf("%d\n",ret[i]);
return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>

struct Node
{
int val;
int lSize;
int rSize;
Node* left;
Node* right;
int rank;

Node (int v): val (v), lSize (0), rSize (0), left (0), right (0)
{
rank = rand();
}

Node* rRotate()
{
Node* temp = left;

this->left = temp->right;
temp->right = this;

this->lSize = temp->rSize;
temp->rSize = (this->lSize + this->rSize + 1);

return temp;
}

Node* lRotate()
{
Node* temp = right;

this->right = temp->left;
temp->left = this;

this->rSize = temp->lSize;
temp->lSize = (this->lSize + this->rSize + 1);

return temp;
}

void clear()
{
if (lSize) left->clear();
if (rSize) right->clear();
delete this;
}
};

class Treap
{
private:
Node* root;

Node* _insert (int v, Node* cur)
{
if (!cur) return new Node (v);

if (v < cur->val)
{
++cur->lSize;
cur->left = _insert (v, cur->left);
return (cur->left->rank > cur->rank) ?
cur->rRotate() : cur;
}
else
{
++cur->rSize;
cur->right = _insert (v, cur->right);
return (cur->right->rank > cur->rank) ?
cur->lRotate() : cur;
}
}

Node* _erase (int v, Node* cur)
{
if (!cur) return 0;
else if (v < cur->val)
{
cur->left = _erase (v, cur->left);
--cur->lSize;
return cur;
}
else if (v > cur->val)
{
cur->right = _erase (v,cur->right);
--cur->rSize;
return cur;
}

return _erase_aux (cur);
}

Node* _erase_aux (Node* cur)
{
int ks = 0;
if (cur->lSize) ks |= 1;
if (cur->rSize) ks |= 2;
switch (ks)
{
case 0:
delete cur;
return 0;
case 1:
return _erase_aux_left (cur);
case 2:
return _erase_aux_right (cur);
case 3:
return (cur->left->rank > cur->right->rank) ?
_erase_aux_left (cur) : _erase_aux_right (cur);
}
}

Node* _erase_aux_left (Node* cur)
{
Node* temp = cur->rRotate();
temp->right = _erase_aux (cur);
--temp->rSize;
return temp;
}

Node* _erase_aux_right (Node* cur)
{
Node* temp = cur->lRotate();
temp->left = _erase_aux (cur);
--temp->lSize;
return temp;
}

public:
Treap(): root (0) {}
~Treap()
{
if (root) root->clear();
}

void insert (int v)
{
root = _insert (v, root);
}

void erase (int v)
{
root = _erase (v, root);
}

int getKth (int k)
{
Node* cur = root;
for (;;)
{
if (k == cur->lSize + 1) return cur->val;
else if (k <= cur->lSize)
cur = cur->left;
else
{
k -= (cur->lSize + 1);
cur = cur->right;
}
}
return -1;
}
};

struct Query
{
int idx;
int left;
int right;
int ans;
int k;

void input (int id)
{
idx = id;
scanf ("%d%d%d", &left, &right, &k);
}
};

bool cmpLeft (const Query& A, const Query& B)
{
return A.left < B.left;
}

bool cmpIdx (const Query& A, const Query& B)
{
return A.idx < B.idx;
}

const int maxN = 100005;
const int maxM = 50005;

int val[maxN];
Query qry[maxM];
int N;
int M;

void input()
{
scanf ("%d%d", &N, &M);
for (int i = 1; i <= N; i++) scanf ("%d", val + i);
for (int i = 1; i <= M; i++) qry[i].input (i);
}

void solve()
{
Treap trp;
std::sort (qry + 1, qry + M + 1, cmpLeft);
int curL = qry[1].left;
int curR = qry[1].right;
for (int i = curL; i <= curR; i++) trp.insert (val[i]);

for (int i = 1; i <= M; i++)
{
for (; curL < qry[i].left; curL++) trp.erase (val[curL]);
for (; curR < qry[i].right; curR++) trp.insert (val[curR + 1]);
qry[i].ans = trp.getKth (qry[i].k);
}

std::sort (qry + 1, qry + M + 1, cmpIdx);
for (int i = 1; i <= M; i++) printf ("%d\n", qry[i].ans);
}

int main()
{
srand (time (0));
input();
solve();
return 0;
}

留一个划分树代码

#include <bits/stdc++.h>
using namespace std;

//#define scanf scanf_s
typedef long long ll;

ll sor[100005];
int n, m;
ll tree[30][100005];
int lp[30][100005], rp[30][100005];
//int md[20];

void build_tree(int lev, const int l, const int r)
{
    if (l >= r) return;
    ll mid = sor[(l + r) >> 1];
    //md[lev] = mid;
    int i = l, j = ((l + r) >> 1) + 1;
    for (int k = l; k <= r; k++) {
        if (tree[lev][k] <= mid) {
            tree[lev + 1][i] = tree[lev][k];
            lp[lev][k] = i; rp[lev][k] = j;
            i++;
        }
        else {
            tree[lev + 1][j] = tree[lev][k];
            lp[lev][k] = i; rp[lev][k] = j;
            j++;
        }
    }
    build_tree(lev + 1, l, ((l + r) >> 1));
    build_tree(lev + 1, ((l + r) >> 1) + 1, r);
}

ll query(int lev, int l, int r, int k, int lr = 1, int rr = n)
{
    //if (l > r) r++;
    //printf("lev : %d, [%d, %d, %d, %d, %d]\n", lev, l, r, k, lr, rr);
    if (l == r) return tree[lev][l];
    ll mid = sor[(lr + rr) >> 1];
    int ls = lp[lev][l], le = lp[lev][r] - 1; if (tree[lev][r] <= mid) le++;//if (tree[lev + 1][le + 1] == tree[lev][r] && lp[lev + 1][le + 1] != 0) le++;
    int lnum = le - ls + 1;
    int rs = rp[lev][l], re = rp[lev][r] - 1; if (tree[lev][r] > mid) re++;//if (tree[lev + 1][re + 1] == tree[lev][r] && lp[lev + 1][re + 1] != 0) re++;
    //int rnum = re - rs + 1;
    if (lnum >= k)
        return query(lev + 1, ls, le, k, lr, (lr + rr) >> 1);
    else
        return query(lev + 1, rs, re, k - lnum, ((lr + rr) >> 1) + 1, rr);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(tree, 0, sizeof tree);
    memset(lp, 0, sizeof lp);
    memset(rp, 0, sizeof rp);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &tree[0][i]);
        (tree[0][i] *= (n + 1)) += i;
        if (tree[0][i] < 0) tree[0][i] -= 2*i;
        //cout << tree[0][i] << " ";
        sor[i] = tree[0][i];
    }
    //puts("");
    sort(sor + 1, sor + n + 1);
    build_tree(0, 1, n);
    for (int i = 1; i <= m; i++) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%lld\n", query(0, l, r, k)/(n+1));
    }
    //while (1);
    return 0;
}

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <queue>

#include <vector>

#include <cctype>

#include <cstdio>

#include <string>

#include <cstring>

#include <sstream>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define pb push_back

#define mp make_pair

#define fillchar(a, x) memset(a, x, sizeof(a))

#define copy(a, b) memcpy(a, b, sizeof(a))

typedef long long LL;

typedef pair<int, int > PII;

typedef unsigned long long uLL;

template<typename T>

void print(T* p, T* q, string Gap = " ") {

int d = p < q ? 1 : -1;

while(p != q) {

cout << *p;

p += d;

if(p != q) cout << Gap;

}

cout << endl;

}

template<typename T>

void print(const T &a, string bes = "") {

int len = bes.length();

if(len >= 2)cout << bes[0] << a << bes[1] << endl;

else cout << a << endl;

}

const int INF = 0x3f3f3f3f;

const int MAXM = 1e5;

const int MAXN = 1e5 + 5;

LL sum[20][MAXN];

int tree[20][MAXN], sorted[MAXN];

int N, M, I, J, K;

void build(int rt, int l, int r) {

int mid = (l + r) >> 1, p = l, q = mid + 1, same = mid - l + 1;
for(int i = l; i <= mid ; i ++) {
if(sorted[i] < sorted[mid]) same --;

}

for(int i = l; i <= r; i ++) {

if(i == l) {

sum[rt][i] = 0;

} else {

sum[rt][i] = sum[rt][i - 1];

}

if(tree[rt][i] == sorted[mid]) {

if(same) {
same --;

sum[rt][i] ++;

tree[rt + 1][p ++] = tree[rt][i];

} else {

tree[rt + 1][q ++] = tree[rt][i];

}

} else if(tree[rt][i] < sorted[mid]) {

sum[rt][i] ++;

tree[rt + 1][p ++] = tree[rt][i];

} else {

tree[rt + 1][q ++] = tree[rt][i];

}

}

if(l == r) return;

build(rt + 1, l, mid);

build(rt + 1, mid + 1, r);

}

int query(int rt,int l, int r, int L, int R, int k) {

int s, ss, mid = (l + r) >> 1;

if(l == r) return tree[rt][l];

if(l == L) {

s = 0, ss = sum[rt][R];

} else {

s = sum[rt][L - 1];

ss = sum[rt][R] - s;

}

if(k <= ss) {

return query(rt + 1, l, mid, l + s, l + s + ss - 1, k);
} else {

return query(rt + 1, mid + 1, r, mid + 1 + L - l - s, mid + 1 + R - l - s - ss, k - ss);
}

}

int main() {

while(cin >> N >> M) {

for(int i = 1 ; i <= N ; i ++) {

cin >> sorted[i];

tree[0][i] = sorted[i];

}

sort(sorted + 1, sorted + N + 1);

build(0, 1, N);

while(M --) {

cin >> I >> J >> K;

print(query(0, 1, N, I, J, K));

}

}

return 0;

}

可持久化0-1Trie即可。

C++ Code

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
void init(){
#ifdef LOCAL
freopen("1081.txt","r",stdin);
#endif // LOCAL
buf[fread(buf,1,MAXSIZE,stdin)]='\0';
bufpos=0;
}
int readint(){
int val=0;
for(;!isdigit(buf[bufpos]);bufpos++);
for(;isdigit(buf[bufpos]);bufpos++)
val=val*10+buf[bufpos]-'0';
return val;
}
struct trie{
static const int maxw=16;
static const int maxt=18*100000+1;
static const int maxv=100001;
struct node{
int val,sz;
int ch[2];
node(){
val=sz=ch[0]=ch[1]=0;
}
node operator =(const node& rhs){
val=rhs.val;
sz=rhs.sz;
ch[0]=rhs.ch[0];
ch[1]=rhs.ch[1];
return *this;
}
};
trie(){
ver=cur=0;
}
int ver,cur;
node t[maxt];
int root[maxv];
void ins(int x){
t[++cur]=t[root[ver]];
t[cur].sz++;
root[++ver]=cur;
int now=cur;
for(int i=maxw;i>=0;i--){
int v=(x&(1<<i))?1:0;
cur++;
t[cur]=t[t[now].ch[v]];
t[cur].sz++;
t[now].ch[v]=cur;
now=cur;
}
t[now].val=x;
}
int query(int l,int r,int k){
int lnow=root[l-1],rnow=root[r];
for(int i=maxw;i>=0;i--){
int sz=t[t[rnow].ch[0]].sz-t[t[lnow].ch[0]].sz;
if(sz>=k){
lnow=t[lnow].ch[0];
rnow=t[rnow].ch[0];
}
else {
k-=sz;
lnow=t[lnow].ch[1];
rnow=t[rnow].ch[1];
}
}
return t[rnow].val;
}
}t;
int a[100001],b[100001];
int main(){
init();
int n=readint(),m=readint();
for(int i=1;i<=n;i++){
a[i]=b[i]=readint();
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+n+1,a[i])-b;
for(int i=1;i<=n;i++)
t.ins(a[i]);
for(int i=1;i<=m;i++){
int l=readint(),r=readint(),k=readint();
printf("%d\n",b[t.query(l,r,k)]);
}
}

评测状态 Accepted
题目 P1081 野生动物园
递交时间 2016-01-19 21:23:18
代码语言 C++
评测机 VijosEx
消耗时间 1923 ms
消耗内存 40596 KiB
评测时间 2016-01-19 21:23:24
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 40592 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 40596 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 40596 KiB, score = 10
测试数据 #3: Accepted, time = 23 ms, mem = 40588 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 40596 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 40592 KiB, score = 10
测试数据 #6: Accepted, time = 234 ms, mem = 40596 KiB, score = 10
测试数据 #7: Accepted, time = 374 ms, mem = 40588 KiB, score = 10
测试数据 #8: Accepted, time = 561 ms, mem = 40592 KiB, score = 10
测试数据 #9: Accepted, time = 577 ms, mem = 40596 KiB, score = 10
Accepted, time = 1923 ms, mem = 40596 KiB, score = 100
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int maxn=100010;

struct Q{
int l,r,a,b,sum;
}tr[maxn*20];

int fir[maxn],cnt;
int n,k,Sot[maxn],h[maxn],pos;

void Build(int a,int b,int &rt)
{
int md=(a+b)>>1;
rt=++cnt;
tr[rt].a=a;
tr[rt].b=b;
if(a==b)return;
Build(a,md,tr[rt].l);
Build(md+1,b,tr[rt].r);
}

void Add(int pre,int &rt,int a,int b)
{
rt=++cnt;
tr[rt].l=tr[pre].l;
tr[rt].r=tr[pre].r;
tr[rt].a=tr[pre].a;
tr[rt].b=tr[pre].b;

tr[rt].sum=tr[pre].sum+1;

if(a<b){
int md=(a+b)>>1;

if(pos<=md)Add(tr[pre].l,tr[rt].l,a,md);
else Add(tr[pre].r,tr[rt].r,md+1,b);
}
}
#define Cmp(x) tr[tr[x].l].sum
int Query(int pre,int rt,int a,int b,int K)
{
if(a==b) return Sot[a];

int md=(a+b)>>1;

int D=Cmp(rt)-Cmp(pre);
if(D<K){
return Query(tr[pre].r,tr[rt].r,md+1,b,K-D);
}
else{
return Query(tr[pre].l,tr[rt].l,a,md,K);
}
}

int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;Sot[i]=h[i],i++)scanf("%d",&h[i]);
sort(Sot+1,Sot+n+1);
Build(1,n,fir[0]);
for(int i=1;i<=n;i++){
pos=lower_bound(Sot+1,Sot+n+1,h[i])-Sot;
Add(fir[i-1],fir[i],1,n);
}
for(int i=1;i<=k;i++)
{
int l,r,ks;
scanf("%d%d%d",&l,&r,&ks);
printf("%d\n",Query(fir[l-1],fir[r],1,n,ks));
}
return 0;
}

主席树轻松撸过。还有POJ2104和2761.
#include<iostream>
#include<cstdio>
#include<algorithm>
#define mid (l+r)/2
#define maxn 100010
#define maxm 2000000
using namespace std;
int da[maxn],b[maxn],tr[maxm],lc[maxm],rc[maxm],n,root[maxn],cnt;
int find(int x){
int l=1,r=n;

while(l<=r){
int m=mid;
if(da[m]==x)return m;
if(da[m]<x)l=m+1;
else r=m-1;
}
}
void update(int oo,int &o,int l,int r,int x){
o=++cnt;
if(l==r){
tr[o]=tr[oo]+1;
return;
}
int m=mid;
if(x<=m){
rc[o]=rc[oo];
update(lc[oo],lc[o],l,m,x);
}else{
lc[o]=lc[oo];
update(rc[oo],rc[o],m+1,r,x);
}
tr[o]=tr[lc[o]]+tr[rc[o]];
}
int query(int k,int o1,int o2,int l,int r){
if(l==r){
return da[l];
}
int m=mid;
if(k<=tr[lc[o2]]-tr[lc[o1]]&&tr[lc[o2]]>tr[lc[o1]]){
return query(k,lc[o1],lc[o2],l,m);
}else{
return query(k+tr[lc[o1]]-tr[lc[o2]],rc[o1],rc[o2],m+1,r);
}
}
bool cmp(int a,int b){
return a>b;
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&da[i]);
b[i]=da[i];
}

sort(da+1,da+n+1);
for(int i=1;i<=n;i++){
update(root[i-1],root[i],1,n,find(b[i]));
}

while(m--){
int i,j,k;
scanf("%d%d%d",&i,&j,&k);
printf("%d\n",query(k,root[i-1],root[j],1,n));
}
return 0;
}

刚学的划分树……无比丑陋的代码：
###BLOCK
var
x,y,z,len,i,j,k,m,n:longint;
sum,tree:array[0..20,0..100000] of longint;
he,left,right,l,r:array[1..300000] of longint;
a:array[1..100000,0..1] of longint;
v:array[1..100000] of 0..1;
procedure sort(h,t:longint);
var
i,j,x,y,k:longint;
begin
x:=a[(h+t)div 2,0];
y:=a[(h+t)div 2,1];
i:=h;j:=t;
repeat
while (a[i,0]<x) or ((a[i,0]=x)and(a[i,1]<y)) do
inc(i);
while (a[j,0]>x) or ((a[j,0]=x)and(a[j,1]>y)) do
dec(j);
if i<=j then begin
k:=a[i,0];a[i,0]:=a[j,0];a[j,0]:=k;
k:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=k;
inc(i);
dec(j);
end;
until i>j;
if i<t then sort(i,t);
if j>h then sort(h,j);
end;
procedure build(root,ll,rr,h:longint);
begin
l[root]:=ll;
r[root]:=rr;
he[root]:=h;
if ll<>rr then begin
inc(len);
left[root]:=len;
build(len,ll,(ll+rr)div 2,h+1);
inc(len);
right[root]:=len;
build(len,(ll+rr)div 2+1,rr,h+1);
end;
end;
procedure divide_h(root:longint);
var
i,j,s:longint;
begin
if l[root]=r[root] then exit;
for i:=l[root] to r[root] do v[i]:=0;
for i:=l[root] to r[root] do
begin
a[i,0]:=tree[he[root],i];
a[i,1]:=i;
end;
sort(l[root],r[root]);
for i:=l[root] to (l[root]+r[root])div 2 do
v[a[i,1]]:=1;
s:=0;j:=0;
for i:=l[root] to r[root] do
if v[i]=1 then begin
tree[he[root]+1,l[root]+s]:=tree[he[root],i];
inc(s);sum[he[root],i]:=s;
end
else begin
tree[he[root]+1,(l[root]+r[root])div 2+1+j]:=tree[he[root],i];
inc(j);sum[he[root],i]:=s;
end;
if left[root]<>0 then divide_h(left[root]);
if right[root]<>0 then divide_h(right[root]);
end;
function kthnum(root,ll,rr,k:longint):longint;
var
i,j,x:longint;
begin
if l[root]=r[root] then exit(tree[he[root],l[root]]);
if ll-1<l[root] then x:=0
else x:=sum[he[root],ll-1];
if k<=sum[he[root],rr]-x then exit(kthnum(left[root],l[left[root]]+x,l[left[root]]+sum[he[root],rr]-1,k))
else exit(kthnum(right[root],l[right[root]]+ll-l[root]-x,r[right[root]]-((r[root]-rr)-(sum[he[root],r[root]]-sum[he[root],rr])),k-(sum[he[root],rr]-x)))
end;
begin
readln(n,m);
fillchar(sum,sizeof(sum),0);
fillchar(tree,sizeof(tree),0);
fillchar(left,sizeof(left),0);
fillchar(right,sizeof(right),0);
fillchar(l,sizeof(l),0);
fillchar(r,sizeof(r),0);
len:=1;
build(1,1,n,0);

for i:=1 to n do
read(tree[0,i]);
divide_h(1);
for i:=1 to m do
begin
readln(x,y,z);
writeln(kthnum(1,x,y,z));
end;
end.

不会写划分树啊，有时间学学吧。写了个Treap
时间有点慢啊
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1888 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1940 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2120 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2260 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 2356 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 2820 KiB, score = 10
测试数据 #6: Accepted, time = 156 ms, mem = 3764 KiB, score = 10
测试数据 #7: Accepted, time = 281 ms, mem = 5640 KiB, score = 10
测试数据 #8: Accepted, time = 421 ms, mem = 6580 KiB, score = 10
测试数据 #9: Accepted, time = 453 ms, mem = 6580 KiB, score = 10
Accepted, time = 1434 ms, mem = 6580 KiB, score = 100

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
#define _MAX 50010
using namespace std;

struct ComplexAsk{
int l,r,k;
int from;
bool operator <(const ComplexAsk& a)const{
return l<a.l;
}
}asks[_MAX];
struct Complex{
int random,val,cnt,size;
Complex* son[2];
Complex(){
random=rand();
cnt=size=1;
son[0]=son[1]=NULL;
}
inline void Maintain(){
size=cnt;
if(son[0]!=NULL) size+=son[0]->size;
if(son[1]!=NULL) size+=son[1]->size;
}
inline int Compare(int x){
if(x==val) return -1;
return x>val;
}
}*root;

int total,step;
int source[MAX];
int ans[_MAX];

inline void Rotate(Complex*& a,int dir);
void Insert(Complex*& a,int x);
void Delete(Complex*& a,int x);
int FindK(Complex*& a,int k);

int main()
{
cin>>total>>step;
for(int i=1;i<=total;i++)
scanf("%d",&source[i]);
for(int i=1;i<=step;i++)
scanf("%d%d%d",&asks[i].l,&asks[i].r,&asks[i].k),asks[i].from=i;
sort(asks+1,asks+step+1);
for(int i=1;i<=step;i++){
if(asks[i-1].r>=asks[i].l){
for(int j=asks[i-1].l;j<asks[i].l;j++)
Delete(root,source[j]);
for(int j=asks[i-1].r+1;j<=asks[i].r;j++)
Insert(root,source[j]);
}
else{
if(i-1)
for(int j=asks[i-1].l;j<=asks[i-1].r;j++)
Delete(root,source[j]);
for(int j=asks[i].l;j<=asks[i].r;j++)
Insert(root,source[j]);
}
ans[asks[i].from]=FindK(root,asks[i].k);
}
for(int i=1;i<=step;i++)
printf("%d\n",ans[i]);
return 0;
}

inline void Rotate(Complex*& a,int dir)
{
Complex* k=a->son[dir^1];
a->son[dir^1]=k->son[dir];
k->son[dir]=a;
a->Maintain(),k->Maintain();
a=k;
}

void Insert(Complex*& a,int x)
{
if(a==NULL){
a=new Complex();
a->val=x;
return ;
}
int dir=a->Compare(x);
if(dir==-1)
a->cnt++;
else{
Insert(a->son[dir],x);
if(a->son[dir]->random > a->random)
Rotate(a,dir^1);
}
a->Maintain();
}

void Delete(Complex*& a,int x)
{
int dir=a->Compare(x);
if(dir!=-1)
Delete(a->son[dir],x);
else{
if(a->cnt > 1)
a->cnt--;
else{
if(a->son[0]==NULL)
a=a->son[1];
else if(a->son[1]==NULL)
a=a->son[0];
else{
int _dir=(a->son[0]->random > a->son[1]->random);
Rotate(a,_dir);
Delete(a->son[_dir],x);
}
}
}
if(a!=NULL) a->Maintain();
}

int FindK(Complex*& a,int k)
{
int t=0;
if(a->son[0]!=NULL)
t=a->son[0]->size;
if(k<=t)
return FindK(a->son[0],k);
if(k>t+a->cnt)
return FindK(a->son[1],k-t-a->cnt);
return a->val;
}

测试数据 #0: Accepted, time = 0 ms, mem = 8560 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8560 KiB, score = 10
测试数据 #2: Accepted, time = 3 ms, mem = 8560 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 8556 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 8556 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 8560 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 8560 KiB, score = 10
测试数据 #7: Accepted, time = 171 ms, mem = 8560 KiB, score = 10
测试数据 #8: Accepted, time = 312 ms, mem = 8556 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 8560 KiB, score = 10

划分树党RE记得注意(1,1)之类的划分子树情况，最好使用随机划分，否则有可能出现用中位数划分恰好死循环情况，就是无限RE。
再贴个主席树代码（略慢）：
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2468 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 3032 KiB, score = 10
测试数据 #2: Accepted, time = 62 ms, mem = 6036 KiB, score = 10
测试数据 #3: Accepted, time = 109 ms, mem = 8428 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 10120 KiB, score = 10
测试数据 #5: Accepted, time = 359 ms, mem = 18764 KiB, score = 10
测试数据 #6: Accepted, time = 671 ms, mem = 36944 KiB, score = 10
测试数据 #7: Accepted, time = 1515 ms, mem = 75188 KiB, score = 10
测试数据 #8: Accepted, time = 1890 ms, mem = 94900 KiB, score = 10
测试数据 #9: Accepted, time = 1843 ms, mem = 94900 KiB, score = 10
Accepted, time = 6620 ms, mem = 94900 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 100001

struct node {
node *left,*right;
int l,r,s;
node (){
left=right=NULL;
}
} *t[MAXN];

int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int n,m;

bool cmp(int x,int y){
return x<y;
}

void Build0(int l,int r,node *t){
t->l=l;
t->r=r;
t->s=0;
if (l==r){
return ;
}
Build0(l,(l+r)>>1,t->left=new(node));
Build0(((l+r)>>1)+1,r,t->right=new(node));
}

void Build(int x,node *p,node *t){
t->l=p->l;
t->r=p->r;
t->s=p->s+1;
if (p->l==p->r) return ;
int mid=(p->l+p->r)>>1;
if (x<=mid) {
t->right=p->right;
Build(x,p->left,t->left=new(node));
} else {
t->left=p->left;
Build(x,p->right,t->right=new(node));
}
}

int Find(int x){
int l=1,r=c[0];
if (x==c[1]) return 1;
if (x==c[c[0]]) return c[0];
while (l<r){
int mid=(l+r)>>1;
if (c[mid]==x) return mid;
if (c[mid]<x) l=mid; else r=mid;
}
return l;
}

int main(){
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1,cmp);
memset(d,0,sizeof(d));
c[0]=0;
c[++c[0]]=b[1];
d[1]=1;
for (int i=1;i++<n;){
if (b[i]!=b[i-1]){
c[++c[0]]=b[i];
d[c[0]]=1;
} else d[c[0]]++;
}
Build0(1,c[0],t[0]=new(node));
for (int i=0;i++<n;){
int x=Find(a[i]);
Build(x,t[i-1],t[i]=new(node));
}
while (m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
node *lt=t[l-1],*rt=t[r];
while (lt->l!=rt->r){
if (rt->left->s - lt->left->s <= k-1){
k-=(rt->left->s-lt->left->s);
rt=rt->right;
lt=lt->right;
} else {
rt=rt->left;
lt=lt->left;
}
}
printf("%d\n",c[lt->l]);
}
return 0;
}

在RUNTIME ERROR了N次之后果断打了随机化的划分树 终于A了 还是略慢
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 78840 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 78940 KiB, score = 10
测试数据 #2: Accepted, time = 19 ms, mem = 79376 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 79708 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 79924 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 81024 KiB, score = 10
测试数据 #6: Accepted, time = 171 ms, mem = 83224 KiB, score = 10
测试数据 #7: Accepted, time = 359 ms, mem = 87620 KiB, score = 10
测试数据 #8: Accepted, time = 484 ms, mem = 89812 KiB, score = 10
测试数据 #9: Accepted, time = 484 ms, mem = 89812 KiB, score = 10
Accepted, time = 1655 ms, mem = 89812 KiB, score = 100
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define MAXN 100001
#define MAXD 100

struct node {
node *left_child,*right_child;
int l,r;
int MID,mid;
int depth;
bool flag0;
};

node *roof;

int a[MAXD][MAXN];
int f[MAXD][MAXN];

int n,m;

int get_random(int l,int r){
int x=0;
for (int i=0;i++<5;){
x+=rand();
}
x%=(r-l+1);
x+=l;
return x;
}

int get_f(int x,node *p){
if (x<(*p).l){
return 0;
}
return f[(*p).depth][x];
}

int Build(int l,int r,int depth,node *p){
(*p).l=l;
(*p).r=r;
(*p).depth=depth;
(*p).flag0=false;
if (l==r){
(*p).MID=a[depth][l];
(*p).mid=l;
return 0;
}
bool flag=true;
for (int i=l;i++<r;){
if (a[depth][i]!=a[depth][i-1]){
flag=false;
break;
}
}
if (flag){
(*p).flag0=true;
(*p).MID=a[depth][l];
return 0;
}
while (1){
(*p).MID=a[depth][get_random(l,r)];
(*p).mid=l;
for (int i=l;i<=r;i++){
if (a[depth][i]<=(*p).MID){
a[depth+1][(*p).mid++]=a[depth][i];
f[depth][i]=get_f(i-1,p)+1;
} else {
f[depth][i]=get_f(i-1,p);
}
}
int j=((*p).mid--);
if ((*p).mid>=r){
continue;
}
for (int i=l;i<=r;i++){
if (a[depth][i]>(*p).MID){
a[depth+1][j++]=a[depth][i];
}
}
break;
}
Build(l,(*p).mid,depth+1,(*p).left_child=new(node));
Build((*p).mid+1,r,depth+1,(*p).right_child=new(node));
return 0;
}

int find(int l,int r,int k,node *p){
if ((*p).l==(*p).r||(*p).flag0){
return (*p).MID;
}
if ((*p).flag0){
return a[(*p).depth][l+k-1];
}
int left_s=get_f(r,p)-get_f(l-1,p);
int right_s=(r-l+1)-left_s;
int left_=(*p).l+get_f(l-1,p);
int right_=(*p).mid+(l-(*p).l)-get_f(l-1,p)+1;
if (k<=left_s) return find(left_,left_+left_s-1,k,(*p).left_child);
return find(right_,right_+right_s-1,k-left_s,(*p).right_child);
}

int main(){
// freopen("input.txt","r",stdin);
srand(0);
memset(f,sizeof(f),0);
memset(a,sizeof(a),0);
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[0][i]);
}
Build(1,n,0,roof=new(node));
while (m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",find(l,r,k,roof));
}
return 0;
}

划分树无压力
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define N 100001
#define Max_Deep 30
#define array vector<int>
using namespace std;
typedef struct
{
int l,r,lc,rc,m,d;
}node;
node tree[3*N];
array a(1);
int n,q,size=0,sorted[N];
int sum[Max_Deep][N];
void build(int cur,int L,int R,array A,int deep)
{
tree[cur].l=L;
tree[cur].r=R;
tree[cur].d=deep;
if (L==R) return;
int i,M=(L+R)>>1,mid=sorted[M],lct=0;
array tl(1),tr(1),flag(1);
for (i=1;i<=A.size()-1;i++)
{
if (A[i]<mid) {flag.push_back(1);lct++;}
if (A[i]>mid) flag.push_back(2);
if (A[i]==mid) flag.push_back(0);
}
int con=((R-L+1)>>1)-lct;
for (i=1;i<=A.size()-1;i++)
if (flag[i]==0)
{
if (con>0) {flag[i]=1;con--;}
else flag[i]=2;
}
int temp=sum[deep][L-1];
sum[deep][L-1]=0;
tree[cur].m=L-1;
for (i=1;i<=A.size()-1;i++)
{
if (flag[i]==1)
{
tree[cur].m++;
tl.push_back(A[i]);
sum[deep][L+i-1]=sum[deep][L+i-2]+1;
} else
{
tr.push_back(A[i]);
sum[deep][L+i-1]=sum[deep][L+i-2];
}
}
sum[deep][L-1]=temp;
size++;
tree[cur].lc=size;
build(size,L,tree[cur].m,tl,deep+1);
size++;
tree[cur].rc=size;
build(size,tree[cur].m+1,R,tr,deep+1);
}
int query(int cur,int L,int R,int k)
{
if (tree[cur].lc==0) return sorted[L];
int left=tree[cur].l,deep=tree[cur].d,temp;
if (L==left) temp=0; else temp=sum[deep][L-1];
int s=sum[deep][R]-temp;
int M=tree[cur].m;
if (k<=s)
return query(tree[cur].lc,left+temp,left+sum[deep][R]-1,k);
else
return query(tree[cur].rc,M+L-left+1-temp,M+R-left+1-sum[deep][R],k-s);

}
int main()
{
scanf("%d %d",&n,&q);
int i,t,l,r,k;
for (i=1;i<=n;i++)
{
scanf("%d",&t);
a.push_back(t);
sorted[i]=t;
}
sort(sorted+1,sorted+n+1);
build(0,1,n,a,1);
for (i=1;i<=q;i++)
{
scanf("%d %d %d",&l,&r,&k);
printf("%d\n",query(0,l,r,k));
}
return 0;
}

标准划分树代码啊，居然只得10分。。其他全部RE- -
没办法了- -
const
maxn=100010;
type
rec=record
mid,left,right:longint;
end;
var
n,m,lt,rt:longint;
b:array[0..maxn]of longint;
tree:array[0..maxn*5]of rec;
lnum:array[0..20,0..maxn]of longint;
g:array[0..20,0..maxn]of longint;
procedure init;
var
i:longint;
begin
read(n,m);
for i:=1 to n do
begin
read(g[0,i]);
b[i]:=g[0,i];
end;
end;
procedure qsort(l,r:Longint);
var
m,i,j,k:Longint;
begin
i:=l;j:=r;
m:=b[(l+r) shr 1];
repeat
while b[i]<m do inc(i);
while b[j]>m do dec(j);
if i<=j then
begin
k:=b[i];b[i]:=b[j];b[j]:=k;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
procedure setup(x,l,r,dep:longint);
var
i:longint;
begin
with tree[x] do
begin
left:=l;
right:=r;
mid:=(l+r)shr 1;
if l=r then exit;
lt:=l-1;
rt:=mid;
for i:=l to r do
if (g[dep-1,i]<=b[mid])and(lt<mid)
then
begin
inc(lt);
g[dep,lt]:=g[dep-1,i];
if i-1<l then
lnum[dep,i]:=1
else
lnum[dep,i]:=lnum[dep,i-1]+1;
end
else
begin
inc(rt);
g[dep,rt]:=g[dep-1,i];
if i=l-1 then lnum[dep,i]:=0
else
lnum[dep,i]:=lnum[dep,i-1];
end;
setup(x*2,l,mid,dep+1);
setup(x*2+1,mid+1,r,dep+1);
end;
end;
function find(x,l,r,kth,dep:Longint):Longint;
var
tlnum,t1,t2,ll,rr:Longint;
begin
if (l=tree[x].left)and(r=tree[x].right) then
exit(b[l+kth-1]);
t1:=lnum[dep,r];
if l-1<tree[x].left then t2:=0
else
t2:=lnum[dep,l-1];
tlnum:=t1-t2;
if kth<=tlnum then
begin
ll:=tree[x].left+t2;
rr:=ll+tlnum-1;
exit(find(x*2,ll,rr,kth,dep+1));
end
else
begin
ll:=tree[x].mid+1+l-tree[x].left-t2;
rr:=r-l-tlnum+ll;
exit(find(x*2+1,ll,rr,kth-tlnum,dep+1));
end;
end;

procedure main;
var
i,x,y,z,p:Longint;
begin
for i:=1 to m do
begin
if (y>n) then y:=n;
if (x<1) then x:=1;
if x>y then begin p:=x;x:=y;y:=p;end;
read(x,y,z);
writeln(find(1,x,y,z,1));
end;
end;
begin
init;
qsort(1,n);
setup(1,1,n,1);
main;
end.

无限RE是什么情况- -交了无数次了

点击查看程序源码+详细题解