经典模板题 牛牛的等差数列

Q.给定初始序列 $a_1,\cdots,a_n$ 写数据结构，支持：

• 给指定区间 $[l, r]$ 加上一段首项为 $val$ ，公差为 $d$ 的长度为 $r - l + 1$ 的等差数列
• 求指定区间 $[l,r]$ 的和。

考虑懒标记维护当前位置 $x$ 的 由多个等差数列凑出的 $dx + b$ 的 $d,b$.

注意到如果我们维护了这样的 $d_0 x + b_0$，如果对这个位置再来一个 $(d_1,b_1)$ 的等差数列的某一项，则：
$$ d_0 x + b_0 + d_1x + b_1 = (d_0 + d_1) x + (b_0 + b_1) $$

最后注意，我们根据当前要求的给 $[l,r]$ 加上一个公差为 $d$ ，首项为 $val$ 的等差数列，将其凑成 $dx + b$ 的形式也就是：

$$ dl + b = val,b = val - dl $$

因此输入到线段树的懒标记为 $(d, val - dl)$

下面给出牛客这道题的代码(牛客这道题要求和对于一个它给出的 $m$ 进行取模，由于它的数据都是 $1e9 \times 1e9$ 级别容易爆 longlong，所以考虑取模，取 $\rm lcm(3,\cdots,25)$)

code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

constexpr int N = 2e5 + 10;
int a[N];

template<class T>
constexpr T qpow(T a, long long b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
template<long long P>
struct MLLong {
    long long x;
    constexpr MLLong() : x{} {}
    constexpr MLLong(long long x) : x{norm(x % getMod())} {}
    static long long Mod;
    constexpr static long long getMod() {return P ? P : Mod;}
    constexpr static void setMod(long long Mod_) {Mod = Mod_;}
    constexpr long long norm(long long x) const {if (x < 0) x += getMod();if (x >= getMod()) x -= getMod();return x;}
    constexpr long long  val() const {return x;}
    explicit constexpr operator long long() const {return x;}
    constexpr MLLong inv() const {assert(x != 0);return qpow(*this, getMod() - 2);}
    constexpr MLLong operator-() const {MLLong res;res.x = norm(getMod() - x);return res;}
    constexpr MLLong &operator*=(MLLong rhs) & {x = __int128_t(1) * x * rhs.x % getMod();return *this;}
    constexpr MLLong &operator+=(MLLong rhs) & {x = norm(x + rhs.x);return *this;}
    constexpr MLLong &operator-=(MLLong rhs) & {x = norm(x - rhs.x);return *this;}
    constexpr MLLong &operator/=(MLLong rhs) & {return *this *= rhs.inv();}
    friend constexpr MLLong operator*(MLLong lhs, MLLong rhs) {MLLong res = lhs;res *= rhs;return res;}
    friend constexpr MLLong operator+(MLLong lhs, MLLong rhs) {MLLong res = lhs;res += rhs;return res;}
    friend constexpr MLLong operator-(MLLong lhs, MLLong rhs) {MLLong res = lhs;res -= rhs;return res;}
    friend constexpr MLLong operator/(MLLong lhs, MLLong rhs) {MLLong res = lhs;res /= rhs;return res;}
    friend constexpr std::istream &operator>>(std::istream &is, MLLong &a) {long long v;is >> v;a = MLLong(v);return is;}
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLLong &a) {return os << a.val();}
    friend constexpr bool operator==(MLLong lhs, MLLong rhs) {return lhs.val() == rhs.val();}
    friend constexpr bool operator!=(MLLong lhs, MLLong rhs) {return lhs.val() != rhs.val();}
    friend string to_string(MLLong x) {return to_string(x.val());}
};
using Z = MLLong<26771144400>;

struct Tag{
    // dx + b ; d : 公差，b : 偏移
    Z d = 0, b = 0;
};
struct Val{
    Z s = 0;
};
struct Info{
    int l,r;Val s;Tag z;
};
Val operator+(const Val &a,const Val &b){
    return {a.s + b.s};
}
Info apply(Info a,Tag b){
    if (b.d != 0 || b.b != 0) {
        a.s.s += b.d * (1ll * (a.l + a.r) * (a.r - a.l + 1) / 2) + b.b * (a.r - a.l + 1);
        a.z.b += b.b;
        a.z.d += b.d;
    }
    return a;
}
struct SegTree
{
    int n;
    vector<Info> tr;
    SegTree(int n):n(n){
        tr.resize(n * 4 + 1),build(1,1,n);
    }
    void build(int u,int l,int r){
        tr[u].l = l,tr[u].r = r;
        if(l != r){
            int mid = (l + r) / 2;
            build(u * 2,l,mid);
            build(u * 2 + 1,mid + 1,r);
            pushup(u);
        } else tr[u].s.s = a[l];
    }
    void modify(int u,int l,int r,Tag d){
        if(tr[u].l < l || tr[u].r > r){
            pushdown(u);
            int mid = (tr[u].l  + tr[u].r) / 2;
            if(l <= mid) modify(u * 2,l,r,d);
            if(r > mid) modify(u * 2 + 1,l,r,d);
            pushup(u);
        }
        else tr[u] = apply(tr[u],d);
    }
    Val ask(int u,int l,int r){
        if(tr[u].l >= l && tr[u].r <= r)
            return tr[u].s;
        pushdown(u);
        int mid = (tr[u].l + tr[u].r ) / 2;
        Val ans;
        if(l <= mid) ans = ask(u * 2,l,r);
        if(r > mid) ans = ans + ask(u * 2 + 1,l,r);
        return ans; 
    }
    void pushup(int u){
        tr[u].s = tr[u * 2].s + tr[u * 2 + 1].s;
    }
    void pushdown(int u){
        tr[u * 2] = apply(tr[u * 2],tr[u].z);
        tr[u * 2 + 1] = apply(tr[u * 2 + 1],tr[u].z);
        tr[u].z = Tag();
    }
};

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n;cin >> n;
    for (int i = 1;i <= n;i ++ ) 
        cin >> a[i];
    SegTree Tree(n);
    int q;cin >> q;

    while (q -- ) {
        int op;cin >> op;
        if (op == 1) {
            int64_t l, r, val, d;
            cin >> l >> r >> val >> d;
            val = val - d * l;
            Tree.modify(1, l, r, {d, val});
        } else {
            int l, r, m;cin >> l >> r >> m;
            cout << Tree.ask(1, l, r).s.val() % m << '\n';
        }
    }
}

Practice

• https://codeforces.com/problemset/problem/1924/B
• https://www.luogu.com.cn/problem/P1438