首页 > 其他分享 >分块 - 树分块

分块 - 树分块

时间：2024-05-03 21:55:06浏览次数：24  
标签：const Blk 分块 int sqrt MAXN 当前

分块 - 树分块

Luogu P3203 [HNOI2010] 弹飞绵羊

经典的 \(LCT\) 板子题，十分滴规范，但我们今天不讲 \(LCT\)

我们用 树分块 这个俎法哈，又短又快的咩（好像不是很快哈，同学们要认真学习哈

我们把一个点能到的点当成 它的老子，那 \(N + 1\) 就是 根 的咩

显然它的编号 越跳越大 撒，我们就按 编号来分这个块块儿哈，每 \(\sqrt N\) 分一块

然后 我们想要一块一块的跳 哈，就要处理下 每个点能跳到下一块的哪个点 哈

这个东西 倒起处理，\(O(\sqrt N)\) 就能俎一块的咩

然后我们还需要记录一哈 每个点跳几下能出块，算答案的时候每跳一块就加一哈

单点修改就 暴力重构 一块就行了哈，反正最后都是 \(O(N \sqrt N)\) 的复杂度的咩！

#include <bits/stdc++.h>

const int MAXN = 200005;
const int MAXB = 900;

using namespace std;

int N, M, B;
int K[MAXN], Blk[MAXN];
int BL[MAXB], BR[MAXB];

struct Block {
	int T[MAXB];
	short F[MAXB];
	
	inline void Init (const int x) {
		int Tmp;
		short Cnt;
		memset (F, 0, sizeof F);
		memset (T, 0, sizeof T);
		for (int i = BR[x]; i >= BL[x]; -- i) {
			Tmp = i, Cnt = 0;
			while (Tmp <= BR[x] && !F[Tmp - BL[x] + 1]) Tmp = Tmp + K[Tmp], ++ Cnt;
			if (Tmp > BR[x]) T[i - BL[x] + 1] = Tmp, F[i - BL[x] + 1] = Cnt;
			else T[i - BL[x] + 1] = T[Tmp - BL[x] + 1], F[i - BL[x] + 1] = Cnt + F[Tmp - BL[x] + 1];
		}
	}
} P[MAXB];

inline void Modify (const int x, const int y) {
	K[x] = y, P[Blk[x]].Init (Blk[x]);
}

inline int Query (int x) {
	int Ret = 0;
	while (x <= N) Ret += P[Blk[x]].F[x - BL[Blk[x]] + 1], x = P[Blk[x]].T[x - BL[Blk[x]] + 1];
	return Ret;
}

int Opt, x, y;

int main () {

	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> N, B = sqrt (N) * 2;
	
	for (int i = 1; i <= N; ++ i) cin >> K[i];
	
	for (int i = 1; i <= N; ++ i) {
		Blk[i] = i / B + 1;
		if (Blk[i] != Blk[i - 1]) BL[Blk[i]] = i, BR[Blk[i - 1]] = i - 1;
	} BR[N / B + 1] = N;
	
	for (int i = 1; i <= N / B + 1; ++ i) P[i].Init (i);
	
	cin >> M;
	
	for (int i = 1; i <= M; ++ i) {
		cin >> Opt >> x, ++ x;
		if (Opt == 1) cout << Query (x) << '\n';
		if (Opt == 2) cin >> y, Modify (x, y);
	}
	
	return 0;
}

Luogu P7446 [Ynoi2007] rfplca

和 上一道题 很像的，只是求的是 \(LCA\)，然后 单点修改 变成 区间减，强制在线

注意到每跳一次 所在结点编号必然变小，于是同样按照编号分块，每 \(\sqrt N\) 一块

我们发现这个 区间减 又 可以被摊掉

具体来说，当一块被减超过 \(\sqrt N\)（区间长）次的时候

那个块里的 任意点直接跳父亲必然出块，此时再对那个块区间减时 就不必要重构块乐

只需要打个 \(Tag\) 就行，单块处理复杂度 \(O(\sqrt N) \to O(1)\)

也就是每块最多 重构 \(\sqrt N\) 次，一共 \(\sqrt N\) 块，故重构部分复杂度 \(O(N \sqrt N)\)

查询的话和 倍增找 \(LCA\) 有点像，但需要 注意一些细节

以下我们称 跳出块的操作称为 跳块，跳父亲的操作称为 跳步

