专栏文章

昨日寻找星星的借口

冷冷却心月明かり
P9776题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minec8ai
此快照首次捕获于
2025/12/02 01:01
3 个月前
此快照最后确认于
2025/12/02 01:01
3 个月前
查看原文
宝宝巴士题。
对建树过程有一些初步观察：是一颗线段树，结点编号是他的 dfs 序。
发现操作一二是独立的，先考虑操作二。显然 dfs 序区间 [l,r][l,r] 管辖的叶节点也是一个区间，找到 [l,r][l,r] 各自管辖的叶子区间的最左端和最右端即可，需要支持区间加法区间查询，bit 或者线段树做到 1log。
观察操作一，发现这个操作可以打懒标记。对每个结点 uu 维护其叶子的 f(i)f(i) 总和 sus_u，以及两个标记 au,bua_u,b_u，bub_u 表示操作一对结点 uu 管辖的叶子 ff 值的整体加法贡献，aua_u 表示操作一对结点 uu 的子树内点权值的加法贡献，bub_u 上的标记是平凡的加法标记，如果对当前结点子树的点权整体加 kk，我们可以建树时预处理出对点权整体加一时 sus_u 产生的贡献，那么此时的贡献就是他的 kk 倍。考虑下传标记，bb 下传是平凡的，aua_u 下传到子节点 vv 时，会对 vv 子树内的点权值整体加上 aua_u，和上文对 uu 子树整体加 kk 同样做，但除此之外还有 uu 结点点权 +au+a_u 对 vv 子树的贡献，所以还需要对 vv 管辖的叶子区间 ff 整体加 aua_u，打在 bvb_v 上，下传结束。然后就直接把操作摊到线段树上的区间打标记即可。注意如果一个点在操作区间内但是他管辖的区间整体不包含于操作区间，还要给他的叶子区间整体加 kk。
时间复杂度 1log。
CPP
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;

const int N = 1e6 + 10;
const ull MOD = 1e9 + 7;
int n, Q;

int ls[N << 1], rs[N << 1], ptot, pos[N], rt;

int rgt[22][N << 1], lg2[N << 1];
int querymx(int l, int r) {
	int t = lg2[r - l + 1]; return max(rgt[t][l], rgt[t][r - (1 << t) + 1]);
}

void build(int &p, int l, int r) {
	p = ++ ptot; if (l == r) { pos[l] = rgt[0][p] = p; return ; }
	int mid = (l + r) >> 1; build(ls[p], l, mid), build(rs[p], mid + 1, r); rgt[0][p] = rgt[0][rs[p]];
}

namespace DS {

ull tr[N << 1], add[N << 1], tag[N << 1]; int cnt[N << 1];
void build(int p, int l, int r) {
	if (l == r) { cnt[p] = 1; return ; }
	int mid = (l + r) >> 1; build(ls[p], l, mid), build(rs[p], mid + 1, r);
	cnt[p] = cnt[ls[p]] + cnt[rs[p]] + r - l + 1; return ;
}

void Add(int p, int l, int r, ull k) { tr[p] = (tr[p] + (r - l + 1) * k % MOD) % MOD, (add[p] += k) %= MOD; }
void f(int p, ull k) { tr[p] = (tr[p] + cnt[p] * k % MOD) % MOD; (tag[p] += k) %= MOD; (add[p] += k) %= MOD; }
void pushdown(int p, int l, int r) {
	int mid = (l + r) >> 1;
	if (tag[p]) f(ls[p], tag[p]), f(rs[p], tag[p]), tag[p] = 0;
	if (add[p]) Add(ls[p], l, mid, add[p]), Add(rs[p], mid + 1, r, add[p]), add[p] = 0;
	return ;
}

void update(int p, int l, int r, int x, int y, ull k) {
	if (x > rgt[0][p] || y < p) return ;
	if (x <= p && y >= rgt[0][p]) { f(p, k); return ; }
	if (p >= x && p <= y) Add(p, l, r, k); 
	int mid = (l + r) >> 1;
	pushdown(p, l, r);
	update(ls[p], l, mid, x, y, k), update(rs[p], mid + 1, r, x, y, k);
	tr[p] = (tr[ls[p]] + tr[rs[p]]) % MOD; return ;
}

ull query(int p, int l, int r, int x, int y) {
	if (x > r || y < l) return 0;
	if (x <= l && y >= r) return tr[p];
	int mid = (l + r) >> 1; pushdown(p, l, r);
	return (query(ls[p], l, mid, x, y) + query(rs[p], mid + 1, r, x, y)) % MOD;
}

}

#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
namespace Sgt {

ull tr[N << 2], tag[N << 2];
void add(int u, int l, int r, ull k) { tr[u] = (tr[u] + (r - l + 1) * k) % MOD, (tag[u] += k) %= MOD; }
void pushdown(int u, int l, int r) { 
	if (tag[u]) { int mid = (l + r) >> 1; add(ls(u), l, mid, tag[u]), add(rs(u), mid + 1, r, tag[u]); tag[u] = 0; } 
}
void update(int p, int l, int r, int x, int y, ull k) {
	if (x > r || y < l) return ;
	if (x <= l && y >= r) { add(p, l, r, k); return ; }
	int mid = (l + r) >> 1; pushdown(p, l, r);
	update(ls(p), l, mid, x, y, k), update(rs(p), mid + 1, r, x, y, k);
	tr[p] = (tr[ls(p)] + tr[rs(p)]) % MOD;
}
ull query(int p, int l, int r, int x, int y) {
	if (x > r || y < l) return 0;
	if (x <= l && y >= r) return tr[p];
	int mid = (l + r) >> 1; pushdown(p, l, r);
	return (query(ls(p), l, mid, x, y) + query(rs(p), mid + 1, r, x, y)) % MOD;
}

}
#undef ls
#undef rs

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> Q; build(rt, 1, n);
	for (int i = 2; i <= n * 2; i ++) lg2[i] = lg2[i >> 1] + 1;
	for (int k = 1; k <= 21; k ++) for (int i = 1; i + (1 << k) - 1 <= n * 2; i ++)
		rgt[k][i] = max(rgt[k - 1][i], rgt[k - 1][i + (1 << (k - 1))]);
	DS::build(1, 1, n);
	int o, x, y, k;
	while (Q --) {
		cin >> o >> x >> y;
		if (o == 1) { cin >> k; DS::update(1, 1, n, x, y, k); }
		else if (o == 2) {
			cin >> k;
			int l = lower_bound(pos + 1, pos + 1 + n, x) - pos, 
				r = upper_bound(pos + 1, pos + 1 + n, querymx(x, y)) - pos - 1;
			Sgt::update(1, 1, n, l, r, k);
		}
		else cout << (Sgt::query(1, 1, n, x, y) + DS::query(1, 1, n, x, y)) % MOD << "\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...