高级数据结构
一、左偏树&斜堆
orz黄源河论文
合并，插入，删除根节点
打标记
struct Node { int fa,l,r,w,dep } tree[Mx];
int Merge(int k1,int k2)//返回值为根节点
{
if(k1==||k2==) return k1+k2;
if(tree[k1].val<tree[k2].val) swap(k1,k2);
tree[k1].r=Merge(tree[k1].r,k2);
tree[tree[k1].r].fa=k1;
if(tree[tree[k1].l].dep<tree[tree[k1].r].dep) swap(tree[k1].l,tree[k1].r);
if(tree[k1].r==) tree[k1].dep=;
else tree[k1].dep=tree[tree[k1].r].dep+;
return k1;
}
int del(int root)//删除根节点
{
int k1=tree[root].l,k2=tree[root].r;
l[root]=;r[root]=;fa[k1]=;fa[k2]=;
return Merge(k1,k2);
}
应用：bzoj1367【Baltic 2004】
给定一个整数序列a1,a2,…,an，求一个不下降序列b1≤b2≤…≤bn，使得数列{ai}和{bi}的各项之差的绝对值之和最小
首先给出结论：①bi是由多段相同的数组成的
②bi的每一段的数一定是ai该段的中位数
P.S.证明我也不会QAQ，自己看论文
solution:考虑若已经解决了前k个数的最优解(m个区间)，记为w[1~m]，
新加一个点时，先将其单独作为一个区间插入w，若w[now]<w[now-1]，
则合并后两个区间，并继续判定，直到满足单调不降，最终w序列即为b序列。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int Mx=;
int n,top,ans,a[Mx],b[Mx],L[Mx],R[Mx],stk[Mx],siz[Mx];
struct Node { int fa,l,r,val,dep; } tree[Mx];
int Merge(int k1,int k2)
{
if(k1==||k2==) return k1+k2;
if(tree[k1].val<tree[k2].val) swap(k1,k2);
tree[k1].r=Merge(tree[k1].r,k2);
tree[tree[k1].r].fa=k1;
if(tree[tree[k1].l].dep<tree[tree[k1].r].dep) swap(tree[k1].l,tree[k1].r);
if(tree[k1].r==) tree[k1].dep=;
else tree[k1].dep=tree[tree[k1].r].dep+;
return k1;
}
signed main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int i=;i<=n;i++)
{
tree[i].val=a[i];
stk[++top]=i;
L[top]=R[top]=i;
siz[top]=;
while(top>&&tree[stk[top]].val<=tree[stk[top-]].val)
{
R[top-]=R[top];
siz[top-]+=siz[top];
stk[top-]=Merge(stk[top-],stk[top]);
top--;
int len=R[top]-L[top]+;
if(len%==) len /= ;
else len = len / + ;
while(siz[top]>len)
{
siz[top]--;
stk[top]=Merge(tree[stk[top]].l, tree[stk[top]].r);
}
}
}
for(int i=;i<=top;i++)
for(int j=L[i];j<=R[i];j++)
b[j]=tree[stk[i]].val;
for(int i=;i<=n;i++) ans+=abs(b[i]-a[i]);
printf("%lld\n", ans);
return ;
}
二、线段树
建树，修改，查询，lazy标记
主席树，可持久化线段树
//zkw线段树
例：bzoj1146
bzoj2653
三、平衡树
旋转：splay
单旋&双旋
单旋仅在当前节点为根节点的儿子时使用
考虑当前节点与其父亲，其父亲与其祖父的关系，分为zig-zig,zig-zag
当p为根时进行zig操作
若x为p的左儿子，则p的左子树换为x的右子树，x的右儿子换为p。（对x右旋）
若x为p的右儿子，则p的右子树换为x的左子树，x的左儿子换为p。（对x左旋）
当x，p同为左（右）儿子时进行zig-zig操作
若同为左儿子，则先将p右旋，再将x右旋
若同为右儿子，则先将p左旋，再将x左旋
当x，p不同为左（右）儿子时进行zig-zag操作
若p为左孩子，x为右孩子，将x先左旋再右旋
若p为右孩子，x为左孩子，将x先右旋再左旋
#include<iostream>
using namespace std; void pushup(int rr)
{
t[rr].siz=t[t[rr].l].siz+t[t[rr].r].siz+t[rr].num;
}
void zig(int x)
{
int y=t[x].fa;
if(t[x].r)t[y].l=t[x].r,t[t[x].r].fa=y;
else t[y].l=;
if(t[t[y].fa].l==y)t[t[y].fa].l=x;
else t[t[y].fa].r=x;
t[x].fa=t[y].fa;t[x].r=y;t[y].fa=x;
pushup(y);
}
void zag(int x)
{
int y=t[x].fa;
if(t[x].l)t[y].r=t[x].l,t[t[x].l].fa=y;
else t[y].r=;
if(t[t[y].fa].l==y)t[t[y].fa].l=x;
else t[t[y].fa].r=x;
t[x].fa=t[y].fa;t[x].l=y;t[y].fa=x;
pushup(y);
}
void splay(int x,int tar)
{
while(t[x].fa!=tar)
{
int y=t[x].fa,yy=t[y].fa;
if(yy)
{
if(t[y].l==x)zig(x);
else zag(x);
}
else
{
if(t[yy].l==y)
{
if(t[y].l==x)zig(y),zig(x);
else zag(x),zig(x);
}
else
{
if(t[y].l==x)zig(x),zag(x);
else zag(y),zag(x);
}
}
}
if(!tar)root=x;
pushup(x);
}
void newnode(int &x,int fa,int key)
{
x=++tot;
t[x].pre=fa;
t[x].siz=t[x].num=;
t[x].rev=t[x].l=t[x].r=;
t[x].key=key;
}
void build(int l,int r,int &rr,int fa)
{
if(l>r)return;
int mid=(l+r)/;
newnode(rr,fa,a[mid]);
build(l,mid-,t[rr].l,rr);
build(mid+,r,t[rr].r,rr);
pushup(rr);
}
int main()
{
// 1 to n a[]
build(,n,root,);
return ;
}
treap
插入节点：先将节点插入，然后随机一个优先级，通过旋转使优先级满足堆性质。
删除：找到节点后将其旋转到叶子上并删除
查询：同二叉搜索树
//来源：@SiriusRen （我懒得写了QAQ）
//poj1442：动态插入点，查询第k大
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt=,jy,a[],n,m,root=-;
struct node{
int left,right,count_left,count_right,key,priority;
}treap[];
void zig(int &x){
int y=treap[x].right;
treap[x].right=treap[y].left;
treap[x].count_right=treap[y].count_left;
treap[y].left=x;
treap[y].count_left=treap[x].count_left+treap[x].count_right+;
x=y;
}
void zag(int &x){
int y=treap[x].left;
treap[x].left=treap[y].right;
treap[x].count_left=treap[y].count_right;
treap[y].right=x;
treap[y].count_right=treap[x].count_left+treap[x].count_right+;
x=y;
}
void insert(int &x,int new_key){
if(x==-){
x=cnt++;
treap[x].left=treap[x].right=-;
treap[x].priority=rand();
treap[x].key=new_key;
treap[x].count_left=treap[x].count_right=;
}
else if(new_key<treap[x].key){
treap[x].count_left++;
insert(treap[x].left,new_key);
if(treap[x].priority>treap[treap[x].left].priority)zag(x);
}
else{
treap[x].count_right++;
insert(treap[x].right,new_key);
if(treap[x].priority>treap[treap[x].right].priority)zig(x);
}
}
int query(int &x,int k_th){
if(treap[x].count_left+==k_th)return treap[x].key;
if(treap[x].count_left+<k_th)return query(treap[x].right,k_th-treap[x].count_left-);
return query(treap[x].left,k_th);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=m;i++){
scanf("%d",&jy);
while(cnt<jy)insert(root,a[cnt+]);
printf("%d\n",query(root,i));
}
}
笛卡尔树
后缀平衡树
重建：替罪羊树
在二叉搜索树的基础上拍扁重建为完全二叉树
加点：往上判断找最靠近根的不满足(siz[l]<=0.7*siz[root]&&siz[r]<=0.7*siz[root])的点，将此子树拍扁重建
删点：打标记，如果某棵子树被删掉的点>=siz/2，就将这棵子树重建
查询：与二叉搜索树相同
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int Mx=;
struct Node { int val,cnt; }tree[Mx];
int n,point,tot,l[Mx],r[Mx],fa[Mx],siz[Mx];
int num[Mx],cnt1;
void pre(int root)
{
if(root!=)
{
pre(l[root]);
if(tree[root].cnt!=) num[++cnt1]=root;
pre(r[root]);
}
}
int tmp;
void build(int lft,int rgh,int root,int jud)
{
int now=num[(lft+rgh)/];
fa[now]=root;r[now]=;l[now]=;siz[now]=;
if(jud==) l[root]=now;
else r[root]=now;
if(lft<(lft+rgh)/) build(lft,(lft+rgh)/-,now,);
if(rgh>(lft+rgh)/) build((lft+rgh)/+,rgh,now,);
siz[now]++;fa[siz[now]]+=siz[now];
}
void rebuild(int root,int jud)
{
cnt1=;
pre(root);
build(,cnt1,fa[root],jud);
}
void add(int num,int root)
{
if(num==tree[root].val)
{
tree[root].cnt++;
int temp=root;
while(fa[temp]!=)
{
temp=fa[temp];
siz[temp]++;
}
}
else if(num<tree[root].val)
{
if(l[root]==)
{
tree[++tot].val=num;tree[tot].cnt=;
l[root]=tot;fa[tot]=root;
siz[tot]=;
int temp=tot,temp1=;
while(fa[temp]!=)
{
temp=fa[temp];
siz[temp]++;
if((double)siz[l[temp]]>0.7*(double)siz[temp]||(double)siz[r[temp]]>0.7*(double)siz[temp]) temp1=temp;
}
if(temp1!=)
{
if(l[fa[temp1]]==temp1) rebuild(temp1,);
else rebuild(temp1,);
}
}
else add(num,l[root]);
}
else
{
if(r[root]==)
{
tree[++tot].val=num;tree[tot].cnt=;
r[root]=tot;fa[tot]=root;
siz[tot]=;
int temp=tot,temp1=;
while(fa[temp]!=)
{
temp=fa[temp];
siz[temp]++;
if((double)siz[l[temp]]>0.7*(double)siz[temp]||(double)siz[r[temp]]>0.7*(double)siz[temp]) temp1=temp;
}
if(temp1!=)
{
if(l[fa[temp1]]==temp1) rebuild(temp1,);
else rebuild(temp1,);
}
}
else add(num,r[root]);
}
}
int cntdel[Mx];
void cleardel(int root)
{
cntdel[root]=;
if(l[root]!=) cleardel(l[root]);
if(r[root]!=) cleardel(r[root]);
}
void del(int num)
{
int root=,tmp=;
while(tree[root].val!=num)
{
if(tree[root].val<num) root=r[root];
else root=l[root];
}
tree[root].cnt--;cntdel[root]++;siz[root]--;
while(fa[root]!=)
{
root=fa[root];cntdel[root]++;siz[root]--;
if((double) cntdel[root]>=(double) siz[root]/) tmp=root;
}
if(tmp!=)
{
if(l[fa[tmp]]==tmp) rebuild(tmp,);
else rebuild(tmp,);
cleardel(tmp);
}
}
void search_rank(int num,int root,int tmp)
{
if(num==tree[root].val) printf("%d\n",tmp+siz[l[root]]+);
else if(num<tree[root].val) search_rank(num,l[root],tmp);
else search_rank(num,r[root],tmp+siz[l[root]]+);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int jud,a;scanf("%d%d",&jud,&a);
if(jud==) add(a,);
else if(jud==) del(a);
else search_rank(a,r[],);
}
return ;
}
分裂合并：FHQ treap
四、树套树
线段树套线段树
线段树套平衡树 (区间第k小)
树状数组套主席树
替罪羊树套主席树
五、莫队算法
例：bzoj2038【小z的袜子】
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int Mx=;
struct Node { int l,r,num; } que[Mx];
bool cmp1 (Node a,Node b) { return a.l<b.l; }
bool cmp2 (Node a,Node b) { return a.r<b.r; }
int n,m,c[Mx],num[Mx],ans[Mx],ans1[Mx][];
inline int gcd (int a,int b) { int tmp; while(a>) tmp=b%a,b=a,a=tmp; return b; }
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++) scanf("%lld",&c[i]);
for(int i=;i<=m;i++) { scanf("%lld%lld",&que[i].l,&que[i].r);if(que[i].l>que[i].r) swap(que[i].l,que[i].r); }
for(int i=;i<=m;i++) que[i].num=i;
sort(que+,que++m,cmp1);
for(int i=;i<=m;i+=sqrt(m)) sort(que+i,que+min(m,i+(int)sqrt(m)),cmp2);
for(int i=;i<=m;i++)
{
if(i%(int)sqrt(m)==||i==)
{
memset(num,,sizeof(num));
for(int j=que[i].l;j<=que[i].r;j++) num[c[j]]++;
for(int j=;j<=n;j++) ans[i]+=num[j]*(num[j]-)/;
}
else
{
for(int j=que[i-].l,to=que[i].l;j!=to;)
{
if(j<to) ans[i]-=num[c[j]]-,num[c[j]]--,j++;
else ans[i]+=num[c[j-]],num[c[j-]]++,j--;
}
for(int j=que[i-].r,to=que[i].r;j!=to;)
{
if(j<to) ans[i]+=num[c[j+]],num[c[j+]]++,j++;
else ans[i]-=num[c[j]]-,num[c[j]]--,j--;
}
ans[i]+=ans[i-];
}
int div=gcd(ans[i],(que[i].r-que[i].l+)*(que[i].r-que[i].l)/);
if(que[i].r==que[i].l||ans[i]==) ans1[que[i].num][]=,ans1[que[i].num][]=;
else ans1[que[i].num][]=ans[i]/div,ans1[que[i].num][]=(que[i].r-que[i].l+)*(que[i].r-que[i].l)/(div*);
}
for(int i=;i<=m;i++) printf("%lld/%lld\n",ans1[i][],ans1[i][]);
return ;
}