洛谷Luogu - P3373 线段树2(区间乘模板)

Link

关于先乘后加，还是先加后乘的一点个人理解，举个栗子，为了方便理解，我们举单点而不是区间为例，两者是等价的：
对于一个节点:

struct Node{
	int l,r;
	int sum;
	int add,mul;
}

里面存储的信息有add和mul，比如我们现在要计算出节点a的真实值并清空a的懒标记，有两种计算方式

• (a times mul +add)，向下传时：
  ((a times mul +add)times mul'+add')
  (=atimes multimes mul'+addtimes mul'+add')
• ((a +add) times mul)，向下传时：
  (((a +add) times mul+add')times mul')
  (=atimes mul times mul'+addtimes multimes mul'+add'times mul')

由于代码的执行方式是不能发生变化的，这一步是先乘后加，下一步也会是先乘后加，那么只有第一种方式是可以的，第二种则因为向下传后不能变成原来的先加再乘的形式，所以必须先乘后加

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;

int n, m, p;
int w[N];

struct Node {
	int l, r;
	int sum, add, mul;
} tr[ N << 2];

void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void eval(Node &t, int add, int mul) {
	t.sum = ((ll)t.sum * mul + (ll)(t.r - t.l + 1) * add) % p;
	t.mul = (ll)t.mul * mul % p;
	t.add = ((ll)t.add * mul + add) % p;
}

void pushdown(int u) {// 用本层节点的懒标记修改其下一层的节点
	eval(tr[u << 1], tr[u].add, tr[u].mul);
	eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
	tr[u].add = 0;
	tr[u].mul = 1;
}

void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = {l, r, w[r], 0, 1};
		return ;
	}
	tr[u] = {l, r, 0, 0, 1};
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int l, int r, int add, int mul) {
	if (tr[u].l >= l && tr[u].r <= r)
		eval(tr[u], add, mul);// 如果范围已经被包含在树的范围内，那么修改的就不是下一层节点，而是直接修改这层
	else {
		pushdown(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid)
			modify(u << 1, l, r, add, mul);// 下传懒标记到左节点
		if (r > mid)
			modify(u << 1 | 1, l, r, add, mul);// 下传懒标记到右节点
		pushup(u);
	}
}

ll query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r)
		return tr[u].sum;
	pushdown(u);
	int mid = (tr[u].r + tr[u].l) >> 1;
	ll ans = 0;
	if (l <= mid)
		ans += query(u << 1, l, r);
	if (r > mid)
		ans = (ans + query(u << 1 | 1, l, r)) % p;
	return ans;
}

int main(void) {
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	build(1, 1, n);
	int op, x, y, k;
	while (m--) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			scanf("%d", &k);
			modify(1, x, y, 0, k);
		} else if (op == 2) {
			scanf("%d", &k);
			modify(1, x, y, k, 1);
		} else
			printf("%lldn", query(1, x, y));
	}
	return 0;
}

/*
 * When ability does not derserve ambition, just keep moving
 */

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

292939 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

41897 0元 限免

基于 OpenVINO™ 的 AI 视觉应用基础课

55988 0元 限免