线段树分治

· · 个人记录

前言

这个东西常和线段树二分搞混，然而这俩是完全不一样的东西。

抄了 luogu 中 xht 的题解。

核心思想

考虑这样一个问题：

  1. 有一些操作，每个操作只在 l∼r 的时间段内有效。
  2. 有一些询问，每个询问某一个时间点所有操作的贡献。

对于这样的询问，我们可以离线后在时间轴上建一棵线段树，这样对于每个操作，相当于在线段树上进行区间操作。

遍历整颗线段树，到达每个节点时执行相应的操作，然后继续向下递归，到达叶子节点时统计贡献，回溯时撤销操作即可。

这样的思想被称为线段树分治，可以在低时间复杂度内解决一类在线算法并不优秀的问题

题目引入

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

首先把操作堆到一个时间的线段树上，然后考虑从根节点走到叶子结点相当于是维护加边，最后到叶子节点询问是否存在奇环（二分图充要条件），接着从叶子节点走回根节点，维护撤销加边。

可以发现这个加边、判断奇环、撤销边的过程可以用可撤销扩展域并查集维护。

时间复杂度 O(m \log n \log k)

另外这个题面写的比较糖，时间段 1 指的是 (0,1) 这个时间开区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,k;
int fa[N*2],sz[N*2];
inline int cg(int x){
    if(x<=n)return x+n;
    return x-n;
}
int find(int x){if(x==fa[x])return x;return find(fa[x]);}
stack<int>st;
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y){return;}
    if(sz[x]>sz[y])swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];st.push(x);
}
inline void split(){
    int x=st.top();st.pop();
    sz[fa[x]]-=sz[x];fa[x]=x;
}
struct Izayoi_Sakuya{
    vector<pair<int,int> >g[N<<2];
    inline int ls(int p){return p<<1;}inline int rs(int p){return p<<1|1;}
    void change(int p,int nl,int nr,int ml,int mr,pair<int,int>k){
        if(nl<=ml&&mr<=nr){g[p].push_back(k);return;}
        int mid=ml+mr>>1;
        if(nl<=mid){change(ls(p),nl,nr,ml,mid,k);}
        if(mid+1<=nr){change(rs(p),nl,nr,mid+1,mr,k);}
    }
    void query(int p,int ml,int mr){
        int tim=st.size();bool flag=1;
        for(int i=0;i<g[p].size();i++){
            pair<int,int>tmp=g[p][i];
            if(find(tmp.first)==find(tmp.second)){
                for(int j=ml;j<=mr;j++){cout<<"No\n";}
                flag=0;break;
            }
            merge(tmp.first,cg(tmp.second));
            merge(tmp.second,cg(tmp.first));
        }
        if(flag){
            int mid=ml+mr>>1;
            if(ml==mr){cout<<"Yes\n";}
            else {query(ls(p),ml,mid);query(rs(p),mid+1,mr);}
        }
        while(st.size()>tim){split();}
    }
}IS;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<N*2;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++){
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        if(l==r)continue;
        IS.change(1,l+1,r,1,k,{x,y});
    }
    IS.query(1,1,k);
    return 0;
}

不过值得注意的是，这东西一般不能支持一遍加入删除（即修改）一遍查询，因为这样的时间复杂度是错的。

比如说我每次都是全局添加线段，每次都全局查询，那么这个 vector 就会遍历平方次。

所以通常这种题都是修改删除完了之后最后问你一个很大的问题。（通常是遍历整个线段树）

更多例题

CF1681F Unique Occurrences

好啊，懵逼了，这甚至都感觉和线段树分治没关系！

所以要把边理解为添加边和删除边。

我们发现如果把某一种颜色 w 的所有边去掉，然后把 w 两端的联通块大小乘一下就对了。

这东西就直接写了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n;vector<pair<int,int> >e[N];
ll fa[N],sz[N];ll genshin;
int find(int x){if(fa[x]==x)return x;return find(fa[x]);}
stack<int>st;
inline void merge(int x,int y){
    x=find(x),y=find(y);if(x==y){return;}
    if(sz[x]>sz[y])swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];
    st.push(x);
}
inline void split(){int x=st.top();sz[fa[x]]-=sz[x];fa[x]=x;st.pop();}
struct Izayoi_Sakuya{
    vector<pair<int,int> >g[N<<2];
    inline int ls(int p){return p<<1;}inline int rs(int p){return p<<1|1;}
    void change(int p,int nl,int nr,int ml,int mr,pair<int,int>k){
        if(nl>nr)return;
        if(nl<=ml&&mr<=nr){g[p].push_back(k);return;}
        int mid=ml+mr>>1;
        if(nl<=mid){change(ls(p),nl,nr,ml,mid,k);}
        if(mid+1<=nr){change(rs(p),nl,nr,mid+1,mr,k);}
    }
    void query(int p,int ml,int mr){
        int tim=st.size();
        for(int i=0;i<g[p].size();i++){merge(g[p][i].first,g[p][i].second);}
        if(ml==mr){
            for(int i=0;i<e[ml].size();i++){
                genshin+=sz[find(e[ml][i].first)]*sz[find(e[ml][i].second)];
            }while(st.size()>tim)split();
            return;
        }
        int mid=ml+mr>>1;
        query(ls(p),ml,mid);query(rs(p),mid+1,mr);
        while(st.size()>tim)split();
    }
}IS;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;for(int i=0;i<N;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<n;i++){
        int u,v,w;cin>>u>>v>>w;e[w].push_back(make_pair(u,v));
        IS.change(1,1,w-1,1,n,make_pair(u,v));
        IS.change(1,w+1,n,1,n,make_pair(u,v));
    }
    IS.query(1,1,n);cout<<genshin;
    return 0;
}

P5631 最小mex生成树

没有什么区别（

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,MAXW=1e5+5;
int n,m;
int fa[N],sz[N];
int find(int x){if(fa[x]==x)return x;return find(fa[x]);}
stack<int>st;
inline void merge(int x,int y){
    x=find(x),y=find(y);if(x==y){return;}
    if(sz[x]>sz[y])swap(x,y);
    fa[x]=y;
    sz[y]+=sz[x];
    st.push(x);
}
inline void split(){int x=st.top();sz[fa[x]]-=sz[x];fa[x]=x;st.pop();}
struct Izayoi_Sakuya{
    vector<pair<int,int> >g[N<<2];
    inline int ls(int p){return p<<1;}inline int rs(int p){return p<<1|1;}
    void change(int p,int nl,int nr,int ml,int mr,pair<int,int>k){
        if(nl>nr)return;
        if(nl<=ml&&mr<=nr){g[p].push_back(k);return;}
        int mid=ml+mr>>1;
        if(nl<=mid){change(ls(p),nl,nr,ml,mid,k);}
        if(mid+1<=nr){change(rs(p),nl,nr,mid+1,mr,k);}
    }
    void query(int p,int ml,int mr){
        int tim=st.size();
        for(int i=0;i<g[p].size();i++){merge(g[p][i].first,g[p][i].second);}
        if(ml==mr){
            if(sz[find(1)]==n){cout<<ml<<endl;exit(0);}
            while(st.size()>tim)split();
            return;
        }
        int mid=ml+mr>>1;
        query(ls(p),ml,mid);query(rs(p),mid+1,mr);
        while(st.size()>tim)split();
    }
}IS;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;for(int i=0;i<N;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        IS.change(1,1,w-1,1,MAXW,make_pair(u,v));
        IS.change(1,w+1,MAXW,1,MAXW,make_pair(u,v));
    }
    IS.query(1,1,MAXW);
    return 0;
}