具体来说，我们一直执行以下三个步骤，直到跳到同一个点

  1. 跳块的结果 不在同一块的时候，跳块后 块编号更大的 跳块
  2. 跳块的结果 在同一块的时候 但不是同一结点时，跳块后 结点编号更大的 跳块
  3. 跳块的结果 在同一块的时候 且是是同一结点时，当前编号更大的 跳步

我们注意到我们 不能 直接判断 当前在不在同一块内 来决定 跳块还是跳步

因为可能 当前在同一块，而 跳块后的结果不在同一块

这意味着 \(LCA\) 并不在这一块，但如果此时因为 当前在同一块内 就选择 跳步

那么最后就可能被卡到 \(O(N)\) 一次查询，假掉

#include <bits/stdc++.h>

const int MAXN = 400005;
const int MAXB = 700;

using namespace std;

int N, M, B, LA = 0;
int Blk[MAXN];
int T[MAXN], F[MAXN];
int BL[MAXB], BR[MAXB], C[MAXB], Mns[MAXB];

#define Bx Blk[x]
#define By Blk[y]

inline void Update (const int x) {
	if (C[Bx] <= B) T[x] = Blk[F[x]] != Bx ? F[x] : T[F[x]];
}

inline int FOB (const int x) {
	return C[Bx] > B ? max (1, F[x] - Mns[Bx]) : T[x];
}

inline int FIB (const int x) {
	return C[Bx] > B ? max (1, F[x] - Mns[Bx]) : F[x];
}

inline void ModBlk (const int x, const int v) {
	if (C[x] > B) return Mns[x] = min (Mns[x] + v, N), void ();
	for (int i = BL[x]; i <= BR[x]; ++ i) F[i] = max (F[i] - v, 1), Update (i), void ();
}

int Opt, L, R, x;

inline void Modify (const int x, const int y, const int v) {
	if (Bx == By) {
		for (int i = x; i <= y; ++ i) F[i] = max (F[i] - v, 1);
		for (int i = x; i <= BR[Bx]; ++ i) Update (i);
		return ;
	}
	for (int i = x; i <= BR[Bx]; ++ i) F[i] = max (F[i] - v, 1);
	for (int i = x; i <= BR[Bx]; ++ i) Update (i);
	for (int i = BL[By]; i <= y; ++ i) F[i] = max (F[i] - v, 1);
	for (int i = BL[By]; i <= BR[By]; ++ i) Update (i);
	for (int i = Bx + 1; i < By; ++ i) ModBlk (i, v), ++ C[i];
} 

inline int Query2 (int x, int y) {
	while (x != y) {
		if (x > y) swap (x, y);
		if (Blk[x] < Blk[y]) y = FOB (y);
		else if (x < y) y = FIB (y);
	}
	return x;
}

inline int Query (int x, int y) {
	if (x == y) return x;
	int fx, fy;
	while (x != y) {
		fx = FOB (x), fy = FOB (y);
		if (Blk[fx] != Blk[fy]) Blk[fx] < Blk[fy] ? y = fy : x = fx;
		else if (fx ^ fy) fx > fy ? x = fx : y = fy;
		else x < y ? y = FIB(y) : x = FIB (x);
	}
	return x;
}

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M, B = sqrt (N);

	F[1] = T[1] = 1;
	
	for (int i = 1; i <= N; ++ i) {
		Blk[i] = i / B + 1;
		if (Blk[i] != Blk[i - 1]) BL[Blk[i]] = i, BR[Blk[i - 1]] = i - 1;
	} BR[N / B + 1] = N, BL[N / B + 2] = N + 1;

	for (int i = 2; i <= N; ++ i) cin >> F[i], Update (i);

	for (int i = 1; i <= M; ++ i) {
		cin >> Opt >> L >> R;
		L ^= LA, R ^= LA;
		if (Opt == 1) cin >> x, x ^= LA, Modify (L, R, x);
		if (Opt == 2) cout << (LA = Query (L, R)) << '\n';
	}
	
	return 0;
}

Luogu P6779 [Ynoi2009] rla1rmdq

感觉比上一个题要强一点

给定一棵树，给定任意节点序列，区间跳父亲，区间查询最小深度

感觉不好标记维护，大抵还是能想到 分块

