题目链接：poj2104
题目大意：求不带修改的区间第K小
题解：
整体二分
之前用主席树做了一下，刚学整体二分就用来练练手。
(可能会有人想看或者找主席树的代码。。所以待会都贴出来好了
分治，solve(head,tail,l,r)表示head~tail的询问的答案在l~r这个范围里。若某一询问区间内比mid=(l+r)>>1小的数超过了k(要查第k小)那么就说明这个询问的答案在[l,mid]上，于是就把这个询问划分到[l,mid]这个区间，反之则在[mid+1,r]上。统计某一区间内有多少个比mid小的数用树状数组来维护就好了。
感觉我学模板时候摸索出来的打法常数有点大啊[摊手
整体二分的代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 110000
#define inf 1e9
int ans[maxn],tol[maxn],tor[maxn];
struct node
{
int l,r,c,bz,id;
}q[maxn];int id[maxn];
int n,m,c[maxn],cur[maxn],tmp[maxn];
int lowbit(int x){return x&(-x);}
void change(int x,int k)
{
for (x;x<=n;x+=lowbit(x)) c[x]+=k;
}
int query(int x)
{
int ret=0;
for (x;x>0;x-=lowbit(x)) ret+=c[x];
return ret;
}
void solve(int head,int tail,int l,int r)
{
if (head>tail) return;
int i,lnum=0,rnum=0;
int mid=(l+r)>>1;
if (l==r)
{
for (i=head;i<=tail;i++)
if (q[id[i]].bz==2) ans[q[id[i]].id]=l;
return;
}
for (i=head;i<=tail;i++)
if (q[id[i]].bz==1 && q[id[i]].c<=mid) change(q[id[i]].l,1);
for (i=head;i<=tail;i++)
if (q[id[i]].bz==2)
{
tmp[id[i]]=0;
tmp[id[i]]=query(q[id[i]].r)-query(q[id[i]].l-1);
if (cur[id[i]]+tmp[id[i]]>=q[id[i]].c) tol[++lnum]=id[i];
else cur[id[i]]+=tmp[id[i]],tor[++rnum]=id[i];
}else
{
if (q[id[i]].c<=mid) tol[++lnum]=id[i];
else tor[++rnum]=id[i];
}
for (i=head;i<=tail;i++)
if (q[id[i]].bz==1 && q[id[i]].c<=mid) change(q[id[i]].l,-1);
for (i=0;i<lnum;i++) id[head+i]=tol[i+1];
for (i=0;i<rnum;i++) id[head+lnum+i]=tor[i+1];
solve(head,head+lnum-1,l,mid);
solve(head+lnum,tail,mid+1,r);
}
int main()
{
int i,ls;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d",&q[i].c);q[i].l=i;
q[i].bz=1;q[i].id=0;
}
for (i=1;i<=m;i++)
{
int t=i+n;
scanf("%d%d%d",&q[t].l,&q[t].r,&q[t].c);
q[t].bz=2;q[t].id=i;
}
for (i=1;i<=n+m;i++) cur[i]=0,id[i]=i;
solve(1,m+n,-inf,inf);
for (i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
主席树的：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 101000
struct tree
{
int l,r,lc,rc,c;
}tr[maxn*20];int trlen;
struct node
{
int x,nw,id,rt;
}a[maxn];int ys[maxn];
bool cmp1(node x,node y) {return (x.x<y.x);}
bool cmp2(node x,node y) {return (x.id<y.id);}
int add(int l,int r,int c)
{
trlen++;int now=trlen;
tr[now].l=l;tr[now].r=r;
tr[now].lc=tr[now].rc=-1;
tr[now].c=c;
return now;
}
void bt(int l,int r)
{
int now=add(l,r,0);
if (l<r)
{
int mid=(l+r)>>1;
tr[now].lc=trlen+1;bt(l,mid);
tr[now].rc=trlen+1;bt(mid+1,r);
}
}
void ins(int x,int y,int l,int r,int c)
{
int mid=(l+r)>>1;
tr[x].c=tr[y].c;
if (l==r) {tr[x].c++;return;}
tr[x].l=l;tr[x].r=r;
if (c<=mid)
{
tr[x].rc=tr[y].rc;
tr[x].lc=add(l,mid,0);
ins(tr[x].lc,tr[y].lc,l,mid,c);
}else
{
tr[x].lc=tr[y].lc;
tr[x].rc=add(mid+1,r,0);
ins(tr[x].rc,tr[y].rc,mid+1,r,c);
}tr[x].c++;
}
int query(int x,int y,int k)
{
int cnt=0;
if (tr[x].l==tr[x].r) return tr[x].l;
cnt=tr[tr[x].lc].c-tr[tr[y].lc].c;
if (cnt>=k) return query(tr[x].lc,tr[y].lc,k);
else return query(tr[x].rc,tr[y].rc,k-cnt);
}
int main()
{
int n,m,i,x,y,k;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].id=i;
}sort(a+1,a+1+n,cmp1);
for (i=1;i<=n;i++) {a[i].nw=i;ys[i]=a[i].x;}
sort(a+1,a+1+n,cmp2);
trlen=0;bt(1,n);
a[0].rt=1;
for (i=1;i<=n;i++)
{
a[i].rt=add(1,n,0);
ins(a[i].rt,a[i-1].rt,1,n,a[i].nw);
}
while (m--)
{
scanf("%d%d%d",&x,&y,&k);
printf("%d
",ys[query(a[y].rt,a[x-1].rt,k)]);
}
return 0;
}它们都有一个共同点：慢出天际！！！