余明泽的博客
2025年7月24日至7月25日总结
余明泽 LV 7 @ 2025-7-24 16:50:36

暑假集训 Day10~11 总结

前置知识：

今天学习线段树，这是一个代码量很大的数据结构，先来画一张图。

线段树支持区间查询与区间修改，树状数组可以做的题，线段树一定能做，但线段树的常数很大，所以用线段树时，尽量用位运算，减少常数量。

下面是线段树的几种操作。

1.建树操作：

void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, 0};
	} else {
		t[u] = {l, r, 0};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}

2.修改操作：

void change(int u, int x, int c) {
	if (t[u].l == x && t[u].r == x) {
		t[u].dat = c;
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (x <= mid) {
			change(u << 1, x, c);
		} else {
			change(u << 1 | 1, x, c);
		}

		pushup(u);
	}
}

3.查询操作：

int ask(int u, int l, int r) {
	if (t[u].l >= l && t[u].r <= r) {
		return t[u].dat;
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (r <= mid) {
			return ask(u << 1, l, r);
		} else if (l > mid) {
			return ask(u << 1 | 1, l, r);
		} else {
			int v = ask(u << 1, l, r);
			v = max(v, ask(u << 1 | 1, l, r));
			return v;
		}
	}
}

延迟标记：

延迟标记又称懒标记。之前，我们要修改一个区间的值都是找到每一个区间内元素然后立即修改，但这样是不是太浪费时间了呢？如果我们根本就不查询其中的某些节点，那哪些节点不更新是不是也没关系？可以证明，是可以的。所以，我们可以把子节点要加的直线存到父节点上面，要查询到子节点的时候，在把之前记在父节点上的所有值一起加上，这样既不影响查询，又可以节省许多时间，一举两得。延迟标记需要一个新的函数，里面要修改的东西看情况会有所不同，下面给一个参考。

void pushdown(int u) {
	if (t[u].cnt) {
		t[u << 1].dat += t[u].cnt;
		t[u << 1 | 1].dat += t[u].cnt;
		t[u << 1].cnt += t[u].cnt;
		t[u << 1 | 1].cnt += t[u].cnt;
		t[u].cnt = 0;
	}
}

扫描线：

这是一个很难的算法，需要比较高的思维能力。下面，我画一张图清晰反应扫描线算法每一步的操作。

这就是扫描线，每遇到一个新的矩阵，就让扫描线的值加一，遇到一个矩阵结束，就减一。扫描线把整个图分成了很多部分。由于扫描线的题目各不相同，没有比较通用的模板，详细的分析见五、六题。

A.最大数

正解思路：

纯线段树模板，主函数用两个变量分别存储上一次的答案和插入了多少元素。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int m, p;
int last, n;
struct node {
	int l, r, dat;
} t[N * 4];
void pushup(int u) {
	t[u].dat = max(t[u << 1].dat, t[u << 1 | 1].dat);
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, 0};
	} else {
		t[u] = {l, r, 0};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}
void change(int u, int x, int c) {
	if (t[u].l == x && t[u].r == x) {
		t[u].dat = c;
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (x <= mid) {
			change(u << 1, x, c);
		} else {
			change(u << 1 | 1, x, c);
		}

		pushup(u);
	}
}
int ask(int u, int l, int r) {
	if (t[u].l >= l && t[u].r <= r) {
		return t[u].dat;
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (r <= mid) {
			return ask(u << 1, l, r);
		} else if (l > mid) {
			return ask(u << 1 | 1, l, r);
		} else {
			int v = ask(u << 1, l, r);
			v = max(v, ask(u << 1 | 1, l, r));
			return v;
		}
	}
}
signed main() {
	cin >> m >> p;
	build(1, 1, m);

	while (m--) {
		string s;
		int x;
		cin >> s >> x;

		if (s == "Q") {
			last = ask(1, n - x + 1, n);
			cout << last << endl;
		} else if (s == "A") {
			change(1, n + 1, (last + x) % p);
			n++;
		}
	}

	return 0;
}

B.你能回答这些问题吗？

~~我不能回答这些问题！~~

正解思路：