我们先对给定的 序列分块，对每块考虑如何处理 跳父亲 和 询问 的操作

注意到我们只要 最小深度，这意味着 一个点被到达过，另一个点再跳到它时是 无意义的

若前面有一个点 \(u\) 到过 \(u'\)，那么当这个点 \(v\) 到 \(u'\) 时，\(u\) 的深度严格不大于 \(v\)，\(v\) 无贡献

当深度等于时意味着 \(u, v\) 共点，之后也会 一起跳，那也不需要两个分别考虑

也就是 对于每一块的操作，每个点至多被访问一次，\(O(N)\) 时间

而一共 \(O(\sqrt N)\) 块，故复杂度 \(O(N \sqrt N)\) 正确

实际实现上有一些细节，但还是简单的

注意到空间只有 \(64 ~ MB\)，故空间不能用 \(O(N \sqrt N)\) 的

于是我们可以离线操作，然后 依次对每一块操作，同时合并答案，这样空间就是 \(O(N)\) 的

对于一个询问，其 区间的最小深度

必然等于 区间两端散块部分的最小深度 和 **中间整块每块的最小深度 **的 最小值

我们只需要分别算出 每块对应时刻的最小深度，暴力跑散块最小深度即可

具体来说，我们每次处理一块，维护一个 当前有意义的点集

然后 遍历所有操作，判断 当前块 是 当前操作 的 整块 / 散块 / 无交集块

当前块 是 当前操作 的 整块 即 当前块被当前操作区间 完全包含

当前块 是 当前操作 的 散块 即 当前块被当前操作区间 部分包含

当前块 是 当前操作 的 无交集块 即 当前块与当前操作区间 无交集

如果当前操作是 跳父亲操作

  1. 若当前块是整块，遍历 有意义点集，跳父亲，同时将 新的无意义点踢出点集，更新当前答案

就是某个点跳父亲之后发现 他的父亲被跳到过，那么这个点就无意义了

  1. 若当前块是散块，遍历对应区间（当前操作的一个端点 和 当前块的一个端点 组成的区间）

    暴力跳 若干次 父亲，同时将 新的有意义点加入点击，更新当前答案

这里的 若干次 具体指什么？

我们记录其 整块跳跃的次数 \(Tag\)，而实际上我们每次只对 当前有意义点集的点 跳父亲

也就是 无意义的点 被忽略了若干次，但我们在这里 可能需要要这部分点的真实深度

于是就得 补跳，我们记录 每个点实际上（被当作有意义点）跳的次数 \(Val_i\)

那么对于当前点，\(Tag - Val_i\) 就是它要 补跳 的次数，再加上当前跳父亲的操作

于是这里的 若干次 其实就是 \(Tag - Val_i + 1\) 次


注意到为什么会有 新的有意义点 呢？

由于这个散块操作 并不是整个块一起跳，就可能出现 原来无意义的点跳了很多次

跳到了 没有被访问过的地方，那么这个点就 变得有意义了

我们仍然保证 树上每个点只被访问一次，故变有意义这个操作 并没有破坏复杂度

  1. 若当前块是无交集块，显然直接忽略即可

如果当前操作是 询问最小深度操作

  1. 若当前块是整块，将这个询问更新到当前的答案 和 当前块 当前最小深度 取 min 即可

  2. 若当前块是散块，我们暴力 补跳，使得所有点更新到 当前深度，然后更新答案即可

由于这里 不需要额外的 跳父亲操作，所以跳 \(Tag - Val_i\) 次即可，没有 \(+1\)

大体做完了，唯一需要考虑的就是 \(k\) 级祖先的求法

容易发现，这道题是 有性质的，对于每个点，我们将 一路往上跳 而不会返回

于是采用 树剖求 \(k\) 级祖先，从一个点到顶 一共需要切换至多 \(\log N\) 次重链

而由于这个性质，我们就把这个 \(\log\) 给 摊掉了

也就是询问的总时间复杂度是 \(O(N \sqrt N + N \log N)\) 而不是 \(O(N \sqrt N \log N)\)

但是如果使用 倍增求 \(k\) 级祖先，显然我们就 摊不掉 这个 \(\log\)，于是复杂度 \(O(N \sqrt N \log N)\)

其实卡卡常也能过，但是复杂度就会有点假，跑的慢一点


树剖实现

#include <bits/stdc++.h>

