线段树分治

线段树分治

线段树分治，解决的是这样一类问题：有一个时间轴，有一些操作，这些操作在时间轴上每一个的作用范围是一个区间；在某些时间或者全局询问一些关于操作效果的问题。

它的重要效果是：一是可以把所有删除操作改成撤回操作（也就是撤回当前最近一个操作，而不是删除之前随便一个操作），可以和加入做到同时间复杂度。二是和扫描线类似，具有一个时序性，可以帮助维护。

我们具体这么做：把每一个操作拆成线段树上一些完整区间，并放到对应节点上；dfs 整棵线段树，具体流程是：进入节点时，做所有该节点上的操作；然后递归儿子；然后回溯，把所有该节点上的操作撤回。

这样做有什么性质：到达某一个叶子的时候，恰好是代表一个时刻，这时候的局面就是这个时刻的局面；走到区间 \([l, r]\) 的时候，区间 \([1, r]\) 中所有操作均已经做过一遍并且有的回溯了；当前节点所有操作一定是在栈顶。

其中第一个性质方便我们回答一些时刻相关的问题；而第二个性质不要小瞧，它正是刚刚所说的扫描线性质，这意味着你在维护一些东西的时候可以打标记，然后下传标记，这个标记打上去的时间知道（可能意味着那个时间的局面上某个整体被做了什么操作），但是之后这个整体可能被做了替换（后来加上了一些东西）。那么维护打上标记的时间和加上东西的时间，下传的时候判断加上东西的时间是不是晚于打上标记的时间，如果是，那么不应该下传（这个标记打的时候这个东西还不属于那个整体）。可能还有其他妙用，但是暂时总结了这个。总而言之第二个性质是重要的。

注意点：回溯的时候，所有操作是倒序删除的。

CF1814F

【题意】
有 \(n\) 个点，\(m\) 条边，每个点有一个区间 \([l, r]\)。称 \(a, b\) 相互可达当且仅当存在路径 \(v_0 = a, v_1, ..., v_k = b\) 使得 \(v_0, ..., v_k\) 的区间无交。求哪些点和 \(1\) 相互可达。

【分析】
显然直接在原图上不能做。不妨把时间看做区间，某一个时刻 \(t\)，图上有边 \((i ,j)\) 当且仅当 \((i, j) \in E\) 并且 \(t \in [l_i, r_i], t \in [l_j, r_j]\)。这样，我们对一个边的时效定义为这两个区间的交集。（考虑点是更不好的选择，更不本质，也更繁琐）

然后我们线段树分治，维护并查集（按秩合并，不用可持久化所以不用建立线段树）。

思考每一个修改是什么，是改变一个 \(fa\) 数组内的值（加边）；或者不动，这依赖于之前的局面，但不依赖于之后的局面。线段树分治使得它变得可行。改变元素个数 \(O(1)\)，可以直接记下来撤回。

到了叶子，是某一个时刻，和 \(1\) 相邻的所有点都在答案中，想到打标记在其根上，并且等到删边的时候下传。但是有个问题是，有可能下传的时候某些点是在根底下，但是打标记的时候并不和根属于同一集合。某个时刻打标记的意义是打在这一时刻的连通块上，所以这种点不能往下传。

因此记录一个打标记时间；然后某个边删除的时候，在哪个节点，意味着其存在的时间是这个节点表示的时间区间。判断这个区间是否包含打标记时间即可。由于 \(r\) 一定大于等于打标记时间，可以只判断 \(l\)。有新标记了，直接覆盖，因为之前和它在一起的节点们，如果断开了那么会继承标记，否则还是在同一个连通块内；后来加入的，应当让它能继承标记，因此兼容。

所以代码很简单。

时间复杂度：一共 \(O(m \log t)\) 个加边操作，每次耗时 \(O(\log n)\)。传 tag，每一个加边操作最多一次。于是总复杂度 \(O(m \log t \log n)\)，可以通过。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
int lt[200200], rt[200200]; int fa[200200], rnk[200200]; 
int tm[200200]; int zy = 200000; int n,m;int tag[200200];
int get(int x) {if(fa[x] == x) return x; else return get(fa[x]);}
struct delinfo {int i, j, k; };
struct SGT {
    vector<pii> ap[800200];stack<delinfo> stk;
    void add(int now, int x,int y,int l,int r, pii ed) {
        if(r<l)return;
        if(x>=l&&y<=r) { ap[now].push_back(ed); return;}
        if(x > r||y < l) return;
        int mid=(x+y)>>1;add(now*2,x,mid,l,r,ed);add(now*2+1,mid+1,y,l,r,ed); 
    }
    void addedge(pii x) {
        int i = get(x.first), j = get(x.second);
        if(i == j) {stk.push({0, 0, 0}); return;}
        else {
            if(rnk[i] > rnk[j]) swap(i, j);
            fa[i] = j; stk.push({i, j, rnk[j]}); rnk[j] = max(rnk[j], rnk[i] + 1);
        }
    }
    void deledge(delinfo x, int l) {
        if(x.i == 0) return; 
        else { 
            if(l <= tag[x.j]) tag[x.i] = tag[x.j];
            fa[x.i] = x.i; rnk[x.j] = x.k;
        }   
    }
    void dfs(int now,int l,int r) {
        for(pii i:ap[now]) {addedge(i);}
        if(l!=r){int mid=(l+r)>>1;dfs(now*2,l,mid);dfs(now*2+1,mid+1,r);}
        else {tag[get(1)]=l;}
        f(T,1,(int)ap[now].size()) {deledge(stk.top(),l);stk.pop();}
    }
}sgt;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    cin>>n>>m; f(i,1,n)fa[i]=i;
    f(i,1,n)cin>>lt[i]>>rt[i];
    f(i,1,m){
        int u,v;cin>>u>>v;sgt.add(1,1,zy,max(lt[u],lt[v]),min(rt[u],rt[v]), {u,v});
    }
    sgt.dfs(1,1,zy); vector<int> ans;
    f(i,1,n)if(tag[i])ans.push_back(i);
    sort(ans.begin(), ans.end());
    for(int i:ans)cout<<i<<" ";
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}
/*
2023/4/10
start thinking at 10:00


start coding at 21:30
finish debugging at 21:45
*/