2山东大学ACM模板数据结构.docx
《2山东大学ACM模板数据结构.docx》由会员分享，可在线阅读，更多相关《2山东大学ACM模板数据结构.docx（127页珍藏版）》请在冰点文库上搜索。
2山东大学ACM模板数据结构
数据结构
1.二叉堆3
2.左偏树3
3.并查集_数组9
4.并查集_种类（未带路径压缩）9
5.SpareTable_RMQ10
6.树状数组_123D11
7.树状数组_log二分12
8.树状数组_插段问段13
9.树状数组_rmq13
10.线段树14
11.线段树_二维求最值插点问段15
12.线段树_寻找最左空间17
13.后缀数组18
14.归并树19
15.归并树_K小元素_可修改值21
16.划分树25
17.划分树_返回k小元素下标27
18.划分树-区间中位数29
19.笛卡尔树31
20.分数31
21.Matrix_Double32
22.Gauss消元（精简版）34
23.Matrix_Integer34
24.斐波那契37
25.Java小数高精度封装38
26.Java分数高精度封装39
27.BigInteger中需要注意的函数40
28.BigNumber40
29.单调队列44
30.DLX45
31.DLX数独46
32.DLX多重覆盖49
33.hash_开放寻址53
34.HashMap_cpp54
35.Trie54
36.Treap55
二叉堆
structNod{
intnum;
booloperator<（constNod&n）const{
returnnum}
};
structHeap{
Nod*arr[10010];
intlen;
voidset（intidx,Nod*nod）{//改变arr中值的唯一渠道。
。
。
arr[idx]=nod;
}
voidinit（）{
len=0;
}
voidpush（Nod&nod）{
len++;
set（len,&nod）;
up（len）;
}
Nod*pop（）{
Nod*r=arr[1];
set（1,arr[len--]）;
down
（1）;
returnr;
}
Nod*front（）{
returnarr[1];
}
//下面是辅助方法，一般不用可以调用
voiddown（intp）{
intq=p<<1;
Nod*nod=arr[p];
while（q<=len）{
if（qif（!
（*arr[q]<*nod））break;
set（p,arr[q]）;
p=q;q=p<<1;
}
set（p,nod）;
}
voidup（intp）{
intq=p>>1;
Nod*nod=arr[p];
while（q&&*nod<*arr[q]）{
set（p,arr[q]）;
p=q;
q=p>>1;
}
set（p,nod）;
}
voidbuild（）{
for（inti=len/2;i>0;i--）{
down（i）;
}
}
};
左偏树
//注释：
initTree（）只需调一次,NULL节点编号为0、D为-1,单元素节点的L、R、D都为0
intK[maxn];//Key
intL[maxn],R[maxn],D[maxn];//左、右、dis
intN[maxn];//本棵树节点个数
intlen;//资源使用量
intrubbish;//【回收资源0】
voidinitTree（）{//只需掉一次，清资源，设NULL节点
len=1;
D[0]=-1;
rubbish=0;
N[0]=0;
}
structLeftTree{
intr;//次树的根
LeftTree（intr=0）{//构造，传根，0表示为空树
this->r=r;
}
voidmerge（LeftTreex）{//this=thismergex
r=merge（r,x.r）;
}
inttop（）{
returnK[r];
}
intsize（）{
returnN[r];
}
intpop（）{//this=thispopmin
D[r]=rubbish;rubbish=r;//【回收资源1】
intt=K[r];
r=merge（L[r],R[r]）;
returnt;
}
voidpush（intkey）{//this=thispushkey
intB;
if（rubbish）{//【回收资源2】
B=rubbish;
rubbish=D[rubbish];
}else{
B=len++;
}
K[B]=key;
L[B]=R[B]=D[B]=0;
N[B]=1;
r=merge（r,B）;
}
voidclear（）{//【待测】清空本树的资源，请保证这棵树是合法的;如果是initTree后第一次建树，应该用=LeftTree（）
clear（r）;
r=0;
}
private:
voidclear（intidx）{//【待测】
if（idx==0）return;
D[idx]=rubbish;rubbish=idx;//【回收资源3】
clear（L[idx]）;clear（R[idx]）;
}
intmerge（intA,intB）{//合并A和B树，返回新树（此函数私有）
if（A==0||B==0）returnA+B;
if（K[B]>K[A]）swap（A,B）;//大于为最大堆
R[A]=merge（R[A],B）;
if（D[L[A]]D[A]=D[R[A]]+1;//无论R[a]是不是NULL，都满足
N[A]=N[L[A]]+N[R[A]]+1;
returnA;
}
};
/**
【题目1】ZOJ2334-MonkeyKing
分析：
题目很简单，有N个猴子，开始每个猴子相互不认识，并且都有一个个子的力量值
他们之间会发生冲突，冲突的两只猴子如果不认识，就各自在自己的朋友圈子里找力量最强的然后决斗，
决斗完两群猴子都相互认识了，并且力量最强的一只会力量值减半。
有M问，每问i,j，第i只猴子和第j只猴子发生冲突，输出战斗后合并成一堆的最强猴子的最大值。
*/
#definemaxn100010
intn,m;
intarr[maxn];
intp[maxn],r[maxn];
voidmake（）{
memset（r,0,sizeof（r））;
memset（p,255,sizeof（p））;
}
intfind（intx）{
intpx,i;
for（px=x;p[px]!
=-1;px=p[px]）;
while（x!
=px）{
i=p[x];
p[x]=px;
x=i;
}
returnpx;
}
//失败返回-1，否则返回新祖先
intunio（intx,inty）{
x=find（x）;y=find（y）;
if（x==y）return-1;
if（r[x]>r[y]）{
p[y]=x;
returnx;
}else{
p[x]=y;
if（r[x]==r[y]）r[y]++;
returny;
}
}
//////////////华丽的分割线！
！
！
！
！
！
！
！
！
以上是并查集
//注释：
initTree（）只需调一次,NULL节点编号为0、D为-1,单元素节点的L、R、D都为0
intK[maxn];//Key
intL[maxn],R[maxn],D[maxn];//左、右、dis
intlen;//资源使用量
intrubbish;//【回收资源0】
voidinitTree（）{//只需掉一次，清资源，设NULL节点
len=1;
D[0]=-1;
rubbish=0;
}
structLeftTree{
intr;//次树的根
LeftTree（intr=0）{//构造，传根，0表示为空树
this->r=r;
}
voidmerge（LeftTreex）{//this=thismergex
r=merge（r,x.r）;
}
inttop（）{
returnK[r];
}
intpop（）{//this=thispopmin
D[r]=rubbish;rubbish=r;//【回收资源1】
intt=K[r];
r=merge（L[r],R[r]）;
returnt;
}
voidpush（intkey）{//this=thispushkey
intB;
if（rubbish）{//【回收资源2】
B=rubbish;
rubbish=D[rubbish];
}else{
B=len++;
}
K[B]=key;
L[B]=R[B]=D[B]=0;
r=merge（r,B）;
}
private:
intmerge（intA,intB）{//合并A和B树，返回新树（此函数私有）
if（A==0||B==0）returnA+B;
if（K[B]>K[A]）swap（A,B）;//大于为最大堆
R[A]=merge（R[A],B）;
if（D[L[A]]D[A]=D[R[A]]+1;//无论R[a]是不是NULL，都满足
returnA;
}
};
LeftTreelt[maxn];
voiddes（inta）{
intval=lt[a].pop（）;
lt[a].push（val/2）;
}
intmain（）{
while（scanf（"%d",&n）!
=EOF）{
make（）;initTree（）;
for（inti=0;iscanf（"%d",arr+i）;
lt[i]=LeftTree（）;
lt[i].push（arr[i]）;
}
inta,b,c;
for（scanf（"%d",&m）;m--;）{
scanf（"%d%d",&a,&b）;
a=find（a-1）;b=find（b-1）;
c=unio（a,b）;
if（c==-1）printf（"%d\n",-1）;
else{
des（a）;des（b）;
lt[a].merge（lt[b]）;
lt[c]=lt[a];///将并查集的根的节点作为LeftTree的根
printf（"%d\n",lt[c].top（））;
}
}
}
return0;
}
/**
【题目2】boi2004-Sequence
原题:
给定数列（Sequence）a[1..N]（N<10^6）构造一个严格递增数列b[1..N]（b[i]使得|a[i]-b[i]|（i=1..N）的和最小.输出这个最小值.
solve:
对于Sequenceb先考虑满足b[i]<=b[j]{i首先设当前构造position=i,若a[i]>=b[i-1]显然可以取b[i]=a[i],若a[i]<
b[i-1]则对于当前一个"块"（block,letrange[currentblock]=k..i,每一个b[j|j=
k..i]的值均相同）key[currentblock]显然应该取a[k..i]的中位数,我们只需要不断维
护我们的block就可以了.而维护block的目的是选取中位数,我们就可以将a[k..i]中选
取最小的ceil[（i-k+1）/2]个元素,询问最大值就可以了.而这显然可以使用leftlisttree
这一种数据结构高效解决.
再考虑b先考虑满足b[i]这个时候我们只要令a'[i]=a[i]-i,同样处理a'就可以了.
*/
#definemaxn1000100
//注释：
initTree（）只需调一次,NULL节点编号为0、D为-1,单元素节点的L、R、D都为0
intK[maxn];//Key
intL[maxn],R[maxn],D[maxn];//左、右、dis
intN[maxn];//本棵树节点个数
intlen;//资源使用量
intrubbish;//【回收资源0】
voidinitTree（）{//只需掉一次，清资源，设NULL节点
len=1;
D[0]=-1;
rubbish=0;
N[0]=0;
}
structLeftTree{
intr;//次树的根
LeftTree（intr=0）{//构造，传根，0表示为空树
this->r=r;
}
voidmerge（LeftTreex）{//this=thismergex
r=merge（r,x.r）;
}
inttop（）{
returnK[r];
}
intsize（）{
returnN[r];
}
intpop（）{//this=thispopmin
D[r]=rubbish;rubbish=r;//【回收资源1】
intt=K[r];
r=merge（L[r],R[r]）;
returnt;
}
voidpush（intkey）{//this=thispushkey
intB;
if（rubbish）{//【回收资源2】
B=rubbish;
rubbish=D[rubbish];
}else{
B=len++;
}
K[B]=key;
L[B]=R[B]=D[B]=0;
N[B]=1;
r=merge（r,B）;
}
private:
intmerge（intA,intB）{//合并A和B树，返回新树（此函数私有）
if（A==0||B==0）returnA+B;
if（K[B]>K[A]）swap（A,B）;//大于为最大堆
R[A]=merge（R[A],B）;
if（D[L[A]]D[A]=D[R[A]]+1;//无论R[a]是不是NULL，都满足
N[A]=N[L[A]]+N[R[A]]+1;
returnA;
}
};
/////////////////////华丽的分隔线---------以上是左偏树
LeftTreelt[maxn];
intq[maxn],m;
longlonggetNotDec（int*a,intn,int*b）{//【构造非降的序列b】
initTree（）;
m=0;
for（inti=0;iq[m++]=i;
q[m]=i+1;
lt[m-1]=LeftTree（）;
lt[m-1].push（a[i]）;
while（m-2>=0&<[m-2].top（）>lt[m-1].top（））{
lt[m-2].merge（lt[m-1]）;
q[m-1]=q[m];
while（lt[m-2].size（）>（q[m-1]-q[m-2]）/2+1）{//取较大的那个中位数
lt[m-2].pop（）;
}
m--;
}
}
longlongres=0;
for（inti=0;ifor（intj=q[i];jb[j]=lt[i].top（）;
res+=abs（a[j]-lt[i].top（））;
}
}
returnres;
}
longlonggetInc（int*a,intn,int*b）{//【构造上升的序列b】
for（inti=0;ilonglongres=getNotDec（a,n,b）;
for（inti=0;ireturnres;
}
intarr[maxn],n,res[maxn];
intmain（）{
while（scanf（"%d",&n）!
=EOF）{
for（inti=0;iscanf（"%d",arr+i）;
}
longlongans=getInc（arr,n,res）;
printf（"%lld\n",ans）;
for（inti=0;iprintf（"%d",res[i]）;
}
printf（"\n"）;
}
return0;
}
并查集_数组
intp[maxn],r[maxn];
voidmake（）{
memset（r,0,sizeof（r））;
memset（p,255,sizeof（p））;
}
intfind（intx）{
intpx,i;
for（px=x;p[px]!
=-1;px=p[px]）;
while（x!
=px）{
i=p[x];
p[x]=px;
x=i;
}
returnpx;
}
//失败返回-1，否则返回新祖先
intunio（intx,inty）{
x=find（x）;y=find（y）;
if（x==y）return-1;
if（r[x]>r[y]）{
p[y]=x;
returnx;
}else{
p[x]=y;
if（r[x]==r[y]）r[y]++;
returny;
}
}
并查集_种类（未带路径压缩）
constintK=3;//种类数，种类为[0,k）
intp[maxn],k[maxn];//父亲，种类号
voidmake（）{
memset（p,255,sizeof（p））;
memset（k,0,sizeof（k））;
}
intfind（intx）{
if（p[x]==-1）returnx;
intpx=p[x];
p[x]=find（p[x]）;
k[x]=（k[x]+k[px]）%K;
returnp[x];
}
/**find的非递归版：
intfind（intx）{
intpx,i,num=0,tmp;
for（px=x;p[px]!
=-1;px=p[px]）
num+=k[px];
while（x!
=px）{
tmp=k[x];
k[x]=num%K;
num-=tmp;//和普通并查集的不同
i=p[x];
p[x]=px;
x=i;
}
returnpx;
}
*/
//d=a的种类-b的种类.返回true说明a、b未合并过
boolunio（inta,intb,intd）{
intra=find（a）,rb=find（b）;
if（ra==rb）returnfalse;
p[rb]=ra;
k[rb]=（（k[a]-k[b]-d）%K+K）%K;
returntrue;
}
性质：
在同一个并查集里面的编号都已经相对稳定
经典用法：
if（false==unio（a,b,d））{
if（（k[a]-k[b]–d）%K!
=0）{
…//因为此时已经find完了，所以直接掉k
}
}
SpareTable_RMQ
/**
spare-table算法，取rmq[1...n]中的极值
询问的时候，是闭区间
*/
#definemaxn1000010
intrmq[maxn];
structST{
#
升级会员 