当前位置: 首页 > news >正文

线段树分治

作用

处理一些加边删边问题。

实现

不知道为啥叫线段树分治,不如叫时间线段树。

如果一条边 \(e\)\(l\) 时刻加入 \(r\) 时刻删除,那么可以看成在 \([l,r)\) 的时刻内都有这条边。

考虑用线段树维护时刻,给线段树上每个区间维护一个 vector,里面存覆盖了这个区间的边。

然后询问时就在线段树上递归,每次把这个区间的边加进一个数据结构中,当离开这个区间时,把这个区间中的边给撤销。

所以维护边的数据结构要支持撤销,一般使用可撤销并查集。

题目

【模板】线段树分治

首先先把题目的 \(l\) 时刻出现,\(r\) 时刻删除变成在 \([l+1,r]\) 时刻内出现。

考虑如何快速判定二分图,可以考虑扩展域并查集,也就是维护两个集合 \(S\)\(T\),每次添加一条边 \((u,v)\),若这两个点属于相同的集合,那么就不是二分图。

有了这个,对时间开一棵线段树,再用可撤销并查集维护边即可。

代码
#include <bits/stdc++.h>void Freopen() {freopen("", "r", stdin);freopen("", "w", stdout);
}using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;int n, m, K;struct DSU {int fa[N], siz[N], n;vector< pair< int, int> > del;DSU() {}DSU( int _n) {n = _n; del.clear();for ( int i = 1; i <= n; i ++) siz[i] = 1, fa[i] = i;}int find( int x) {return x == fa[x] ? x : find(fa[x]);}int merge( int u, int v) {u = find(u), v = find(v);if (u == v) return 0;if (siz[u] < siz[v]) swap(u, v);del.push_back({u, v});siz[u] += siz[v], fa[v] = u;return 1;}void Del() {if (! del.size()) return ;auto [u, v] = del.back(); del.pop_back();siz[u] -= siz[v], fa[v] = v;}
} D;vector< pair< int, int> > tr[N * 4];void ins( int x, int y, pair< int, int> e, int k = 1, int l = 1, int r = K) {if (x > y) return ;if (x <= l && r <= y) return tr[k].push_back(e), void();int mid = (l + r) >> 1;if (x <= mid) ins(x, y, e, k << 1, l, mid);if (y > mid) ins(x, y, e, k << 1 | 1, mid + 1, r);
}void solve( int k = 1, int l = 1, int r = K) {int tot = 0; // tot 表示这个区间加了多少边for ( auto [u, v] : tr[k]) {if (D.find(u) == D.find(v)) {for ( int i = l; i <= r; i ++)cout << "No\n";while (tot --) D.Del();return ;}tot += D.merge(u, v + n);tot += D.merge(u + n, v);}if (l == r) {cout << "Yes\n";while (tot --) D.Del();return ;}int mid = (l + r) >> 1;solve(k << 1, l, mid), solve(k << 1 | 1, mid + 1, r);while (tot --) D.Del();
}signed main() {ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> K;D = DSU(2 * n);for ( int i = 1; i <= m; i ++) {int x, y, l, r;cin >> x >> y >> l >> r;l ++;ins(l, r, make_pair(x, y));}solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=28931

相关文章:

  • 2025双氧水供应厂家推荐:苏州市岚昱化工品质卓越选择!
  • 2025婚纱照拍摄推荐,南通造物摄影有限公司专业团队打造梦幻
  • 2025上海保洁公司最新推荐榜:高效清洁与贴心服务的优质选择
  • 10.11
  • 「解题报告」蓝桥杯2013省AB 错误票据
  • 2025精密弹簧优质厂家推荐:蓝侨盈科技,精准弹性解决方案!
  • 时时想起 寸步难行 叩问自己 无人回应 若我离去 若我死去 枯萎于这幽暗的井底 长眠不醒
  • 有限空间作业安全无死角!AI 视觉守护人员与操作合规
  • 2025抖音推广服务商最新推荐榜:精准引流与高效转化的营销利
  • 2025甘肃西服定制店推荐榜单:匠心工艺与贴心服务的完美结合
  • 完整教程:计算机毕业设计免费领源码-教师教学进度管理及建议系统的设计与实现
  • 2025表面瑕疵检测设备厂家最新推荐:精准高效,工业品质之选
  • 战略、运营、经营三循环:企业卓越绩效的密码 - 智慧园区
  • 2025书包柜定做厂家推荐:杰尚家具专业定制,品质卓越!
  • 2025环氧板定制厂家推荐:一博科技材料,专业定制品质卓越!
  • 2025农机带实力厂家推荐:浙江三星胶带,品质卓越供货无忧!
  • 打不动十个
  • CSP-S模拟29 2025.10.11
  • 2025风机盘管优质厂家推荐:洛卡尔环境科技,高效节能首选!
  • 最简单实用的SQL注入检测方法:Break Repair技巧详解
  • 2025拉伸器厂家最新推荐榜:专业制造与优质服务的行业佼佼者
  • 个性化推荐系统技术解析
  • NOIP20251009E
  • 2025七水硫酸锌订做厂家推荐榜:品质保证与客户信赖之选
  • 2025螺杆泵厂家最新推荐榜:高效稳定与优质服务的行业首选!
  • 2025南通婚纱摄影最新推荐榜:创意拍摄与贴心服务的完美结合
  • 语义slam - MKT
  • 尝试茶叶数据集
  • 2025氧化镁供应厂家推荐:松辽镁业高纯度优质选择!
  • 2025硅藻土订制厂家口碑推荐:品质卓越与专业服务的双重保障