zcmimi's blog

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启发式合并的思想

Q: 很简单,但有什么用?

A: 假设我们要合并n个元素

按普通方法,最坏的复杂度\Theta(n^2)

假设我们按照启发式合并,可以证明每个元素最多被合并\log n

这样以来总复杂度不会超过n \log n

是不是很玄学又神奇?

启发式合并还可以可以应用在数据结构上(如线段树,平衡树,堆等),复杂度O(n \log^2 n)

链表的启发式合并

LG 3201 [HNOI2009]梦幻布丁

其实可以说是前向星

每次都把短的链表接到长的链表上

统计短的链表上每个元素改变后造成的影响

const int N=1000011;
int n,q,a[N],ans=0,st[N],bl[N],head[N],nxt[N],sz[N];
il void mg(int x,int y){
    for(int i=head[x];i;i=nxt[i])ans-=(a[i-1]==y)+(a[i+1]==y);
    for(int i=head[x];i;i=nxt[i])a[i]=y;
    sz[y]+=sz[x];nxt[st[x]]=head[y];head[y]=head[x];
    head[x]=st[x]=sz[x]=0;
}
int main(){
    in(n,q);
    Fur(i,1,n){
        in(a[i]);
        if(a[i]!=a[i-1])++ans;
        bl[a[i]]=a[i];
        if(!st[a[i]])st[a[i]]=i;
        ++sz[a[i]];nxt[i]=head[a[i]];head[a[i]]=i;
    }
    while(q--){
        int opt,x,y;
        in(opt);
        if(opt==2)out(ans,ln);
        else{
            in(x,y);
            if(x!=y){
                if(sz[bl[x]]>sz[bl[y]])SWAP(bl[x],bl[y]);
                if(sz[bl[x]])mg(bl[x],bl[y]);
            }
        }
    }
}

堆的启发式合并

LG 5290 [十二省联考2019]春节十二响

题目的意思就是相同子树中的点不能分配到同一段内存

每个点都开一个大根堆

合并一个点和它的子节点的时候最大值互相对应

启发式合并

具体看代码

const int N=200011;
int n,cnt=0,head[N],a[N],id[N],dfn=0,tmp[N],tp=0;
struct edge{int to,nxt;}e[N];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
std::priority_queue<int>q[N];
il int max(int x,int y){return x>y?x:y;}
il void swap(int &x,int &y){int t=x;x=y;y=t;}
void dfs(int x){
    id[x]=++dfn;
    fl(i,x){
        dfs(to);
        if(q[id[x]].size()<q[id[to]].size())swap(id[x],id[to]);
        int t=q[id[to]].size();tp=0;
        while(t--)
            tmp[++tp]=max(q[id[x]].top(),q[id[to]].top()),
            q[id[x]].pop(),q[id[to]].pop();
        while(tp)q[id[x]].push(tmp[tp--]);
    }
    q[id[x]].push(a[x]);
}
int main(){
    in(n);
    int x;
    Fur(i,1,n)in(a[i]);
    Fur(i,2,n)in(x),add(x,i);
    dfs(1);
    ll ans=0;
    while(!q[id[1]].empty())
        ans+=q[id[1]].top(),
        q[id[1]].pop();
    printf("%lld\n",ans);
}

Trie的启发式合并

CF 788 C

题意:

给一棵trie树,可以删掉某一层的所有边

求删掉哪一层边后合并出的trie树最小?

解法:

trie的启发式合并

int mg(int x,int y){
    if(!x||!y)return x+y;
    int now=++cnt;
    Fur(i,0,25)c[now][i]=mg(c[x][i],c[y][i]);
    return now;
}

这个合并的复杂度是\Theta(\log n)

证明:

每次合并向下递归的时候规模n会变成原来的一半\frac n2

所以最多需要合并\log_2 n

代码:

