分治
本篇重点讲三个东西，线段树分治，点分治，以及CDQ分治。
TOP1 线段树分治
- 这个算法主要是针对于一些对在线算法很不友好的题，其模型大概是维护一张图，其中的边在某个固定时刻存在，其余时刻不存在，并在某些时刻让你针对于那个时刻的图做一些询问。
确实一听就很恶心,你总不能全靠\(LCT\)- 所以这个基于时间轴来分治的线段树分治就有了，其实如果看过线段树优化建图的话，这个就非常好理解了,具体来讲就是把操作和询问离线下来，对于每条边所覆盖的时间区间打上标记，在从根向那个时间搜的时候，一边
dfs一边就把当时有的边建了出来，在搜到叶子节点时处理答案，回溯的时候将建的边撤销，这时就得用上可撤销并查集了(其实就是不路径压缩的按秩合并存一下连边前状态)。然后这个线段树分治就做完了。 - 当然，我们离线下来的轴不一定是时间，类似的只要是基于某个轴的操作都可以进行。
- 例题推荐的话P5787
这个针灸纯板子,就是用了一个扩展域并查集查二分图的\(trick\)
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 2e6 + 10, Inf = 0x3f3f3f3f, Mod = 5000007;
int n, m, k;
int heigh[maxn << 1];
struct EDGE{int from, to;}wmx[maxn];
struct STK{int x, y, hig;}stk[maxn];
int top = 0;
int fa[maxn << 1];
struct Set_Union {
fuc(void, init)(){fr(i, 1, n << 1)fa[i] = i, heigh[i] = 1;}
fuc(int , find)(int x) {while(x != fa[x])x = fa[x]; return x;}
fuc(void, merge)(int x, int y) {
x = find(x), y = find(y);
if(heigh[x] > heigh[y])swap(x, y);
fa[x] = y;
stk[++top] = (STK){x, y, heigh[x] == heigh[y]};
heigh[y] += (heigh[x] == heigh[y]);
}
}F;
struct Seg_Tree {
#define lsp(rt) (rt << 1)
#define rsp(rt) (rt << 1 | 1)
#define mid ((l + r) >> 1)
vector <int> vec[maxn];
fuc(void, insert)(int rt, int l, int r, int L, int R, int val) {
if(L <= l && r <= R) {return vec[rt].pb(val), void();}
if(L <= mid)insert(lsp(rt), l, mid, L, R, val);
if(R > mid)insert(rsp(rt), mid + 1, r, L, R, val);
}
fuc(void, query)(int rt, int l, int r) {
int is = 1, sz = vec[rt].size();
int lst = top;
delfr(i, 0, sz) {
int pos = vec[rt][i];
int from = wmx[pos].from, to = wmx[pos].to;
int ffrom = F.find(from), fto = F.find(to);
if(ffrom != fto) {
F.merge(from, to + n);
F.merge(to, from + n);
}else {
is = 0;
fr(j, l, r) {
puts("No");
}
break;
}
}
if(is && l == r) puts("Yes");
if(is && l != r) query(lsp(rt), l, mid), query(rsp(rt), mid + 1, r);
while(top > lst) {
int x = stk[top].x;
int y = stk[top].y;
heigh[y] -= stk[top].hig;
fa[x] = x;
top--;
}
}
}T;
signed main(){
n = read(), m = read(), k = read();
F.init();
fr(i, 1, m) {
int x = read(), y = read(), l = read(), r = read();
wmx[i].from = x, wmx[i].to = y;
T.insert(1, 1, k, l + 1, r, i);//有0时刻没用
}
T.query(1, 1, k);
}
- 其余的还有地理课，\(No Rest for the Wicked\) 等