两个月前打了个主席树……今天又打了个线段树合并，发现线段树合并的代码挺短的……（其实也差不多）
主席树：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100010
using namespace std;
int A[maxn],b[maxn],n,m;
struct array
{
int x,id;
}a[maxn];
bool cmp(array u,array v) {return u.x<v.x;}
struct tree
{
int val,lc,rc;
}tr[maxn*20];
int len=0,root[maxn];
void build(int l,int r)
{
int t=++len;
tr[t].val=0;
if(l<r)
{
int mid=l+r>>1;
tr[t].lc=len+1;build(l,mid);
tr[t].rc=len+1;build(mid+1,r);
}
}
void update(int last,int l,int r,int k)
{
int now=++len;
tr[now]=tr[last];
if(l==r) {tr[now].val++;return;}
int mid=l+r>>1;
if(k<=mid)
{
tr[now].lc=len+1;
update(tr[last].lc,l,mid,k);
}
else
{
tr[now].rc=len+1;
update(tr[last].rc,mid+1,r,k);
}
tr[now].val=tr[tr[now].lc].val+tr[tr[now].rc].val;
}
int query(int l,int r,int L,int R,int k)
{
if(l==r) return A[l];
int mid=l+r>>1,tt=tr[tr[R].lc].val-tr[tr[L].lc].val;
if(k<=tt) return query(l,mid,tr[L].lc,tr[R].lc,k);
else return query(mid+1,r,tr[L].rc,tr[R].rc,k-tt);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i,A[i]=a[i].x;
build(1,n);root[0]=1;
sort(a+1,a+1+n,cmp);sort(A+1,A+1+n);for(int i=1;i<=n;i++) b[a[i].id]=i;
for(int i=1;i<=n;i++) root[i]=len+1,update(root[i-1],1,n,b[i]);
for(int i=1;i<=m;i++)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",query(1,n,root[x-1],root[y],k));
}
}
线段树合并：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,a[maxn];
struct tyb{int x,id;}A[maxn];
bool cmp(tyb x,tyb y){return x.x<y.x;}
int val[maxn*25],lc[maxn*25],rc[maxn*25],root[maxn],cnt=0,number[maxn];
void build(int &u,int l,int r,int x)
{
if(!u)u=++cnt;
val[u]++;
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)build(lc[u],l,mid,x);
else build(rc[u],mid+1,r,x);
}
void merge(int &u1,int u2)
{
if(!u1){u1=u2;return;}
if(!u2)return;
val[u1]+=val[u2];
merge(lc[u1],lc[u2]);
merge(rc[u1],rc[u2]);
}
int query(int r1,int r2,int l,int r,int k)
{
if(l==r)return number[l];
int c=val[lc[r1]]-val[lc[r2]],mid=(l+r)>>1;
if(k<=c) return query(lc[r1],lc[r2],l,mid,k);
else return query(rc[r1],rc[r2],mid+1,r,k-c);
}
void mem()
{
memset(lc,0,sizeof(lc));
memset(rc,0,sizeof(rc));
memset(val,0,sizeof(val));
memset(root,0,sizeof(root));
}
int main()
{
mem();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&A[i].x),A[i].id=i,number[i]=A[i].x;
sort(A+1,A+1+n,cmp);sort(number+1,number+1+n);
for(int i=1;i<=n;i++) a[A[i].id]=i;
for(int i=1;i<=n;i++)
{
build(root[i],1,n,a[i]);
merge(root[i],root[i-1]);
}
while(m--)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",query(root[y],root[x-1],1,n,k));
}
}