浅谈线段树分治

2022/6/2 23:21:15

编程Tag： int find first FF 浅谈 sz 分治线段 rec

本文主要是介绍浅谈线段树分治，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思想

离线，把询问拆成若干个区间，放到线段树上，在线段树上递归处理，进一个区间就执行操作，出一个区间就撤销执行了的操作，需要支持可回退。

题

P5787 二分图 /【模板】线段树分治

以时间为轴建线段树，把所有的边都放到线段树对应的区间里，走到这个区间时就连边，可以使用扩展域并查集判二分图，并查集不写路径压缩可以支持回退，需要用按秩合并或势能保证复杂度。

Code

#include
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int _=4e5+5;
int n,m,k;
int ff[_],sz[_];
vector s[_<<1];
int find(int x){return ff[x]==x?x:find(ff[x]);}
void ins(int x,int l,int r,int xl,int xr,pii v){
    if(l > xr || r < xl) return;
    if(xl<=l&&xr>=r){
        s[x].push_back(v);
        return;
    }
    int mid=l+r>>1;
    if(xl<=mid) ins(ls,l,mid,xl,xr,v);
    if(xr>mid) ins(rs,mid+1,r,xl,xr,v);
}
void con(int x,int y,deque &rec){
    int a=find(x),b=find(y);
    if(sz[a]>sz[b]) swap(a,b);
    ff[a]=b,sz[b]+=sz[a];
    rec.push_front({a,b});
}
void solve(int x,int l,int r){
    deque rec;
    for(auto v:s[x]){
        int a=find(v.first),b=find(v.second);
        // cout<<a<<" "<<b<<endl;
        // cout<<"*: "<<v.first<<" "<<v.second<<endl;
        if(a==b){
            for(int i=l;i<=r;++i) cout<<"No\n";
            for(auto v:rec) sz[v.second]-=sz[v.first],ff[v.first]=v.first;
            return;
        }
        con(v.first+n,v.second,rec);
        con(v.first,v.second+n,rec);
    }
    if(l==r) cout<<"Yes\n";
    else{
        int mid=l+r>>1;
        solve(ls,l,mid),solve(rs,mid+1,r);
    }
    for(auto v:rec) sz[v.second]-=sz[v.first],ff[v.first]=v.first;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;++i){
        int x,y,l,r; cin>>x>>y>>l>>r;
        ins(1,1,k,l+1,r,{x,y});
    }
    for(int i=1;i<=2*n;++i) sz[ff[i]=i]=1;
    solve(1,1,k);
    return 0;
}

P5227 [AHOI2013]连通图

以集合为轴建线段树，不会被删除的边在预处理时直接加入，递归线段树区间依次加入会被删除的边（注意一下边加入的范围，在上一次之后到下一次之前），用并查集很好判断是否连通且可回退。

Code

#include
#define ls x<<1
#define rs x<<1|1
#define pii pair<int,int>
using namespace std;
const int _=8e5+5;
int n,m,k;
int ff[_],sz[_],cnt;
vector s[_];
pii e[_];
bool vis[_];
map<int,int> pre;
int find(int x){return ff[x]==x?x:find(ff[x]);}
void solve(int x,int l,int r){
    deque rec;
    for(auto v:s[x]){
        int a=find(v.first),b=find(v.second);
        if(a==b) continue;
        if(sz[a]>sz[b]) swap(a,b);
        ++cnt,ff[a]=b,sz[b]+=a,rec.push_front(a);
    }
    if(l==r) cout<<(cnt==n-1?"Connected\n":"Disconnected\n");
    else{
        int mid=l+r>>1;
        solve(ls,l,mid),solve(rs,mid+1,r);
    }
    for(auto v:rec) sz[ff[v]]-=sz[v],ff[v]=v,--cnt;
}
void ins(int x,int l,int r,int xl,int xr,pii v){
    if(xl>xr) return;
    if(xl<=l&&xr>=r) {s[x].push_back(v);return;}
    int mid=l+r>>1;
    if(xl<=mid) ins(ls,l,mid,xl,xr,v);
    if(xr>mid) ins(rs,mid+1,r,xl,xr,v);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) sz[ff[i]=i]=1;
    for(int i=1;i<=m;++i) cin>>e[i].first>>e[i].second;
    cin>>k;
    for(int i=1;i<=k;++i){
        int t; cin>>t;
        while(t--){
            int x; cin>>x;
            vis[x]=1;
            ins(1,1,k,pre[x]+1,i-1,e[x]);
            pre[x]=i;
        }
    }
    for(auto v:pre) if(v.second) ins(1,1,k,pre[v.first]+1,k,e[v.first]);
    for(int i=1;i<=m;++i){
        if(!vis[i]){
            // cout<<"Pre: "<<i<<endl;
            int a=find(e[i].first),b=find(e[i].second);
            if(a==b) continue;
            if(sz[a]>sz[b]) swap(a,b);
            ++cnt,ff[a]=b,sz[b]+=a;
        }
    }
    solve(1,1,k);
    return 0;
}

CF1681F Unique Occurrences

数数方式：每种颜色单独算贡献，选一个颜色，去除所有这种颜色的边，当前颜色贡献为所有连通块大小两两相乘再相加。

以颜色为轴，去除一种颜色的边等价于在处理这个颜色之前和处理完这个颜色之后才加入这条边，同理并查集维护连通块即可。

Code

#include
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int _=5e5+5;
int n,ff[_],sz[_];
long long ans;
vector E[_<<2],col[_];
int find(int x){return ff[x]==x?x:find(ff[x]);}
void insert(int x,int l,int r,int xl,int xr,pii v){
    if(xl>xr) return;
    if(xl<=l&&xr>=r) {E[x].push_back(v);return;}
    int mid=l+r>>1;
    if(xl<=mid) insert(ls,l,mid,xl,xr,v);
    if(xr>mid) insert(rs,mid+1,r,xl,xr,v);
}
void calc(int x,int l,int r){
    deque rec;
    for(auto v:E[x]){
        int a=find(v.first),b=find(v.second);
        if(sz[a]>sz[b]) swap(a,b);
        ff[a]=b,sz[b]+=sz[a],rec.push_front({a,b});
    }
    if(l==r) for(auto v:col[l]) ans+=1ll*sz[find(v.first)]*sz[find(v.second)];
    else calc(ls,l,l+r>>1),calc(rs,(l+r>>1)+1,r);
    for(auto v:rec) ff[v.first]=v.first,sz[v.second]-=sz[v.first];
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) sz[ff[i]=i]=1;
    for(int i=1;i<n;++i){
        int x,y,z; cin>>x>>y>>z;
        col[z].push_back({x,y});
        insert(1,1,n,1,z-1,{x,y});
        insert(1,1,n,z+1,n,{x,y});
    }
    calc(1,1,n);
    cout<<ans;
    return 0;
}

这篇关于浅谈线段树分治的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

浅谈线段树分治

思想

题

P5787 二分图 /【模板】线段树分治

P5227 [AHOI2013]连通图

CF1681F Unique Occurrences

相关编程文章