const int MAXN = 200005;
const int LOGN = 18;
const long long INF = 1e18;

using namespace std;

struct Edge {
	int to, nxt, w;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v, const int w) {
	E[++ tot] = {v, H[u], w}, H[u] = tot;
	E[++ tot] = {u, H[v], w}, H[v] = tot;
}

int N, M, B, rt;
int Top = 0, Tag = 0, Tot = 0;
int F[MAXN];
int SIZ[MAXN], DFN[MAXN], DEP[MAXN], SON[MAXN], TOP[MAXN], IDF[MAXN];
int LOG[MAXN], Val[MAXN], A[MAXN], Que[MAXN];
long long Dep[MAXN];

inline void DFS1 (const int x, const int f) {
	DEP[x] = DEP[f] + 1, F[x] = f, SIZ[x] = 1;
	for (int i = H[x]; i; i = E[i].nxt) {
		if (E[i].to != f) {
			Dep[E[i].to] = Dep[x] + E[i].w, DFS1 (E[i].to, x);
			if (SIZ[E[i].to] > SIZ[SON[x]]) SON[x] = E[i].to;
			SIZ[x] += SIZ[E[i].to];
		}
	}
}

inline void DFS2 (const int x, const int top) {
	TOP[x] = top, DFN[x] = ++ Tot, IDF[Tot] = x;
	if (!SON[x]) return ;
	DFS2 (SON[x], top);
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != F[x] && E[i].to != SON[x])
			DFS2 (E[i].to, E[i].to);
}

inline int KthF (int x, int k) {
	if (k >= DEP[x]) return rt;
	while (k >= DEP[x] - DEP[TOP[x]] + 1)
		k -= DEP[x] - DEP[TOP[x]] + 1, x = F[TOP[x]];
	return IDF[DFN[x] - k];
}

struct Ques {
	int Opt, L, R;
} Q[MAXN];

long long Ans[MAXN];
bool Vis[MAXN], InQ[MAXN];

inline void Solve (const int L, const int R) {
	Tag = Top = 0; 
	int l = L, r = R, Tmp;
	long long ans = INF;
	for (int i = 1; i <= N; ++ i) Vis[i] = InQ[i] = 0, Val[i] = Que[i] = 0;
	
	for (int i = L; i <= R; ++ i) if (!Vis[A[i]])
		Que[++ Top] = i, InQ[i] = 1, Vis[A[i]] = 1, ans = min (ans, Dep[A[i]]);

	for (int i = 1; i <= M; ++ i) {
		l = max (Q[i].L, L), r = min (Q[i].R, R); 
		if (l > r) continue ;
		if (Q[i].Opt == 1) {
			if (l == L && r == R) {
				++ Tag, Tmp = Top, Top = 0; 
				for (int j = 1; j <= Tmp; ++ j) {
					Val[Que[j]] ++ ;
					if (Vis[A[Que[j]] = F[A[Que[j]]]]) InQ[Que[j]] = 0;
					else Que[++ Top] = Que[j], Vis[A[Que[j]]] = 1;
					ans = min (ans, Dep[A[Que[j]]]);
				}
			} else {
				for (int j = l; j <= r; ++ j) {
					if (!Vis[A[j] = KthF (A[j], Tag - Val[j] + 1)]) {
						ans = min (ans, Dep[A[j]]), Vis[A[j]] = 1;
						if (!InQ[j]) Que[++ Top] = j, InQ[j] = 1;
					}
					Val[j] = Tag;
				}
			}
		} else {
			if (l == L && r == R) Ans[i] = min (ans, Ans[i]);
			else for (int j = l; j <= r; ++ j) Ans[i] = min (Ans[i], Dep[A[j] = KthF (A[j], Tag - Val[j])]), Val[j] = Tag;
		}
	}
}

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M >> rt, B = sqrt (N) * 2;
	
	int u, v, w;
	
	for (int i = 1; i < N; ++ i)
		cin >> u >> v >> w, Add_Edge (u, v, w);
	
	DFS1 (rt, rt), DFS2 (rt, rt); 
	
	for (int i = 1; i <= N; ++ i) cin >> A[i];
	
	for (int i = 1; i <= M; ++ i)
		cin >> Q[i].Opt >> Q[i].L >> Q[i].R, Ans[i] = INF;
	
	for (int i = 0; i <= N / B; ++ i) 
		Solve (i * B + 1, min ((i + 1) * B, N)); 
	
	for (int i = 1; i <= M; ++ i)
		if (Q[i].Opt == 2) cout << Ans[i] << '\n';
	
	return 0;
}

