首页 > 其他分享 >时间线段树(线段树分治)学习笔记

时间线段树(线段树分治)学习笔记

时间:2023-01-15 13:44:24浏览次数:59  
标签:int 线段 分治 undo fa 笔记 rk

时间线段树(线段树分治)学习笔记

思想

考虑如下问题:

进行若干次操作,每次操作都在一个时间段内有效,也就是先被添加然后可能被撤销。同时还进行询问,对于每个时刻,输出所有操作的贡献。

当这类题目在线比较难做时,就可能需要离线,并按照时间进行分治。分治的方法有两种,一种是采用时间线段树(又称线段树分治),另一种是采用 以前我总结过的一类分治 ,可以根据不同的题目看看哪种更适合。

时间线段树顾名思义,是在时间轴上建了一棵线段树,这样我们就把每个操作变为了线段树上的区间修改。算法流程是遍历整棵线段树,到达一个节点时执行这个节点的所有操作,然后继续向下递归,回溯时将操作撤销即可。

例题:P5787 二分图 /【模板】线段树分治

一个图是二分图的充要条件是图中不存在奇环,这个可以使用扩展域并查集维护。

然后照着算法流程做就好了。注意到回溯的时候需要撤销操作,因此需要使用可撤销并查集。为了撤销操作,并查集的形态需要被维持,因此采用按秩合并优化,注意不能采用路径压缩优化。在合并时,若 \(u\) 变成了 \(v\) 的父亲,就在操作栈中记录节点 \(v\) 以及这次合并导致 \(u\) 的秩的增加量。撤销时依次弹栈得到 \(v\),在并查集中找到 \(v\) 的父亲 \(u\)(这就是不能动并查集形态的原因),利用秩的增加量信息恢复 \(u\) 的秩,然后将 \(v\) 的父亲设为自己即可。

时间复杂度 \(\Theta(m\log n\log k)\)。

// Problem: P5787 二分图 /【模板】线段树分治
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5787
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;

int n, m, k, U[N], V[N], fa[N], rk[N];
stack<tuple<int, int>> undo;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
void merge(int x, int y) {
	x = find(x); y = find(y);
	if(rk[x] < rk[y]) swap(x, y);
	undo.emplace(y, rk[x] == rk[y]);
	chkmax(rk[x], rk[y] + 1);
	fa[y] = x;
}
struct SegTree {
	vector<int> t[N<<2];
	#define lc(u) (u<<1)
	#define rc(u) (u<<1|1)
	void insert(int u, int l, int r, int ql, int qr, int id) {
		if(ql > qr) return;
		if(ql <= l && r <= qr) {
			t[u].push_back(id);
			return;
		}
		int mid = (l + r) >> 1;
		if(ql <= mid) insert(lc(u), l, mid, ql, qr, id);
		if(qr > mid) insert(rc(u), mid+1, r, ql, qr, id);
	}
	void solve(int p, int l, int r) {
		bool ok = 1;
		int sz = undo.size();
		for(int i : t[p]) {
			int u = find(U[i]), v = find(V[i]);
			if(u == v) {
				rep(i, l, r) puts("No");
				ok = 0;
				break;
			}
			merge(U[i]+n, V[i]);
			merge(U[i], V[i]+n);
		}
		if(ok) {
			if(l == r) puts("Yes");
			else {
				int mid = (l + r) >> 1;
				solve(lc(p), l, mid);
				solve(rc(p), mid+1, r);
			}
		}
		while((int)undo.size() > sz) {
			int u = get<0>(undo.top()), d = get<1>(undo.top()); undo.pop();
			rk[fa[u]] -= d;
			fa[u] = u;
		}
	}
	#undef lc
	#undef rc
}sgt;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	rep(i, 1, 2*n) fa[i] = i, rk[i] = 0;
	rep(i, 1, m) {
		int l, r;
		scanf("%d%d%d%d", &U[i], &V[i], &l, &r);
		sgt.insert(1, 1, k, l+1, r, i);
	}
	sgt.solve(1, 1, k);
    return 0;
}

标签:int,线段,分治,undo,fa,笔记,rk
From: https://www.cnblogs.com/ruierqwq/p/segment-tree-offline.html

相关文章

  • 1-1. 凸优化(笔记)
    Course:最优化理论Textbook:《凸优化》-StephenBoydISBN:9787302297567一、引言1.1数学优化&符号二、凸集2.1仿射集合和凸集2.2重要的例子2.3保凸运算......
  • 线段树区间加、区间乘、区间推平、区间取相反数的通用处理办法
    首先声明:“通用”并不是万能,只是能维护这些操作下的大多数常见的区间信息。将数列中的每个元素视为一个一次函数\(f_i(x)=k_ix+b_i\)。假设数列为\(a\),则初始化\(f_i(x......
  • 拉链表笔记
    数仓拉链表概述,以及如何迭代或者回滚 1.背景拉链表是什么,在数仓建立时候,一种重要的表数据处理方式,可以将数据结构于算法,类比于拉链表于数仓,旨在解决数仓建立里面的SCD......
  • 动态规划笔记(三):其它的常见线性问题(未整理完)
    最长公共子序列(HDU-1159)注意子序列和子串的区别用\(dp[i][j]\)表示序列\(X\)前\(i\)项和序列\(Y\)的前\(j\)项的最长子序列的长度当\(x[i]=x[j]\)时,\(dp[i][j]=dp[i......
  • “笔记本无线网络搜索不到自家信号,却能搜到其他公司的信号”解决方法
    “笔记本无线网络搜索不到自家信号,却能搜到其他公司的信号”解决方法症状:自己的笔记本无线网络搜索不到自家信号,却能搜到其他公司的信号,并能连上网;其他台式机却能通过无......
  • 纯粹分治
    概述纯粹分治是分治思想最纯粹,最朴实,最本质?的应用。我不太会描述...一个典型是平面分治计数。还是看例题吧...例题PublicNOIPRound#3数圈圈题意:求一个二......
  • CDQ 分治
    例题P3157[CQOI2011]动态逆序对题意略。一开始想了半天,老半天的前后缀主席树做法(分别对前后缀开桶,模仿树状数组求逆序对,算贡献),最后还是发现似乎没办法统计算重的......
  • 分治优化
    概述分治优化常常在DP的转移有某种单向单调性时使用,通过类似整体二分的结构,确保每个决策点只在一条链上出现,从而加速转移。一般这种分治优化也有对应的二分栈形式,区别......
  • 树分治
    概述树分治通过树的唯一连通性质,递归地求解树上路径(主要是路径长度)相关的问题。树分治主要包括点分治和边分治,但到目前为止我都不知道边分治有什么用。点分治......
  • Ansible 学习笔记 - 定位主机和组的模式
    中英文对照表英文中文备注host主机group(主机)组pattern模式adhoc特别命令playbook剧本Ansible专有名词,一段复杂的编排inventory库存......