首页 > 其他分享 >P3250 网络 题解

P3250 网络 题解

时间：2024-10-07 09:23:41浏览次数：1  
标签：int 题解 Upd 网络 fa dfn P3250 bit Op

Solution

单次二分：问“重要度 \(\ge x\) 的所有操作，且 \(t\) 时间点还存在的所有操作中，是否有不经过这个点的”

整体二分：保持操作、询问按时间有序，即预先按时间排序，下传时保持有序；

对于一次 Solve，对于所有重要度 \(\ge mid+1\) 的操作（加入、删除），考虑与询问按时间混合排序，然后依次回答。

这里有比树剖更好的处理方法：树上差分，一次加入路径 \((u,v)\) 就给 \(u,v\) 加一，\(lca,fa(lca)\) 减一；一次询问 \(u\) 就查 \(u\) 子树和是否等于操作数，树状数组可以实现。

用不用 \(O(1)\) LCA 都是 \(O(n\log^2 n)\) 的.

Code 1

\(\text{vector}\) 版整体二分，未卡常

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, tot, ans[N];
vector<int> G[N];
struct Item {
	int op, u, v, w, tim, id;
};

int tim, dfn[N], dep[N], sz[N], son[N], Top[N], Fa[N];
void DFS1(int u, int fa) {
	sz[u] = 1, Fa[u] = fa, dep[u] = dep[fa] + 1;
	for (int v : G[u])
		if (v != fa) {
			DFS1(v, u), sz[u] += sz[v];
			if (sz[v] > sz[son[u]]) son[u] = v;
		}
}
void DFS2(int u, int tp) {
	dfn[u] = ++tim, Top[u] = tp;
	if (son[u]) DFS2(son[u], tp);
	for (int v : G[u])
		if (v != Fa[u] && v != son[u])
			DFS2(v, v);
}
int LCA(int u, int v) {
	while (Top[u] != Top[v]) {
		if (dep[Top[u]] < dep[Top[v]]) swap(u, v);
		u = Fa[Top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

struct BIT {
	ll sum[N];
	BIT() {
		memset(sum, 0, sizeof(sum));
	}
	void Upd(int x, ll v) {
		for (; x <= n; x += x & -x) sum[x] += v;
	}
	ll Qry(int x) {
		ll res = 0;
		for (; x; x -= x & -x) res += sum[x];
		return res;
	}
	ll Qry(int x, int y) {
		return Qry(y) - Qry(x - 1);
	}
} bit;

void Solve(int l, int r, vector<Item> &Op) {
	int cntQ = 0;
	for (auto it : Op) cntQ += it.op == 2;
	if (!cntQ) return;
	if (l == r) {
		for (auto it : Op) {
			if (it.op == 2) ans[it.id] = (l == 1) ? -1 : (l - 1);
		}
		return;
	}
	int mid = (l + r) >> 1;
	vector<Item> OpL, OpR;
	int cnt = 0;
	for (auto it : Op) {
		if (it.op == 0) {
			if (it.w >= mid) {
				int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
				bit.Upd(dfn[u], 1), bit.Upd(dfn[v], 1), bit.Upd(dfn[lca], -1);
				if (fa) bit.Upd(dfn[fa], -1);
				++cnt;
			}
			if (it.w > mid) OpR.push_back(it);
			else OpL.push_back(it);
		}
		if (it.op == 1) {
			if (it.w >= mid) {
				int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
				bit.Upd(dfn[u], -1), bit.Upd(dfn[v], -1), bit.Upd(dfn[lca], 1);
				if (fa) bit.Upd(dfn[fa], 1);
				--cnt;
			}
			if (it.w > mid) OpR.push_back(it);
			else OpL.push_back(it);
		}
		if (it.op == 2) {
			int res = bit.Qry(dfn[it.u], dfn[it.u] + sz[it.u] - 1);
			if (res == cnt) {
				OpL.push_back(it);
			} else {
				OpR.push_back(it);
			}
		}
	}
	for (auto it : Op) {
		if (it.op == 0 && it.w >= mid) {
			int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
			bit.Upd(dfn[u], -1), bit.Upd(dfn[v], -1), bit.Upd(dfn[lca], 1);
			if (fa) bit.Upd(dfn[fa], 1);
		}
		if (it.op == 1 && it.w >= mid) {
			int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
			bit.Upd(dfn[u], 1), bit.Upd(dfn[v], 1), bit.Upd(dfn[lca], -1);
			if (fa) bit.Upd(dfn[fa], -1);
		}
	}
	Solve(l, mid, OpL), Solve(mid + 1, r, OpR);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n - 1) {
		int u, v;
		cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
	}
	int mx = 0;
	vector<Item> Op(m);
	rep(i, 0, m - 1) {
		int x;
		cin >> Op[i].op;
		if (Op[i].op == 0) 
			cin >> Op[i].u >> Op[i].v >> Op[i].w, mx = max(mx, Op[i].w);
		if (Op[i].op == 1) 
			cin >> x, --x, Op[i].u = Op[x].u, Op[i].v = Op[x].v, Op[i].w = Op[x].w;
		if (Op[i].op == 2) 
			cin >> Op[i].u, Op[i].id = ++tot;
	}
	DFS1(1, 0), DFS2(1, 1);
	Solve(1, mx + 1, Op);
	rep(i, 1, tot) 
		cout << ans[i] << '\n';
	return 0;
}

Code 2

普通整体二分

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, tot, ans[M];
vector<int> G[N];
struct Item {
	int op, u, v, w, tim, id;
} Op[M];
int id[M], _id[M], vis[M];

int tim, dfn[N], dep[N], sz[N], son[N], Top[N], Fa[N];
void DFS1(int u, int fa) {
	sz[u] = 1, Fa[u] = fa, dep[u] = dep[fa] + 1;
	for (int v : G[u])
		if (v != fa) {
			DFS1(v, u), sz[u] += sz[v];
			if (sz[v] > sz[son[u]]) son[u] = v;
		}
}
void DFS2(int u, int tp) {
	dfn[u] = ++tim, Top[u] = tp;
	if (son[u]) DFS2(son[u], tp);
	for (int v : G[u])
		if (v != Fa[u] && v != son[u])
			DFS2(v, v);
}
int LCA(int u, int v) {
	while (Top[u] != Top[v]) {
		if (dep[Top[u]] < dep[Top[v]]) swap(u, v);
		u = Fa[Top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

struct BIT {
	ll sum[N];
	BIT() {
		memset(sum, 0, sizeof(sum));
	}
	void Upd(int x, ll v) {
		for (; x <= n; x += x & -x) sum[x] += v;
	}
	ll Qry(int x) {
		ll res = 0;
		for (; x; x -= x & -x) res += sum[x];
		return res;
	}
	ll Qry(int x, int y) {
		return Qry(y) - Qry(x - 1);
	}
} bit;

void Solve(int l, int r, int ql, int qr) {
	int cntQ = 0;
	rep(i, ql, qr) cntQ += Op[id[i]].op == 2;
	if (!cntQ) return;
	if (l == r) {
		rep(i, ql, qr) {
			auto it = Op[id[i]];
			if (it.op == 2) ans[it.id] = (l == 1) ? -1 : (l - 1);
		}
		return;
	}
	int mid = (l + r) >> 1, cnt = 0, L = ql - 1, R;
	rep(i, ql, qr) {
		auto it = Op[id[i]];
		if (it.op == 0) {
			if (it.w >= mid) {
				int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
				bit.Upd(dfn[u], 1), bit.Upd(dfn[v], 1), bit.Upd(dfn[lca], -1);
				if (fa) bit.Upd(dfn[fa], -1);
				++cnt;
			}
			if (it.w > mid) vis[i] = 1;
			else _id[++L] = id[i], vis[i] = 0;
		}
		if (it.op == 1) {
			if (it.w >= mid) {
				int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
				bit.Upd(dfn[u], -1), bit.Upd(dfn[v], -1), bit.Upd(dfn[lca], 1);
				if (fa) bit.Upd(dfn[fa], 1);
				--cnt;
			}
			if (it.w > mid) vis[i] = 1;
			else _id[++L] = id[i], vis[i] = 0;
		}
		if (it.op == 2) {
			int res = bit.Qry(dfn[it.u], dfn[it.u] + sz[it.u] - 1);
			if (res == cnt) {
				_id[++L] = id[i], vis[i] = 0;
			} else {
				vis[i] = 1;
			}
		}
	}
	R = L;
	rep(i, ql, qr) 
		if (vis[i]) _id[++R] = id[i];
	rep(i, ql, qr) {
		auto it = Op[id[i]];
		if (it.op == 0 && it.w >= mid) {
			int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
			bit.Upd(dfn[u], -1), bit.Upd(dfn[v], -1), bit.Upd(dfn[lca], 1);
			if (fa) bit.Upd(dfn[fa], 1);
		}
		if (it.op == 1 && it.w >= mid) {
			int u = it.u, v = it.v, lca = LCA(u, v), fa = Fa[lca];
			bit.Upd(dfn[u], 1), bit.Upd(dfn[v], 1), bit.Upd(dfn[lca], -1);
			if (fa) bit.Upd(dfn[fa], -1);
		}
	}
	rep(i, ql, qr) id[i] = _id[i];
	Solve(l, mid, ql, L), Solve(mid + 1, r, L + 1, qr);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n - 1) {
		int u, v;
		cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
	}
	int mx = 0;
	rep(i, 1, m) {
		int x;
		cin >> Op[i].op;
		if (Op[i].op == 0) 
			cin >> Op[i].u >> Op[i].v >> Op[i].w, mx = max(mx, Op[i].w);
		if (Op[i].op == 1) 
			cin >> x, Op[i].u = Op[x].u, Op[i].v = Op[x].v, Op[i].w = Op[x].w;
		if (Op[i].op == 2) 
			cin >> Op[i].u, Op[i].id = ++tot;
		id[i] = i;
	}
	DFS1(1, 0), DFS2(1, 1), Solve(1, mx + 1, 1, m);
	rep(i, 1, tot) 
		cout << ans[i] << '\n';
	return 0;
}

标签：int,题解,Upd,网络,fa,dfn,P3250,bit,Op
From： https://www.cnblogs.com/laijinyi/p/18449769

相关文章

  • P3215 括号修复 题解
    Statement维护一个括号序列，有以下操作：区间覆盖区间翻转区间反转（左括号变右括号，右括号变左括号）区间问最少改多少位能使括号序列合法，保证有解Solution单纯没想到答案怎么算。。。首先一段括号序，如果消除中间的所有匹配，最终一定形如))))(((，这个信息是可合并的设这时左括......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树，每个节点上有一个集合，每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问，每次问\(u\)点的集合内，\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • 火星商店问题 题解
    Solution线段树套trie，秒了！\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案；我们重点考虑的是偶回文串结论：对于偶回文串\(u\)，从其最长的长度小于等于他的一半的回文后缀，或其父亲转移过来，一定是最优的证明：设\(u\)的一个回文子串为\(v\)（不是父亲），你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点，因为此......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse，多次给\(l,r\)，求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\)：莫队+线段树/树状数组/set，用SA做\(nm/\omega\)：bitset乱搞\(\log^2\)：SAM+LCT+BIT在parent树上，LCP等于LCA的......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • P4093 序列 题解
    Statement给出\(n\) 个数的序列\(\{a_i\}\)，接下来\(m\)秒中每一秒会有一个数发生变化，然后恢复。问最长的子序列长度，使得任意时刻这个子序列不下降。\(n\le10^5\)Solution设\(b_i\)为\(i\)最小能变成的数，\(c_i\)为\(i\)最大能变成的数\[f(i)=\max_{j<i\landc......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义：随机数据下：任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下：每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\)，一次询......
  • Codeforces Rund 977 div2 个人题解(A~E1)
    CodeforcesRund977div2个人题解(A,B,C1,C2,E1)Dashboard-CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#includ......
  • 【题解】C - STEP
    目录题目内容DescriptionInputOutput数据规模与约定做法一思路代码做法2思路代码题目内容原题：洛谷P6492Description给定一个长度为\(n\)的字符序列\(a\)，初始时序列中全部都是字符L。有\(q\)次修改，每次给定一个\(x\)，若\(a_x\)为L，则将\(a_x\)修改成R，否则将\(a_x\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99