倍增实现

#include <bits/stdc++.h>

const int MAXN = 200005;
const int LOGN = 18;
const long long INF = 1e18;

using namespace std;

struct Edge {
	int to, nxt, w;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v, const int w) {
	E[++ tot] = {v, H[u], w}, H[u] = tot;
	E[++ tot] = {u, H[v], w}, H[v] = tot;
}

int N, M, rt;
int Top = 0, Tag = 0;
int F[MAXN][LOGN];
int LOG[MAXN], Val[MAXN], A[MAXN], Que[MAXN];
long long Dep[MAXN];

inline void DFS (const int x, const int f, const int w) {
	F[x][0] = f, Dep[x] = Dep[f] + w;
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) DFS (E[i].to, x, E[i].w);
}

inline void Init () {
	for (int i = 0; i <= 17; ++ i) F[rt][i] = rt;
	for (int j = 1; j <= 17; ++ j) 
		for (int i = 1; i <= N; ++ i)
			F[i][j] = F[F[i][j - 1]][j - 1];
	for (int i = 2; i <= N; ++ i) LOG[i] = LOG[i >> 1] + 1;
}

inline int KthF (int x, int k) {
	while (k) x = F[x][LOG[k]], k = k - (1 << LOG[k]);
	return x;
}

struct Ques {
	int Opt, L, R;
} Q[MAXN];

long long Ans[MAXN];
bool Vis[MAXN], InQ[MAXN];

int B;

inline void Solve (const int L, const int R) {
	Tag = Top = 0; // 初始化清零
	int l = L, r = R, Tmp;
	long long ans = INF;
	for (int i = 1; i <= N; ++ i) Vis[i] = InQ[i] = 0, Val[i] = Que[i] = 0;
	
	for (int i = L; i <= R; ++ i) if (!Vis[A[i]]) // 最开始有意义的点都加入（第一次去重）
		Que[++ Top] = i, InQ[i] = 1, Vis[A[i]] = 1, ans = min (ans, Dep[A[i]]);
	// 这里不考虑有没有 父子关系 的问题，因为如果存在父子均被加人有意义的集合，那么儿子跳一次之后就会被踢出
	
	for (int i = 1; i <= M; ++ i) {
		l = max (Q[i].L, L), r = min (Q[i].R, R); // 判断时 整块，散块，还是没有交
		
	//	cerr << "Now : " << i << " - Blk |" << L << "," << R << "|" << endl;
		
		if (l > r) continue ;
		if (Q[i].Opt == 1) {
			if (l == L && r == R) {
				++ Tag, Tmp = Top, Top = 0; // Tag 是整块跳的总次数 
				for (int j = 1; j <= Tmp; ++ j) {
					Val[Que[j]] ++ ; // 某个点跳了的次数
					if (Vis[A[Que[j]] = F[A[Que[j]]][0]]) InQ[Que[j]] = 0;
					else Que[++ Top] = Que[j], Vis[A[Que[j]]] = 1;
					ans = min (ans, Dep[A[Que[j]]]);
				}
			} else {
				for (int j = l; j <= r; ++ j) {
					if (!Vis[A[j] = KthF (A[j], Tag - Val[j] + 1)]) {
						ans = min (ans, Dep[A[j]]), Vis[A[j]] = 1;
						if (!InQ[j]) Que[++ Top] = j, InQ[j] = 1;
					}
					Val[j] = Tag;
				}
			}
		} else {
			if (l == L && r == R) Ans[i] = min (ans, Ans[i]);
			else for (int j = l; j <= r; ++ j) Ans[i] = min (Ans[i], Dep[A[j] = KthF (A[j], Tag - Val[j])]), Val[j] = Tag;
		}
	}
}

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M >> rt, B = sqrt (N) * 2;
	
	int u, v, w;
	
	for (int i = 1; i < N; ++ i)
		cin >> u >> v >> w, Add_Edge (u, v, w);
	
	DFS (rt, 0, 0), Init (); // 初始化 2 ^ k 级祖先
	
	for (int i = 1; i <= N; ++ i) cin >> A[i];
	
	for (int i = 1; i <= M; ++ i)
		cin >> Q[i].Opt >> Q[i].L >> Q[i].R, Ans[i] = INF;
	
	for (int i = 0; i <= N / B; ++ i) 
		Solve (i * B + 1, min ((i + 1) * B, N)); // 离线每个块单独处理
	
	for (int i = 1; i <= M; ++ i)
		if (Q[i].Opt == 2) cout << Ans[i] << '\n';
	
	return 0;
}

