昨日寻找星星的借口

冷却心 · 2025-11-03 13:33:37 · 题解

宝宝巴士题。

对建树过程有一些初步观察：是一颗线段树，结点编号是他的 dfs 序。

发现操作一二是独立的，先考虑操作二。显然 dfs 序区间 [l,r] 管辖的叶节点也是一个区间，找到 [l,r] 各自管辖的叶子区间的最左端和最右端即可，需要支持区间加法区间查询，bit 或者线段树做到 1log。

观察操作一，发现这个操作可以打懒标记。对每个结点 u 维护其叶子的 f(i) 总和 s_u，以及两个标记 a_u,b_u，b_u 表示操作一对结点 u 管辖的叶子 f 值的整体加法贡献，a_u 表示操作一对结点 u 的子树内点权值的加法贡献，b_u 上的标记是平凡的加法标记，如果对当前结点子树的点权整体加 k，我们可以建树时预处理出对点权整体加一时 s_u 产生的贡献，那么此时的贡献就是他的 k 倍。考虑下传标记，b 下传是平凡的，a_u 下传到子节点 v 时，会对 v 子树内的点权值整体加上 a_u，和上文对 u 子树整体加 k 同样做，但除此之外还有 u 结点点权 +a_u 对 v 子树的贡献，所以还需要对 v 管辖的叶子区间 f 整体加 a_u，打在 b_v 上，下传结束。然后就直接把操作摊到线段树上的区间打标记即可。注意如果一个点在操作区间内但是他管辖的区间整体不包含于操作区间，还要给他的叶子区间整体加 k。

时间复杂度 1log。

#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;
}