这道题目要存处理的信息有点多，分别有 $l$ 和 $r$ ，然后要存区间和 $sum$ 和自己的前缀与后缀 $lsum$ 和 $rsum$ ，以及最大值 $dat$ 。对于 $sum$ ，这是最好算的，直接等于左子节点于右子节点的 $sum$ 之和。对于 $lsum$ ，它可以不变，也可以变为当前的 $sum$ 加上右边的 $lsum$ ，这是对两者取一个较大值就可以了，对于 $rsum$ ，也是同样的原理。最后算 $dat$ ，它可以是左子节点的 $dat$ ，也可以是右子节点的 $dat$ ，还可以是左子节点的后缀加上右子节点的前缀，所以对三者取最大值即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5;
int a[N];
struct node {
	int l, r, dat;
	int sum, lmax, rmax;
} t[N * 4];
int n, m;
void pushup(node &root, node &l, node &r) {
	root.sum = l.sum + r.sum;
	root.lmax = max(l.lmax, l.sum + r.lmax);
	root.rmax = max(r.rmax, r.sum + l.rmax);
	root.dat = max(l.dat, max(r.dat, l.rmax + r.lmax));
}
void pushup(int u) {
	pushup(t[u], t[u << 1], t[u << 1 | 1]);
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, a[l], a[l], a[l], a[l]};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}
void change(int u, int x, int c) {
	if (t[u].l == x && t[u].r == x) {
		t[u] = {x, x, c, c, c, c};
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (x <= mid) {
			change(u << 1, x, c);
		} else {
			change(u << 1 | 1, x, c);
		}

		pushup(u);
	}
}
node ask(int u, int l, int r) {
	if (t[u].l >= l && t[u].r <= r) {
		return t[u];
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (r <= mid) {
			return ask(u << 1, l, r);
		} else if (l > mid) {
			return ask(u << 1 | 1, l, r);
		} else {
			auto x = ask(u << 1, l, r);
			auto y = ask(u << 1 | 1, l, r);
			node v;
			pushup(v, x, y);
			return v;
		}
	}
}
signed main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	build(1, 1, n);

	while (m--) {
		int op;
		cin >> op;

		if (op == 1) {
			int x, y;
			cin >> x >> y;

			if (x > y) {
				swap(x, y);
			}

			cout << ask(1, x, y).dat << endl;
		} else if (op == 2) {
			int x, y;
			cin >> x >> y;
			change(1, x, y);
		}
	}

	return 0;
}

C.区间最大公约数

正解思路：

这题运用了差分的思想，与更相减损术的思想。我们每一次遇到操作 Q，输出 $1$ 到 $l$ 的前缀和与 $l+1$ 到 $r$ 的 gcd。否则对区间 $l$ 到 $r$ 进行一次差分操作。我们要存的东西有四个。前两个永远不变，分别为 $l$ 和 $r$ 。后两个为区间和 $sum$ 与 gcd。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+20;
int n, m;
int a[N];
struct node {
	int l, r;
	int sum, d;
} t[N * 4];
int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}
void pushup(node &rt, node &l, node &r) {
	rt.sum = l.sum + r.sum;
	rt.d = abs(gcd(l.d, r.d));
}
void pushup(int u) {
	pushup(t[u], t[u << 1], t[u << 1 | 1]);
}
void build(int u, int l, int r) {
	if (l == r) {
		int b = a[l] - a[l - 1];
		t[u] = {l, r, b, b};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}
void change(int u, int x, int c) {
	if (t[u].l == x && t[u].r == x) {
		int b = t[u].sum + c;
		t[u] = {x, x, b, b};
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (x <= mid) {
			change(u << 1, x, c);
		} else {
			change(u << 1 | 1, x, c);
		}

		pushup(u);
	}
}
node ask(int u, int l, int r) {
	if (t[u].l >= l && t[u].r <= r) {
		return t[u];
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (r <= mid) {
			return ask(u << 1, l, r);
		} else if (l > mid) {
			return ask(u << 1 | 1, l, r);
		} else {
			auto x = ask(u << 1, l, r);
			auto y = ask(u << 1 | 1, l, r);
			node p;
			pushup(p, x, y);
			return p;
		}
	}
}
signed main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	build(1, 1, n);

	while (m--) {
		string op;
		int l, r, d;
		cin >> op;
		cin >> l >> r;

		if (op == "Q") {
			cout << gcd(ask(1, 1, l).sum, ask(1, l + 1, r).d) << endl;
		} else {
			cin >> d;
			change(1, l, d);

			if (r + 1 <= n) {
				change(1, r + 1, -d);
			}
		}
	}

	return 0;
}

D.一个简单的整数问题2

~~似曾相识的感觉~~

正解思路：

