线段树分治

适用问题类型:

对于一些操作,存在时间限制 $[l,r]$ ,

询问每一刻所有操作的贡献。

对于这种题型,有优秀的离线做法——线段树分治 $\Theta(n\log^2 n)$ 。

线段树分治是一种思想,把 $[l,r]$ 拆成 $\log$ 个线段树区间,然后分治处理情况。

你也可以真的开一棵线段树去存取你想要的信息。

模板题 LuoguP5787

可撤销并查集+线段树分治。

并查集维护当前是否有出现奇环。

/* code */

vector<int> t[N << 2]; 
stack<pii> sta;

void ins(int p, int l, int r, int L, int R, int d) {
    if (L <= l && R >= r) return t[p].pb(d);
    int mid = l + r >> 1;
    if (L <= mid) ins(p << 1, l, mid, L, R, d);
    if (R > mid) ins(p << 1 | 1, mid + 1, r, L, R, d);
}

int fa[N], d[N], dep[N]; pii e[N << 1];

int get(int x) {return x == fa[x] ? x : get(fa[x]);}
int dis(int x) {return x == fa[x] ? d[x] : d[x] ^ dis(fa[x]);} 

bool merge(int x, int y) {
    int p = get(x), q = get(y);
    if (p == q) return 0;
    if (dep[q] > dep[p]) swap(p, q);
    fa[q] = p; d[q] = dis(x) ^ dis(y) ^ 1;
    sta.push(mk(q, dep[p] == dep[q])); 
    dep[p] += (dep[p] == dep[q]); 
    return 1;
}

void solve(int p, int l, int r) {
    ui lst = sta.size();
    bool flag = 1;
    for (auto i : t[p]) {
        int x = e[i].fi, y = e[i].se;
        if (!merge(x, y)) {
            if (dis(x) ^ dis(y) ^ 1) {
                rep(j, l, r) puts("No"); 
                flag = 0; break;
            }
        } 
    } 
    if (flag) {
        int mid = l + r >> 1;
        if (l == r) puts("Yes");
        else solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r);    
    } 
    int x; while (sta.size() != lst) 
        dep[fa[x = sta.top().fi]] -= sta.top().se, fa[x] = x, d[x] = 0, sta.pop();
}

void solve() {
    int n, m, k; qr(n), qr(m), qr(k);
    rep (i, 1, m) {
        int x, y, l, r; qr(x), qr(y), qr(l), qr(r);
        e[i] = mk(x, y); ins(1, 1, k, l + 1, r, i);
    }
    rep (i, 1, n) fa[i] = i;
    solve(1, 1, k);
}

int main() {
    //int T; qr(T); while (T--) {
        solve();
    //}
    return 0;
}

例题 CF 1140F

对于这种题,一般有一个套路,就是把行和列看成二分图。

对于这道题,如果 $(x_1,y_1),(x_1,y_2),(x_2, y_1)$ 都存在,那么 $(x_2,y_2)$ 也存在。

可以规约为一个连通块内行点个数和列点个数的乘积个元素。证明类似于生成树上对于每四个点 $(x_1,y_1,x_2,y_2)$ 添上一条边 $(x_1,y_2)$ 。

之后就是套路线段树分治维护可撤销并查集。

vector<int> t[N << 2]; pii e[N], sta[N << 1], cc[N];
int fa[N << 1], dep[N << 1], cx[N << 1], cy[N << 1], top;
ll ans, Ans[N]; 
 
void ins(int p, int l, int r, int L, int R, int d) {
    if (L <= l && R >= r) return t[p].pb(d);
    int mid = l + r >> 1; 
    if (L <= mid) ins(p << 1, l, mid, L, R, d);
    if (R > mid) ins(p << 1 | 1, mid + 1, r, L, R, d);
}
 
int get(int x) {return x == fa[x] ? x : get(fa[x]);} 
 
void merge(int x, int y) {
    int p = get(x), q = get(y);
    if (p == q) return ;
    if (dep[q] > dep[p]) swap(p, q);
    ans -= 1ll * cx[p] * cy[p] + 1ll * cx[q] * cy[q]; 
    fa[q] = p; cx[p] += cx[q]; cy[p] += cy[q];
    sta[++top] = mk(q, dep[p] == dep[q]);
    dep[p] += (dep[p] == dep[q]);
    ans += 1ll * cx[p] * cy[p];
}
 
void dfs(int p, int l, int r) {
    int lst = top;
    for (auto i : t[p]) {
        int x = e[i].fi, y = e[i].se;
        merge(x, y); 
    } 
    int mid = l + r >> 1;
    if (l == r) Ans[l] = ans;
    else dfs(p << 1, l, mid), dfs(p << 1 | 1, mid + 1, r);
    while (top != lst) {
        int y = sta[top].fi, d = sta[top].se, x = fa[y];
        dep[x] -= d; ans -= 1ll * cx[x] * cy[x];
        cx[x] -= cx[y]; cy[x] -= cy[y];
        ans += 1ll * cx[x] * cy[x] + 1ll * cx[y] * cy[y];
        fa[y] = y; --top;
    }
}
 
map<pii, int> pos; int cnt;
 
void solve() {
    int n; qr(n);
    rep (i, 1, n) {
        int x, y; qr(x), qr(y);
        pii t = mk(x, y + Max);    
        if (!pos.count(t)) {
            pos[t] = ++cnt;
            e[cnt] = mk(x, y + Max);
            cc[cnt].fi = i;
        } else {
            cc[pos[t]].se = i - 1;
            pos.erase(t);
        }
    }
    rep (i, 1, cnt) if (!cc[i].se) cc[i].se = n;
    rep (i, 1, cnt) ins(1, 1, n, cc[i].fi, cc[i].se, i);
    rep (i, 1, Max * 2) fa[i] = i, cx[i] = (i <= Max), cy[i] = 1 - cx[i];
    ans = 0; dfs(1, 1, n);
    rep (i, 1, n) pr1(Ans[i]);
}