const int N=600011;
int n,cnt,c[N][26],a[N];
int mg(int x,int y){
    if(!x||!y)return x+y;
    int now=++cnt;
    Fur(i,0,25)c[now][i]=mg(c[x][i],c[y][i]);
    return now;
}
void dfs(int x,int d){
    int now=n+1;cnt=n+1;
    Fur(i,0,25)if(c[x][i])
        now=mg(now,c[x][i]);
    a[d]+=cnt-n-1;
    Fur(i,0,25)if(c[x][i])
        dfs(c[x][i],d+1);
}
int main(){
    in(n);
    int x,y,ans=0,as=0;char w;
    Fur(i,2,n)in(x,y,w),c[x][w-'a']=y;
    dfs(1,1);
    Fur(i,1,n)if(a[i]>ans)as=i,ans=a[i];
    printf("%d\n%d\n",n-ans,as);
}

数据结构+启发式合并

LG 3302 [SDOI2013]森林

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i(x);i<=y;++i)
#define Fdr(i,x,y) for(int i(x);i>=y;--i)
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
il void SWAP(int &x,int &y){int t=x;x=y;y=t;}
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=80011;
struct node{int v,p;bool operator<(node t){return v<t.v;}}b[N];
int val[N],rnk[N];
int cnt=0,head[N];
int d[N],fa[N],f[17][N],siz[N];
int SZ=0,sz=0,RT[N],ls[N*600],rs[N*600],s[N*600];
bool v[N];
struct edge{int to,nxt;}e[N<<2];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int gf(int x){return (fa[x]==x)?x:(fa[x]=gf(fa[x]));}
void build(int &x,int l,int r){
    s[x=++sz]=0;
    if(l==r)return;
    int m=(l+r)>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int &x,int pre,int l,int r,int v){
    s[x=++sz]=s[pre]+1;
    ls[x]=ls[pre];rs[x]=rs[pre];
    if(l==r)return;
    int m=(l+r)>>1;
    if(v<=m)ins(ls[x],ls[pre],l,m,v);
    else ins(rs[x],rs[pre],m+1,r,v);
}
int ask(int x,int y,int lca,int flca,int l,int r,int k){
    if(l==r)return val[l];
    int m=(l+r)>>1,sum=s[ls[x]]+s[ls[y]]-s[ls[lca]]-s[ls[flca]];
    if(k<=sum)return ask(ls[x],ls[y],ls[lca],ls[flca],l,m,k);
    else return ask(rs[x],rs[y],rs[lca],rs[flca],m+1,r,k-sum);
}
void dfs(int x,int F,int rt){
    ++siz[rt];
    d[x]=d[f[0][x]=fa[x]=F]+1;
    Fur(i,1,16)f[i][x]=f[i-1][f[i-1][x]];
    v[x]=1;
    ins(RT[x],RT[F],1,SZ,rnk[x]);
    fl(i,x)if(to!=F)dfs(to,x,rt);
}
il int lca(int x,int y){
    if(d[x]<d[y])SWAP(x,y);
    Fdr(i,16,0)if(d[f[i][x]]>=d[y])x=f[i][x];
    if(x==y)return x;
    Fdr(i,16,0)if(f[i][x]!=f[i][y])
        x=f[i][x],y=f[i][y];
    return f[0][x];
}
int main(){
    int n,m,q,lastans=0;
    in(n);
    in(n,m,q);
    Fur(i,1,n)in(b[i].v),b[i].p=i,fa[i]=i;
    std::sort(b+1,b+n+1);b[0].v=-(1<<30);
    Fur(i,1,n)val[rnk[b[i].p]=(SZ+=(b[i].v!=b[i-1].v))]=b[i].v;
    int x,y,k,t;char ch;
    Fur(i,1,m)in(x,y),add(x,y),add(y,x);
    build(RT[0],1,SZ);
    Fur(i,1,n)if(!v[i])dfs(i,0,i),fa[i]=i;
    while(q--){
        in(ch,x,y);
        x^=lastans;y^=lastans;
        if(ch=='Q'){
            in(k);k^=lastans;t=lca(x,y);
            out(lastans=ask(RT[x],RT[y],RT[t],RT[f[0][t]],1,SZ,k),ln);
        }
        else{
            add(x,y),add(y,x);
            if(siz[gf(x)]>siz[gf(y)])SWAP(x,y);
            dfs(x,y,gf(y));
        }
    }
    flush();
}

