给新高一小朋友讲可合并数据结构
list
链表，任何合并都是
线段树
例一
注意到模板线段树合并需要用到 LCA，因此我们以 P3224 为例。
参考实现
#include<stdio.h>
#define N 100001
inline char nc()
{
static char buf[99999],*l,*r;
return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
char c=nc();for(;c<'0'||'9'<c;c=nc());
for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node
{
int cnt;node*l,*r;
inline node(){cnt=1;l=r=0;}
}*tre[N];
int n,m,a[N],c[N],f[N];
inline int find(const int&x){if(x^f[x])return f[x]=find(f[x]);return x;}
inline node*b(const int&l,const int&r,const int&p)
{
node*i=new node;
if(l^r)
{
int mid=l+r>>1;
if(p<=mid)i->l=b(l,mid,p);
else i->r=b(mid+1,r,p);
}
return i;
}
inline void onion(node*&i,node*&j)
{
if(!i){i=j;return;}
if(!j)return;
i->cnt+=j->cnt;
onion(i->l,j->l);onion(i->r,j->r);
}
inline int q(const node*i,const int&l,const int&r,const int&p)
{
if(l==r)return l;
int mid=l+r>>1;
if(i->l&&p<=i->l->cnt)return q(i->l,l,mid,p);
return q(i->r,mid+1,r,p-(i->l?i->l->cnt:0));
}
main()
{
read(n);read(m);
for(int i=0;i<n;read(a[i]),c[a[i]]=i+1,tre[i]=b(1,n,a[i]),f[i]=i,++i);
for(int o,x,y;m--;)
{
read(x);read(y);x=find(--x);y=find(--y);
if(x^y)onion(tre[x],tre[y]),f[y]=x;
}
read(m);
for(int o,x,y;m--;)
{
for(;o=nc(),(o^'Q')&&(o^'B'););
if(o^'Q')
{
read(x);read(y);x=find(--x);y=find(--y);
if(x^y)onion(tre[x],tre[y]),f[y]=x;
}
else
{
read(x);read(y);x=find(--x);
if(tre[x]->cnt<y)printf("-1\n");
else printf("%d\n",c[q(tre[x],1,n,y)]);
}
}
}例二
大家都会 LCA，讲 P4556。
参考实现
#include<stdio.h>
#include<algorithm>
#define N 100001
#define LG 17
using namespace std;
inline char nc()
{
static char buf[99999],*l,*r;
return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
char c=nc();for(;c<'0'||'9'<c;c=nc());
for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node{int maxi,maxn,l,r;}a[N<<5];
int n,m,p,h[N],e[N<<1],nxt[N<<1],dep[N],jmp[N][LG],ans[N];
int q1[N],q2[N],q3[N],lsh[N],tre[N],sz;
inline void dfs(const int&i,const int&f)
{
dep[i]=dep[f]+1;jmp[i][0]=f;
for(int j=1;j<LG;++j)jmp[i][j]=jmp[jmp[i][j-1]][j-1];
for(int j=h[i];j;j=nxt[j])if(e[j]^f)dfs(e[j],i);
}
inline void add(int&i,const int&l,const int&r,const int&x,const int&y)
{
if(!i)i=++sz;
if(l^r)
{
int mid=l+r>>1;
if(x<=mid)add(a[i].l,l,mid,x,y);
else add(a[i].r,mid+1,r,x,y);
if(!a[i].l||(a[i].r&&a[a[i].r].maxn>a[a[i].l].maxn))
a[i].maxi=a[a[i].r].maxi,a[i].maxn=a[a[i].r].maxn;
else a[i].maxi=a[a[i].l].maxi,a[i].maxn=a[a[i].l].maxn;
}
else a[i].maxi=l,a[i].maxn+=y;
}
inline void onion(int&i,int&j)
{
if(!j)return;
if(!i){i=j;return;}
if(!a[i].l&&!a[i].r)
{
a[i].maxn+=a[j].maxn;
if(!a[i].maxn)i=0;
}
else
{
onion(a[i].l,a[j].l);onion(a[i].r,a[j].r);
if(!a[i].l&&!a[i].r){i=0;return;}
if(!a[i].l||(a[i].r&&a[a[i].r].maxn>a[a[i].l].maxn))
a[i].maxi=a[a[i].r].maxi,a[i].maxn=a[a[i].r].maxn;
else a[i].maxi=a[a[i].l].maxi,a[i].maxn=a[a[i].l].maxn;
}
}
inline void dfs2(const int&i,const int&f)
{
for(int j=h[i];j;j=nxt[j])if(e[j]^f)
{
dfs2(e[j],i);
onion(tre[i],tre[e[j]]);
}
if(!tre[i])ans[i]=-1;
else ans[i]=a[tre[i]].maxi;
}
main()
{
read(n);read(m);
for(int i=1,u,v;i<n;++i)
{
read(u);read(v);--u;--v;
e[i]=v;nxt[i]=h[u];h[u]=i;
e[i+n]=u;nxt[i+n]=h[v];h[v]=i+n;
}
dfs(0,0);
for(int i=0;i<m;read(q1[i]),--q1[i],read(q2[i]),--q2[i],
read(q3[i]),lsh[i]=q3[i],++i);
sort(lsh,lsh+m);p=unique(lsh,lsh+m)-lsh;
for(int i=0,u,v,w,x,y,l;i<m;++i)
{
u=q1[i];v=q2[i];w=lower_bound(lsh,lsh+p,q3[i])-lsh;
if(!u){add(tre[v],0,p-1,w,1);continue;}
if(!v){add(tre[u],0,p-1,w,1);continue;}
x=u;y=v;
if(dep[x]<dep[y])x^=y^=x^=y;
for(int i=LG-1;i>=0;--i)if(dep[jmp[x][i]]>=dep[y])x=jmp[x][i];
for(int i=LG-1;i>=0;--i)if(jmp[x][i]^jmp[y][i])
x=jmp[x][i],y=jmp[y][i];
l=(x^y?jmp[x][0]:x);
if(l)add(tre[u],0,p-1,w,1),
add(tre[v],0,p-1,w,1),
add(tre[l],0,p-1,w,-1),
add(tre[jmp[l][0]],0,p-1,w,-1);
else add(tre[u],0,p-1,w,1),
add(tre[v],0,p-1,w,1),
add(tre[l],0,p-1,w,-1);
}
dfs2(0,0);
for(int i=0;i<n;printf("%d\n",~ans[i]?lsh[ans[i]]:0),++i);
}习题
P13129
vector deque
讲讲启发式合并。
例题
P8496
摩尔投票：解决绝对众数问题。
参考实现
#include<stdio.h>
#include<deque>
#define N 1000002
using namespace std;
inline char nc()
{
static char buf[99999],*l,*r;
return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
char c=nc();for(;c<'0'||'9'<c;c=nc());
for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct data
{
int maxn,cnt;
inline data operator+(const data&kkk)const
{
if(maxn==kkk.maxn)return(data){maxn,cnt+kkk.cnt};
if(cnt>kkk.cnt)return(data){maxn,cnt-kkk.cnt};
return(data){kkk.maxn,kkk.cnt-cnt};
}
}tmp;
struct node
{
data x;node*l,*r;
inline node(){x.cnt=0;l=r=0;}
}*tre[N];
int n,q,b[N],f[N];deque<int>a[N>>1];
inline int find(const int&x){if(x^f[x])return f[x]=find(f[x]);return x;}
inline void upd(node*i)
{
if(!i->l)i->x=i->r->x;
else if(!i->r)i->x=i->l->x;
else i->x=i->l->x+i->r->x;
}
inline void add(node*&i,const int&l,const int&r,const int&x)
{
if(!i)i=new node;
if(l==r){i->x.maxn=x;++i->x.cnt;return;}
int mid=l+r>>1;
if(x<=mid)add(i->l,l,mid,x);
else add(i->r,mid+1,r,x);
upd(i);
}
inline void del(node*&i,const int&l,const int&r,const int&x)
{
if(l==r){--i->x.cnt;if(!i->x.cnt)i=0;return;}
int mid=l+r>>1;
if(x<=mid)del(i->l,l,mid,x);
else del(i->r,mid+1,r,x);
if(!i->l&&!i->r)i=0;
else upd(i);
}
inline int ask(const node*i,const int&l,const int&r,const int&x)
{
if(!i)return 0;
if(l==r)return i->x.cnt;
int mid=l+r>>1;
if(x<=mid)return ask(i->l,l,mid,x);
return ask(i->r,mid+1,r,x);
}
inline void onion(node*&i,node*&j)
{
if(!i){i=j;return;}
if(!j)return;
if(i->l||i->r)onion(i->l,j->l),onion(i->r,j->r),upd(i);
else i->x.cnt+=j->x.cnt;
}
main()
{
read(n);read(q);
for(int i=1,x;i<=n;++i)
{
read(x);a[i].resize(x);f[i]=i;
for(int j=0;j<x;read(a[i][j]),add(tre[i],0,n+q,a[i][j]),++j);
}
for(int qq=q,o,x,y,z;qq--;)switch(read(o),o)
{
case 1:read(x);read(y);
a[find(x)].emplace_back(y);add(tre[x],0,n+q,y);
break;
case 2:read(x);
del(tre[x],0,n+q,a[find(x)].back());a[find(x)].pop_back();
break;
case 3:read(x);tmp.cnt=0;y=z=0;
for(int i=0;i<x;read(b[i]),y+=a[find(b[i])].size()
,a[find(b[i])].size()&&(tmp=tmp+tre[b[i]]->x,1),++i);
for(int i=0;i<x;z+=ask(tre[b[i++]],0,n+q,tmp.maxn));
// for(int i=0;i<x;++i)
// {
// for(int j=0;j<a[find(b[i])].size();++j)
// printf("%d ",a[find(b[i])][j]);
// putchar('\n');
// }
// printf("%d %d %d %d\n",tmp.maxn,tmp.cnt,y,z);
if(z>y>>1)printf("%d\n",tmp.maxn);
else printf("-1\n");
break;
case 4:read(x);read(y);read(z);
onion(tre[z]=tre[y],tre[x]);
if(a[find(x)].size()<a[find(y)].size())
for(f[z]=find(y);a[find(x)].size();a[find(z)].push_front(
a[find(x)].back()),a[find(x)].pop_back());
else for(f[z]=find(x);a[find(y)].size();a[find(z)].push_back(
a[find(y)].front()),a[find(y)].pop_front());
}
}可并堆
不讲。
平衡树
两棵树值域不交：直接连起来。
有交：启发式合并。
设小的树大小为