如果题目给出1e5的数据范围，，以前只会用n*log（n）的方法去想
今天学了一下两三种n*n*log(n)的数据结构
他们就是大名鼎鼎的 归并树 划分树 主席树，，，，
首先来说两个问题，，区间第k大 ，，，，
这个问题的通用算法是 划分树，，
说白一点就是把快速排序的中间结果存起来，
举个栗子
原数列 4 1 8 2 6 9 5 3 7
sorted 1 2 3 4 5 6 7 8 9
。。。。。。。。。。。。。。。。。。。。。。。。。。。
qs[0] 4 1 8 2 6 9 5 3 7
qs[1] 4 1 2 5 3.....8 6 9 7
qs[2] 1 2 3.....4 5......6 7.....8 9
qs[3] 1 2.....3.....4.....5......6......7.....8.....9
qs[4] 1.....2
快速排序的过程如上
我们要求【2,8】区间里第4小的数
我们可以很轻易的知道qs[0]中【2,8】中的数被快排分到左边的个数
记这个个数为 rs rs=4 rs>4 我们可以知道要的答案肯定不可能出现在下一次快排的右边，一定出现在快排的左边，我们只需要在左边查找便是了
在左边如何查找？？如果我们的快排是稳定的话（事实上是可以做到稳定的） 下一次查找的开始应该不包括【1,1】中在左边的数，也就是下一层的查询左界应该是( 1+【1,1】中被快排分到左边的个数)，有界应该是 (左界+【2,8】被快排分到左边的个数 -1)，放在上图就是在qs[1]中查找【2,5】中的第4小，
也就是在qs[1]的 [1,5]中查找【2,5】中的第4小
【2,5】被快排分到左边的个数是 3 3<4也就是说 我们要找的数不可能在左边，应该是在右边
而且应该是在右边找第 4-3 小的数 最小的数 右边查找的左界应该是 (mid+1 +【1,1】中被分到右边的个数)，而 查询的右界是 （左界 + 【2,5】中被分到右边的个数-1）
也就是在qs[2] 的 [4,5] 区间内查找【5,5】内的最小数。。这个数 就是 5了吧，。。。
我们可以用一个 sum[d][i] 来存储在快排深度为d时 区间内前i位被快排分到左边的数的个数；可以用o（1）的时间算出下次查找的区间
总的时间复杂都市n*log(n)*log(n)
以下是划分树的代码
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define MAXN 100005 typedef struct mydata
{
int p,v,h;
}D; int cmpv(D aa,D bb)
{
if(aa.v==bb.v)return aa.p<bb.p;
return aa.v<bb.v;
} int cmpp(D aa , D bb)
{
return aa.p<bb.p;
} D dat[MAXN];
int da[MAXN];
int sum[][MAXN];
int qso[][MAXN],n,m; void build(int l,int r,int c)
{
if(l==r)return ;
int mid=(l+r)/;
int i,cl=,cr=;
for(i=l;i<=r;i++)
{
if(qso[c][i]<=mid)
{
sum[c][i]=sum[c][i-]+;
qso[c+][l+cl]=qso[c][i];
++cl;
}
else
{
sum[c][i]=sum[c][i-];
qso[c+][mid++cr]=qso[c][i];
++cr;
}
if(i==l)sum[c][i]-=sum[c][i-];
}
build(l,mid,c+);
build(mid+,r,c+);
} int query(int d,int l,int r,int ql,int qr,int k)
{
if(l==r)return qso[d][l];
int mid=(l+r)/;
int sl=sum[d][ql-];
if(l==ql)sl=;
int sr=sum[d][qr];
int rs=sr-sl;
if(k<=rs)return query(d+,l,mid,l+sl,l+sr-,k);
return query(d+,mid+,r,mid++ql-l-sl,mid++qr-l-sr,k-rs);
} int main()
{
int tt;
cin>>tt;
while(tt--)
{
cl(sum,);
cl(qso,);
scanf("%d %d",&n,&m);
int i,j,k,l,r,x;
for(i=;i<=n;i++){
scanf("%d",&dat[i].v);
dat[i].p=i;
}
sort(dat+,dat+n+,cmpv);
for(i=;i<=n;i++)
{
dat[i].h=i;
da[i]=dat[i].v;
}
sort(dat+,dat++n,cmpp);
for(i=;i<=n;i++)qso[][i]=dat[i].h;
build(,n,);
for(i=;i<m;i++)
{
scanf("%d %d %d",&l,&r,&k);
int pos=query(,,n,l,r,k);
printf("%d\n",da[pos]);
}
}
return ;
}
这道题除了用划分树来做之外 还可以用可持久化线段树来做 貌似还可以用归并树来做
其实归并树就是划分树倒过来。。。。。。。。。。。。。。。。。
可持久化线段树---------------------“被一小撮不怀好意的人起了一个奇怪的名字”--主席树 哈哈
主席树的原理是 每次更新的时候。不是修改值 而是插入值。。
主席树的其他建模。。。。。我不是很清楚 只是弄懂了此题的建模。。
对于这种玄幻的数据结构，，我感觉我解释不清楚，，我觉得给我比较鲜明的一个提示是。。。。。。。每次更新是新建一条从根节点到目标节点的路劲。。对于没有修改的节点就用原先的，需要修改的就新插入。而需要插入的节点数是log(n)级的
这种数据结构的空间复杂度和时间复杂度都是o(n*log(n)*log(n))的
talk is cheap show you the code
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cstdio>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define MAXN 100005 int sum[MAXN*];
int ls[MAXN*];
int rs[MAXN*];
int num[MAXN],cn;
int has[MAXN],m,n,ch;
int root[MAXN]; int phash(int l,int r,int x)
{
if(l==r)return l;
int mid=(l+r)/;
if(has[mid]==x)return mid;
if(has[mid]>x)return phash(l,mid,x);
return phash(mid+,r,x);
} void build(int l,int r,int &tx)
{
tx=++cn;
sum[tx]=;
if(l==r)return ;
int mid=(l+r)/;
build(l,mid,ls[tx]);
build(mid+,r,rs[tx]);
} void inst(int pos,int l,int r,int last,int &tx)
{
tx=++cn;
sum[tx]=sum[last]+;
ls[tx]=ls[last];
rs[tx]=rs[last];
// cout<<l<<' '<<r<<endl;
if(l==r)return ;
int mid=(l+r)/;
if(pos<=mid)inst(pos,l,mid,ls[last],ls[tx]);
else inst(pos,mid+,r,rs[last],rs[tx]);
} int query(int l,int r,int k,int last,int tx)
{
if(l==r)return l;
int mid=(l+r)/;
int rum=sum[ls[tx]]-sum[ls[last]];
if(rum>=k)return query(l,mid,k,ls[last],ls[tx]);
else return query(mid+,r,k-rum,rs[last],rs[tx]);
} int main()
{
int tt;
cin>>tt;
while(tt--)
{
cl(ls,);
cl(rs,);
cl(sum,);
scanf("%d %d",&n,&m);
int i,j,k,l,r,x;
for(i=;i<=n;i++){
scanf("%d",&num[i]);
has[i]=num[i];
}
sort(has+,has++n);
i=;j=;
while(i<=n&&j<=n)
{
if(has[i]!=has[j])has[++i]=has[j++];
else j++;
}
ch=i;
cn=;
// cout<<ch<<endl;
build(,ch,root[]);
for(i=;i<=n;i++)
{
inst(phash(,ch,num[i]),,ch,root[i-],root[i]);
}
for(i=;i<m;i++)
{
scanf("%d %d %d",&l,&r,&x);
printf("%d\n",has[query(,ch,x,root[l-],root[r])]);
}
}
return ;
}
再多BB 两句 。。。划分树的可以很方便的求出区间第k大 而归并树可以很方便的求出区间比k大的数个数。。。想到了一道cf 的题，，，
而主席树这种玄幻的东西，，两个都可以做，，
最后引用这种玄幻的东西的作者的一句话
..这个东西是当初我弱不会划分树的时候写出来替代的一个玩意..被一小撮别有用心的人取了很奇怪的名字> < 想法是对原序列的每一个前缀[1..i]建立出一颗线段树维护值域上每个数的出现次数，然后发现这样的树是可以减的，然后就没有然后了