这道题需要用懒标记解决，但是也不难。我们用 add 记录懒标记的数值。需要用到的时候就直接求出区间大小后乘上 add 即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;
int n, m;
int w[N];
struct tree {
	int l, r;
	int sum, add;
} t[N * 4];
void pushup(int u) {
	t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
void pushdown(int u) {
	tree &rt = t[u];
	tree &l = t[u << 1];
	tree &r = t[u << 1 | 1];

	if (rt.add) {
		l.add += rt.add;
		l.sum += (l.r - l.l + 1) * rt.add;
		r.add += rt.add;
		r.sum += (r.r - r.l + 1) * rt.add;
		rt.add = 0;
	}
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, w[l], 0};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}
void change(int u, int l, int r, int d) {
	if (l <= t[u].l && r >= t[u].r) {
		t[u].sum += (t[u].r - t[u].l + 1) * d;
		t[u].add += d;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			change(u << 1, l, r, d);
		}

		if (r > mid) {
			change(u << 1 | 1, l, r, d);
		}

		pushup(u);
	}
}
int ask(int u, int l, int r) {
	if (l <= t[u].l && r >= t[u].r) {
		return t[u].sum;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;
		int sum = 0;

		if (l <= mid) {
			sum += ask(u << 1, l, r);
		}

		if (r > mid) {
			sum += ask(u << 1 | 1, l, r);
		}

		return sum;
	}
}
signed main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}

	build(1, 1, n);

	while (m--) {
		string op;
		cin >> op;

		if (op == "Q") {
			int l, r;
			cin >> l >> r;
			cout << ask(1, l, r) << endl;
		} else {
			int l, r, d;
			cin >> l >> r >> d;
			change(1, l, r, d);
		}
	}

	return 0;
}

E.亚特兰蒂斯

毒瘤扫描线，调了我一个上午！

正解思路：

首先，我们画一个图，反应矩阵之间的关系。

把重复的部分去掉，变成一个整体：

现在，我们按照每一个矩阵的边界画扫描线：

变为：

至此，扫描线画出来了。但我们要把扫描线运用到计算上去。我们先离散化，因为数据太大，是不能直接用的。我们设 $val(y)$ 表示 $y$ 被离散化之后映射到的整数值， $raw(i)$ 表示整数值 $i$ 对应的原始 $y$ 坐标值。在离散化后，若有 $M$ 个不同的 $y$ 坐标值，分别对应 $raw (1), raw(2),\dots,raw(M)$ ，则扫描线至多被分成 $M-1$ 段，其中第 $i$ 段为区间 $[raw(i), raw(i +1)]$ 。建立数组 $c$ ，用 $c[i]$ 记录扫描线上第 $i$ 段被覆盖的次数。起初 $c$ 数组中的元素全为 $0$ 。逐一扫描排序后的 $2N$ 个四元组，设当前四元组为 $(x,yyz,k)$ 。我们把数组中 $c[val(y)], c[val(y1) + 1],\dots, c[val(y2)-1]$ 这些值都加 $k$ ，相当于覆盖了 $[y1,y2]$ 这个区间。此时，如果下一个四元组的横坐标为 $x2$ ，则扫描线从 $x$ 扫到 $x2$ 的过程中，被覆盖的长度就固定为 $\sum_{c_i>0}(raw(i +1) - raw (i))$ ，即数组中至少被覆盖一次的“段”的总长度。于是，我们就让最终的答案 $ans$ 累加上 $(x2-x) \times \sum_{c_i>0}(raw(i +1) - raw (i))$ 。另外，我们可以用线段树来维护 $c$ 数组，把时间复杂度降低到 $O(N log N)$ 。由于 $(x,y1,y2,1)$ 和 $(x,y1,y2,-1)$ 是成对出现的，所以线段树的区间修改也是成对的，所以，这里没有必要用延迟标记。最后，线段树除了必须维护的 $l$ 和 $r$ 外，还要多维护两个值，分别为被覆盖的区间长度 $len$ ，和区间被覆盖的次数 $cnt$ ，最初，两者均为 $0$ 。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+20;
int n;
vector<double> ys;
struct node {
	double x, yl, yr;
	int k;
	bool operator< (const node &t)const {
		return x < t.x;
	}
} sg[N * 2];
struct tree {
	int l, r;
	int cnt;
	double len;
} t[N * 8];
int find(double x) {
	return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void pushup(int u) {
	if (t[u].cnt) {
		t[u].len = ys[t[u].r + 1] - ys[t[u].l];
	} else if (t[u].l != t[u].r) {
		t[u].len = t[u << 1].len + t[u << 1 | 1].len;
	} else {
		t[u].len = 0;
	}
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, 0, 0};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}
void change(int u, int l, int r, int k) {
	if (t[u].l >= l && t[u].r <= r) {
		t[u].cnt += k;
		pushup(u);
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			change(u << 1, l, r, k);
		}

		if (r > mid) {
			change(u << 1 | 1, l, r, k);
		}

		pushup(u);
	}
}
int main() {
	int T = 1;

	while (cin >> n && n) {
		ys.clear();

		for (int i = 1, j = 0; i <= n; i++) {
			double x, xx, y, yy;
			cin >> x >> y >> xx >> yy;
			sg[j++] = {x, y, yy, 1};
			sg[j++] = {xx, y, yy, -1};
			ys.push_back(y);
			ys.push_back(yy);
		}

		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());

		build(1, 0, ys.size() - 2);
		sort(sg, sg + n * 2);
		double ans = 0;

		for (int i = 0; i < n * 2; i++) {
			if (i > 0) {
				ans += t[1].len * (sg[i].x - sg[i - 1].x);
			}

			change(1, find(sg[i].yl), find(sg[i].yr) - 1, sg[i].k);
		}

		cout << "Test case #" << T++ << endl;
		cout << "Total explored area: " << fixed << setprecision(2) << ans << endl;
		cout << endl;
	}

	return 0;
}

