用可持久化线段树做的

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,i,j,x,y,k,tot,pos,p,ans,c[maxn],root[maxn],h[maxn];
struct node{
int a,b,l,r,sum;

}tree[maxn*20];
bool cmp(int a, int b){
if (a<b) return true;
return false;
}
void build(int a, int b, int &rt){
int m;
rt=++tot;
tree[rt].a=a; tree[rt].b=b;
tree[rt].sum=0;
m=(a+b)>>1;
if (a<b){
build(a,m,tree[rt].l);
build(m+1,b,tree[rt].r);
}
}
void insert(int pre, int &rt){
rt=++tot;
tree[rt].a=tree[pre].a;
tree[rt].b=tree[pre].b;
tree[rt].sum=tree[pre].sum+1;
tree[rt].l=tree[pre].l;
tree[rt].r=tree[pre].r;
if (tree[pre].a<tree[pre].b){
if (pos<=(tree[pre].a+tree[pre].b)>>1) insert(tree[pre].l,tree[rt].l);
else insert(tree[pre].r,tree[rt].r);
}
}
void query(int pre, int now){
if (tree[now].a==tree[now].b){
ans=c[tree[now].a];
return;
}
int lsum=tree[tree[now].l].sum-tree[tree[pre].l].sum;
if (p<=lsum) query(tree[pre].l,tree[now].l);
else {
p-=lsum;
query(tree[pre].r,tree[now].r);
}
}
int main(){
scanf("%d%d", &n, &m);
for (i=1; i<=n; i++){
scanf("%d", &c[i]);
h[i]=c[i];
}
tot=0;
memset(root,0,sizeof(root));
sort(c+1,c+1+n);
int cnt=n;//unique(c+1,c+1+n)-c-1;
build(1,cnt,root[0]);
for (i=1; i<=n; i++){
h[i]=pos=lower_bound(c+1,c+1+cnt,h[i])-c;
insert(root[i-1],root[i]);
}
for (i=1; i<=m; i++){
scanf("%d%d%d", &x, &y, &p);
query(root[x-1],root[y]);
printf("%d\n",ans);
}
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1081
难度
7
分类
数据结构 | 平衡树 点击显示
标签
(无)
递交数
2474
已通过
384
通过率
16%
被复制
5
上传者