专栏文章

P9598 [JOI Open 2018] 山体滑坡

GGenius_Star影
P9598题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miq6c70z
此快照首次捕获于
2025/12/03 23:40
3 个月前
此快照最后确认于
2025/12/03 23:40
3 个月前
查看原文

思路：

省选模拟赛题，场切了，来写个题解。
我们发现，如果图形态固定，考虑从 [1,p][1, p] 算 [1,p+1][1, p + 1] 的答案，显然只需要计算出 p+1p + 1 连接了 [1,p][1, p] 的导出子图中多少个联通块即可；直接并查集维护。
考虑如何做动态加边，删边；容易发现我们做加边似乎是容易的，故考虑回滚莫队的思想。
按照时间轴分块，先将 [1,id−1][1, id - 1] 块内的操作和询问做完，然后再做 idid 块的询问；考虑按照 pp 作扫描线，设 LidL_{id} 为这个块的左端点，然后对于询问 (w,p)(w, p) 暴力将 [Lid,w][L_{id}, w] 的操作加入进来，算合并的联通块个数，然后再撤回。
看起来很对，但是在 [Lid,w][L_{id}, w] 的操作时可能会删除 [1,id−1][1, id - 1] 块内的边，于是考虑先对于 [Lid,Rid][L_{id}, R_{id}] 会造成影响的边，在扫描 pp 的时候，先不加入进来，每次将 [Lid,w][L_{id}, w] 内的边的状态取反，然后再插入 [Lid,Rid][L_{id}, R_{id}] 内的边，这样就是对的。
时间复杂度为 O((N+Q)N)O((N + Q) \sqrt{N})。

完整代码：

CPP
 #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;
}
``

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...