F.窗内的星星

又是一道毒瘤的扫描线，~~调了我一下午~~。

正解思路：

我们先画出一个图，以此来理解题意：

由于题目说，矩形边界上的星星不算，为了解决这种问题，我们便可以把顶点改一下，坐标从 $(x,y)$ 变为 $(x - 0.5, y -0.5)$ 。于是，上图的区间左下角就可以为 $(x,y)$ ，而右上角的坐标就可以为 $(x+w-1,y+h-1)$ 。此时，问题转化为：平面上有若干个区域，每个区域都带有一个权值，求在哪个坐标上重叠的区域权值和最大。其中，每一个区域都是由一颗星星产生的，权值等于星星的亮度。

现在，我们就可以使用扫描线算法，把每一个区域的的左右边界保存为两个四元组： $(x,y,y+h-1,l)$ 和 $(x+w-1,y,y+h-1,-l)$ 。保存好后，我们按照 $x$ 坐标从小到大排序。把 $y$ 和 $y+h-1$ 离散化。到这个时候，我们就可以用一个线段树维护了。用 $dat$ 存储区间最大值。逐一扫描每一个四元组 $(x,y1,y2,c)$ 。在线段树中进行区间修改（注意要用延迟标记），把 $[y1,y2]$ 加上 $c$ ，然后用根节点的 $dat$ 来更新答案即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;
int n, w, h;
vector<int> xs;
struct node {
	int l, r, h, sum;
	bool operator <(const node&x) const {
		return (h != x.h) ? h<x.h: sum>x.sum;
	}
} sg[N * 2];
struct tree {
	int l, r;
	int dat, cnt;
} t[N * 8];
int find(int x) {
	return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}
void pushdown(int u) {
	if (t[u].cnt) {
		t[u << 1].dat += t[u].cnt;
		t[u << 1 | 1].dat += t[u].cnt;
		t[u << 1].cnt += t[u].cnt;
		t[u << 1 | 1].cnt += t[u].cnt;
		t[u].cnt = 0;
	}
}
void pushup(int u) {
	t[u].dat = max(t[u << 1].dat, t[u << 1 | 1].dat);
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, 0, 0};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}
void change(int u, int l, int r, int k) {
	if (t[u].l >= l && t[u].r <= r) {
		t[u].dat += k;
		t[u].cnt += k;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			change(u << 1, l, r, k);
		}

		if (r > mid) {
			change(u << 1 | 1, l, r, k);
		}

		pushup(u);
	}
}
signed main() {


	while (cin >> n >> w >> h) {
		xs.clear();

		for (int i = 1, j = 0; i <= n; i++) {
			int x, y, l;
			cin >> x >> y >> l;
			sg[j++] = {y, y + h - 1, x, l};
			sg[j++] = {y, y + h - 1, x + w - 1, -l};
			xs.push_back(y);
			xs.push_back(y + h - 1);
		}

		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		sort(sg, sg + n * 2);
		build(1, 0, xs.size() - 2);
		int ans = 0;

		for (int i = 0; i < n << 1; i++) {
			int l = find(sg[i].l);
			int r = find(sg[i].r);

			if (i > 0) {
				ans = max(ans, t[1].dat);
			}

			change(1, l, r, sg[i].sum);
		}

		cout << ans << endl;
	}


	return 0;
}

G.维护序列

正解思路：