线段树合并

int mg(int x,int y,int l=1,int r=100000){
    if(!x||!y)return x|y;
    if(l==r)return s[x]+=s[y],S[x]=l,x;//合并两个节点的信息
    int m=(l+r)>>1;
    ls[x]=mg(ls[x],ls[y],l,m); 
    rs[x]=mg(rs[x],rs[y],m+1,r);
    pushup(x);return x;
}

例题:

LG 4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,lca(x,y),f_{lca(x,y)}w位置-1

统计的时候不断向上线段树合并

具体看代码

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i(x);i<=y;++i)
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}
const int N=100011;
int n,q,cnt=0,sz=0,head[N],s[N*60],S[N*60],ls[N*60],rs[N*60],RT[N],ans[N];
il void pu(int rt){s[ls[rt]]>=s[rs[rt]]?(s[rt]=s[ls[rt]],S[rt]=S[ls[rt]]):(s[rt]=s[rs[rt]],S[rt]=S[rs[rt]]);}
void upd(int &rt,int x,int v,int l=1,int r=100000){
    if(!rt)rt=++sz;
    if(l==r){s[rt]+=v;S[rt]=l;return;}
    int m=(l+r)>>1;
    if(x<=m)upd(ls[rt],x,v,l,m);
    else upd(rs[rt],x,v,m+1,r);
    pu(rt);
}
int mg(int x,int y,int l=1,int r=100000){
    if(!x||!y)return x|y;
    if(l==r)return s[x]+=s[y],S[x]=l,x;
    int m=(l+r)>>1;
    ls[x]=mg(ls[x],ls[y],l,m); 
    rs[x]=mg(rs[x],rs[y],m+1,r);
    pu(x);return x;
}
struct edge{int to,nxt;}e[N<<1];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int d[N],top[N],siz[N],f[N];
void dfs(int x){
    siz[x]=1;
    fl(i,x)if(to!=f[x]){
        f[to]=x;d[to]=d[x]+1;
        dfs(to);
        siz[x]+=siz[to];
    }
}
void bt(int x,int tp){
    top[x]=tp;int k=0;
    fl(i,x)if(to!=f[x]&&siz[to]>siz[k])k=to;
    if(k)bt(k,tp);
    fl(i,x)if(!top[to])bt(to,to);
}
il int lca(int x,int y){
    while(top[x]!=top[y])
        d[top[x]]>d[top[y]]?x=f[top[x]]:y=f[top[y]];
    return d[x]<d[y]?x:y;
}
void solve(int x){
    fl(i,x)if(to!=f[x])
        solve(to),
        RT[x]=mg(RT[x],RT[to]);
    if(s[RT[x]])ans[x]=S[RT[x]];
}
int main(){
    in(n,q);
    int x,y,w;
    Fur(i,2,n)in(x,y),add(x,y),add(y,x);
    dfs(1);bt(1,1);
    while(q--){
        in(x,y,w);
        int t=lca(x,y);
        upd(RT[x],w,1);upd(RT[y],w,1);
        upd(RT[t],w,-1);upd(RT[f[t]],w,-1);
    }
    solve(1);
    Fur(i,1,n)out(ans[i]),pt('\n');
    flush();
}

LG 3521 [POI2011]ROT-Tree Rotations

给一棵n(1 \le n \le 200000)个叶子的二叉树,可以交换每个点的左右子树,要求前序遍历叶子的逆序对最少

启发式合并
comment评论
Search
search