标签：const,Blk,分块,int,sqrt,MAXN,当前
From： https://www.cnblogs.com/FAKUMARER/p/18171692

相关文章

  • [分块] [Luogu AT_joisc2014_c] 历史研究
    题目描述IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。日记中记录了连续\(N\)天发生的事件，大约每天发生一件。事件有种类之分。第\(i\)天发生的......
  • 分块=-=优雅的暴力=-=中位数模版
    #include<bits/stdc++.h>//#defineintlonglong#definelllonglong#definefd(i,a,b)for(registerinti=a;i<=b;i=-~i)#definebd(i,a,b)for(registerinti=a;i>=b;i=~-i)usingnamespacestd;constintN=1e5+509,M=509,MOD=10007;intn,siz,id;......
  • CF EDU164-E-数论分块
    link：https://codeforces.com/contest/1954/problem/E有一排怪物，第\(i\)只有\(a_i\)的血，每次攻击可以选择在\(i\)处放一个技能，技能会一直向左/右以相同的\(k\)点伤害扩散，直至遇到边界或已经死亡的怪物。问最少需要放几次技能？需要对所有\(k\)回答答案。\(n,a_i\leq10^......
  • 欧拉函数 整除分块 扩展欧几里得
    欧拉函数\(\varphi(x)\)表示求出\(1\ley\lex,\gcd(x,y)=1\)的\(y\)的数量。对于一个质数\(p\),\(\varphi(p)=p-1\)\(\varphi(p^2)=p^2-\frac{p^2}{p}=p^2-p\)\(\dots\)\(\varphi(p^i)=p^i-p^{i-1}=(p-1)\cdotp^{i-1}\)......
  • 分块莫队——维护队列
    题目描述样例输入2312Q12R12Q12样例输出21题目分析首先它是一个离线莫队（在线超时QAQ）离线首先存下它所有的询问和修改，分别存，询问要存下是第几次，以便后续输出，还要存下时间是第几个命令，比较询问和修改的时间，相应的变换颜色，最后整体输出#include<bits/stdc++.h>......
  • 分块（板子）
    “优雅的暴力”——分块分块是一种暴力的优化，虽然效率比线段树、树状数组等数据结构低的多\((N+Q)\sqrt{N}\)，但是更加灵活。分块的思想是把整个区间分成几个部分，对于要处理的区间包括两个部分“整块”，和区间边缘的“零散块”，“零散块”直接暴力，“整块”进行整体操作即可。......
  • 题解 LGP5397【[Ynoi2018] 天降之物】/ 第四分块
    题解P5397【[Ynoi2018]天降之物】/第四分块题目描述一个长为\(n\)的序列\(a\)。你需要实现\(m\)个操作，操作有两种：把序列中所有值为\(x\)的数的值变成\(y\)。找出一个位置\(i\)满足\(a_i=x\)，找出一个位置\(j\)满足\(a_j=y\)，使得\(|i-j|\)最小，并输出\(|i-......
  • 蒲公英(分块)
    [Violet]蒲公英题目背景亲爱的哥哥：你在那个城市里面过得好吗？我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受......
  • 分块板子
    预处理voidinit(){clean();scanf("%lld",&n);for(i=1;i<=n;i++)scanf("%lld",&a[i]);sq=sqrt(n);for(i=1;i<=sq;i++){st[i]=n/sq*(i-1)+1;ed[i]=n/sq*i;}ed[sq]=n;for(i=1;i<......
  • 分块--解决区间问题
    什么时候用分块?当你发现正常数据结构无法解决的时候(比如维度特别多，很不方便或者炸空间)，或者复杂到要3个$log$以上才能解决时。(主要还是得看数据范围，分块的做法一般都是$O(\sqrt{n})$及以上的如何分块?定一个块长$B$,整个序列就会被分成$\floor{n/B}$块,对于末尾的不......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99