P9598 [JOI Open 2018] 山体滑坡

· · 题解

思路：

省选模拟赛题，场切了，来写个题解。

我们发现，如果图形态固定，考虑从 [1, p] 算 [1, p + 1] 的答案，显然只需要计算出 p + 1 连接了 [1, p] 的导出子图中多少个联通块即可；直接并查集维护。

考虑如何做动态加边，删边；容易发现我们做加边似乎是容易的，故考虑回滚莫队的思想。

按照时间轴分块，先将 [1, id - 1] 块内的操作和询问做完，然后再做 id 块的询问；考虑按照 p 作扫描线，设 L_{id} 为这个块的左端点，然后对于询问 (w, p) 暴力将 [L_{id}, w] 的操作加入进来，算合并的联通块个数，然后再撤回。

看起来很对，但是在 [L_{id}, w] 的操作时可能会删除 [1, id - 1] 块内的边，于是考虑先对于 [L_{id}, R_{id}] 会造成影响的边，在扫描 p 的时候，先不加入进来，每次将 [L_{id}, w] 内的边的状态取反，然后再插入 [L_{id}, R_{id}] 内的边，这样就是对的。

时间复杂度为 O((N + Q) \sqrt{N})。

完整代码：


 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define hash(x, y) 1ll * x * (n - 1) + y
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, q, x, y, cnt, t, k, s, _s;
int a[N], b[N], g[N], id[N], ans[N];
ll h[N];
bool f[N], _f[N];
vector<int> E[N];
vector<pair<int, int>> Q[N];
vector<pair<pair<int, int>, int>> V[N];
inline void add(int u, int v){
    E[u].push_back(v);
}
namespace DSU{
    int fa[N], _fa[N];
    inline void init(){
        s = _s = 0;
        for(int i = 1; i <= n; ++i)
          fa[i] = _fa[i] = i;
    }
    inline int Find(int x){
        if(x != fa[x])
          return fa[x] = Find(fa[x]);
        return fa[x];
    }
    inline int _Find(int x){
        if(x != _fa[x])
          return _fa[x] = _Find(_fa[x]);
        return _fa[x];
    }
    inline void merge(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y)
          return ;
        fa[x] = y;
        ++s;
    }
    inline void _merge(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y)
          return ;
        x = _Find(x), y = _Find(y);
        if(x == y)
          return ;
        _fa[x] = y;
        ++_s;
    }
    inline void tidy(int x){
        x = Find(x);
        _fa[x] = x;
    }
};
inline void sol(int now, bool F){
    int l = (now - 1) * t + 1, r = min(now * t, m);
    DSU::init();
    for(int i = 1; i <= n; ++i)
      E[i].clear(), Q[i].clear();
    for(auto t : V[now]){
        if(F)
          Q[t.fi.se + 1].push_back({t.fi.fi, t.se});
        else
          Q[t.fi.se].push_back({t.fi.fi, t.se});
    }
    for(int i = 1; i < l; ++i)
      if(f[g[i]] && !_f[g[i]])
        F ? add(a[i], b[i]) : add(b[i], a[i]);
    for(int u = (F ? n : 1); (F ? u >= 1 : u <= n); (F ? (--u) : (++u))){
        for(auto v : E[u])
          DSU::merge(u, v);
        for(auto t : Q[u]){
            _s = 0;
            for(int i = l; i <= t.fi; ++i)
              f[g[i]] ^= 1;
//          cerr << l << ' ' << r << ' ' << s << '\n';
            for(int i = l; i <= r; ++i)
              if(f[g[i]] && (F ? a[i] >= u : b[i] <= u))
                DSU::_merge(a[i], b[i]);
            ans[t.se] += s + _s;
            for(int i = l; i <= r; ++i)
              if(f[g[i]] && (F ? a[i] >= u : b[i] <= u))
                DSU::tidy(a[i]), DSU::tidy(b[i]);
            for(int i = l; i <= t.fi; ++i)
              f[g[i]] ^= 1;
        }
    }
}
bool End;
int main(){
//  open("cruising.in", "cruising.out");
    n = read(), m = read(), q = read();
    for(int i = 1; i <= m; ++i){
        read(), a[i] = read() + 1, b[i] = read() + 1;
        if(a[i] > b[i])
          swap(a[i], b[i]);
        h[++cnt] = hash(a[i], b[i]);
    }
    sort(h + 1, h + cnt + 1);
    cnt = unique(h + 1, h + cnt + 1) - (h + 1);
    for(int i = 1; i <= m; ++i)
      g[i] = lower_bound(h + 1, h + cnt + 1, hash(a[i], b[i])) - h;
    t = 705;
    for(int i = 1; i <= m; ++i)
      id[i] = (i - 1) / t + 1;
    for(int i = 1; i <= q; ++i){
        x = read() + 1, y = read() + 1;
        V[id[x]].push_back({{x, y}, i});
    }
    for(int now = 1; now <= (m + t - 1) / t; ++now){
        int l = (now - 1) * t + 1, r = min(now * t, m);
        for(int i = l; i <= r; ++i)
          _f[g[i]] = 1;
        sol(now, 0);
        sol(now, 1);
        for(int i = l; i <= r; ++i){
            _f[g[i]] = 0;
            f[g[i]] ^= 1;
        }
    }
    for(int i = 1; i <= q; ++i){
        write(n - ans[i]);
        putchar('\n');
    }
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}
``