懒标记模板题，和 D 题十分类似。我们用 $sum$ 保存区间和， $mul$ 保存区间乘积。 $add$ 存储懒标。在 psuhdown 操作时，更新 $sum$ 为 $sum\times mul$ 再加上区间大小乘 $add$ 。更新 $mul$ 为自己的 $mul$ 乘上父节点的 $mul$ 。更新 $add$ 为自己的 $add$ 乘父节点的 $mul$ 加上父节点的 $add$ 。最后父节点的 $add = 0$ ， $mul = 1$ 。注意：每一步都要对 $p$ 取模。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;
int n, p, m;
int w[N];
struct tree {
	int l, r;
	int sum, add, mul;
} t[N * 4];
void pushup(int u) {
	t[u].sum = (t[u << 1].sum + t[u << 1 | 1].sum) % p;
}
void pushdown(int u) {
	t[u << 1].sum = (t[u << 1].sum * t[u].mul + t[u].add * (t[u << 1].r - t[u << 1].l + 1)) % p;
	t[u << 1 | 1].sum = (t[u << 1 | 1].sum * t[u].mul + t[u].add * (t[u << 1 | 1].r - t[u << 1 | 1].l + 1)) % p;
	t[u << 1].mul = (t[u << 1].mul * t[u].mul) % p;
	t[u << 1 | 1].mul = (t[u << 1 | 1].mul * t[u].mul) % p;
	t[u << 1].add = (t[u << 1].add * t[u].mul + t[u].add) % p;
	t[u << 1 | 1].add = (t[u << 1 | 1].add * t[u].mul + t[u].add) % p;
	t[u].add = 0;
	t[u].mul = 1;
}
void build(int u, int l, int r) {
	t[u].l = l;
	t[u].r = r;
	t[u].mul = 1;

	if (l == r) {
		t[u].sum = w[l] % p;
	} else {
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}
void changem(int u, int l, int r, int k) {
	if (l <= t[u].l && r >= t[u].r) {
		t[u].add = (t[u].add * k) % p;
		t[u].sum = (t[u].sum * k) % p;
		t[u].mul = (t[u].mul * k) % p;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			changem(u << 1, l, r, k);
		}

		if (r > mid) {
			changem(u << 1 | 1, l, r, k);
		}

		pushup(u);
	}
}
void changea(int u, int l, int r, int k) {
	if (l <= t[u].l && r >= t[u].r) {
		t[u].add = (t[u].add + k) % p;
		t[u].sum = (t[u].sum + (t[u].r - t[u].l + 1) * k) % p;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			changea(u << 1, l, r, k);
		}

		if (r > mid) {
			changea(u << 1 | 1, l, r, k);
		}

		pushup(u);
	}
}
int ask(int u, int l, int r) {
	if (l <= t[u].l && r >= t[u].r) {
		return t[u].sum;
	} else {
		pushdown(u);
		int mid = t[u].l + t[u].r >> 1;
		int sum = 0;

		if (l <= mid) {
			sum = (sum + ask(u << 1, l, r)) % p;
		}

		if (r > mid) {
			sum = (sum + ask(u << 1 | 1, l, r)) % p;
		}

		return sum;
	}
}
signed main() {
	cin >> n >> p;

	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}

	cin >> m;
	build(1, 1, n);

	for (int i = 1; i <= m; i++) {
		int op;
		cin >> op;

		if (op == 1) {
			int t, g, c;
			cin >> t >> g >> c;
			changem(1, t, g, c);
		} else if (op == 2) {
			int t, g, c;
			cin >> t >> g >> c;
			changea(1, t, g, c);
		} else {
			int t, g;
			cin >> t >> g;
			cout << ask(1, t, g) << endl;
		}
	}

	return 0;
}

2025年7月24日至7月25日总结

暑假集训 Day10~11 总结

前置知识：

延迟标记：

扫描线：

A.最大数

正解思路：

AC 代码：

B.你能回答这些问题吗？

正解思路：

AC 代码：

C.区间最大公约数

正解思路：

AC 代码：

D.一个简单的整数问题2

正解思路：

AC 代码：

E.亚特兰蒂斯

正解思路：

AC 代码：

F.窗内的星星

正解思路：

AC 代码：

G.维护序列

正解思路：

AC 代码：

状态

开发

支持

关于

2025年7月24日至7月25日总结

暑假集训 Day10~11 总结

前置知识：

延迟标记：

扫描线：

A.最大数

正解思路：

AC 代码：

B.你能回答这些问题吗？

正解思路：

AC 代码：

C.区间最大公约数

正解思路：

AC 代码：

D.一个简单的整数问题2

正解思路：

AC 代码：

E.亚特兰蒂斯

正解思路：

AC 代码：

F.窗内的星星

正解思路：

AC 代码：

G.维护序列

正解思路：

AC 代码：

状态

开发

支持

关于

登录