#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#define N 500000
using namespace std;
int read() {
    char c = 0;
    int sum = 0;

    while (c < '0' || c > '9')
        c = getchar();

    while ('0' <= c && c <= '9')
        sum = sum * 10 + c - '0', c = getchar();

    return sum;
}
struct rds {
    int op, l, r, a, b;
};
rds st[N + 1];
struct reads {
    int l, r, sl, sr, a, b;
    bool operator < (const reads &t)const {
        return r < t.r;
    }
};
set<reads>s;
int n, q, length, tong[N + 1];
long long c[N + 1], res;
int lowbit(int x) {
    return x & (-x);
}
void add(int x, long long d) {
    x = lower_bound(tong + 1, tong + length + 1, x) - tong;

    for (; x <= length; x += lowbit(x))
        c[x] += d;

    return;
}
long long query(int x) {
    long long res = 0;
    x = lower_bound(tong + 1, tong + length + 1, x) - tong;

    for (; x >= 1; x -= lowbit(x))
        res += c[x];

    return res;
}
struct node {
    long long a, b, res;
};
node zero;
node operator * (node x, node y) {
    return (node) {
        x.a + y.a, x.b + y.b, x.res + y.res + x.a *y.b
    };
}
node get_pow(node x, long long d) {
    return (node) {
        x.a *d, x.b *d, x.a *x.b*((d * (d - 1)) >> 1) + x.res *d
    };
}
node solve(long long x, long long a, long long b, long long c, node U, node R) {
    if (!x)
        return zero;

    if (b >= c)
        return get_pow(R, b / c) * solve(x, a, b % c, c, U, R);

    if (a >= c)
        return solve(x, a % c, b, c, U, get_pow(U, a / c) * R);

    long long ds = (a * x + b) / c;

    if (!ds)
        return get_pow(R, x);

    return get_pow(R, (c - b - 1) / a) * U * solve(ds - 1, c, (c - b - 1) % a, a, R, U) * get_pow(R,
            x - (c * ds - b - 1) / a);
}
long long calc(int l, int r, int a, int b) {
    int ds = (1ll * a * (l - 1) % b + b) % b;
    return ((node) {
        ds, 0, 0
    }
    *solve(r - l + 1, a, ds, b, (node) {
        -b, 0, 0
        }, (node) {
        a, 1, a
    })).res;
}
void adder(int l, int r, int a, int b) {
    int tl, tr, sl, sr, ta, tb;

    for (auto it = s.lower_bound((reads) {
    0, l, 0, 0
}); it != s.end() && (*it).l <= r; it = s.lower_bound((reads) {
    0, l, 0, 0
})) {
        tl = (*it).l, tr = (*it).r, sl = (*it).sl, sr = (*it).sr, ta = (*it).a, tb = (*it).b, s.erase(it), add(tr,
                                         -calc(sl, sr, ta, tb));

        if (tl <= l - 1)
            s.insert((reads) {
            tl, l - 1, sl, sl + (l - tl) - 1, ta, tb
        }), add(l - 1, calc(sl, sl + (l - tl) - 1, ta, tb));

        if (r + 1 <= tr)
            s.insert((reads) {
            r + 1, tr, sr - (tr - r) + 1, sr, ta, tb
        }), add(tr, calc(sr - (tr - r) + 1, sr, ta, tb));
    }
    s.insert((reads) {
        l, r, 1, r - l + 1, a, b
    }), add(r, calc(1, r - l + 1, a, b));
    return;
}
int main() {
    n = read(), q = read();

    for (int i = 1; i <= q; ++i) {
        st[i].op = read(), st[i].l = read(), st[i].r = read();

        if (st[i].op == 1)
            st[i].a = read(), st[i].b = read();
        else
            tong[++length] = st[i].l - 1, tong[++length] = st[i].r;
    }

    sort(tong + 1, tong + length + 1), length = unique(tong + 1, tong + length + 1) - tong - 1, s.insert((reads) {
        1, n, 1, n, 0, 1
    });

    for (int i = 1; i <= q; ++i) {
        if (st[i].op == 1)
            adder(st[i].l, st[i].r, st[i].a, st[i].b);
        else {
            auto it = s.lower_bound((reads) {
                0, st[i].r, 0, 0, 0, 0
            });

            if (st[i].l >= (*it).l)
                printf("%lld\n", calc((*it).sl + st[i].l - (*it).l, (*it).sr - ((*it).r - st[i].r), (*it).a, (*it).b));
            else {
                res = query(st[i].r) - query(st[i].l - 1);

                if ((*it).r != st[i].r)
                    res += calc((*it).sl, (*it).sl + st[i].r - (*it).l, (*it).a, (*it).b);

                auto it2 = s.lower_bound((reads) {
                    0, st[i].l, 0, 0, 0, 0
                });

                if ((*it2).l != st[i].l)
                    res -= calc((*it2).sl, (*it2).sl + st[i].l - (*it2).l - 1, (*it2).a, (*it2).b);

                printf("%lld\n", res);
            }
        }
    }

    return 0;
}

题解：ALADIN 数组操作问题

问题分析

本题要求处理一个长度为 ( N ) 的初始全零数组，支持两类操作：

1. 修改操作：对区间 ([L, R]) 赋值，其中 ( a[L+i] = (i+1) \times A \mod B )（( 0 \leq i \leq R-L )）。
2. 查询操作：计算区间 ([L, R]) 的元素和。

由于 ( N ) 最大可达 ( 10^9 )，无法直接存储数组，需通过区间管理和数学公式高效计算。

算法思路

1. 区间管理：使用 set 维护非重叠的区间，每个区间记录其对应的修改参数（( A, B )）和内部索引范围，避免重复存储。
2. 差分与前缀和：通过树状数组（Fenwick Tree）维护区间和的差分信息，快速计算任意区间的前缀和。
3. 数学公式优化：对于修改操作中的线性模运算序列，推导其求和公式，结合数论分块技巧，高效计算区间和，避免逐项计算。
4. 操作处理：
   • 修改操作：拆分已有区间，插入新的修改区间，并更新树状数组。
   • 查询操作：通过树状数组和区间参数，计算目标区间的和。

关键技术

1. 区间拆分：使用 set 存储区间，修改时拆分重叠区间，确保每个区间参数唯一。
2. 树状数组：用于维护区间和的差分，支持快速前缀和查询与更新。
3. 模运算求和公式：通过推导 ( k \times A \mod B ) 的求和公式，结合数论分块处理大规模区间求和。
4. 迭代函数求解：使用类似欧几里得算法的迭代方法，高效计算模线性序列的和。

代码实现解析

• 区间表示：struct reads 存储区间的左右端点、内部索引范围及修改参数 ( A, B )。
• 树状数组：add 和 query 函数用于维护和查询区间和的差分信息。
• 模和计算：calc 函数通过迭代求解模线性序列的和，利用数论分块优化计算效率。
• 修改与查询：adder 函数处理修改操作，拆分并更新区间；查询操作通过树状数组和区间参数计算结果。

算法标签

• 区间管理
• 树状数组（Fenwick Tree）
• 数论分块
• 模运算求和
• 迭代算法

复杂度分析

• 时间复杂度：每次操作涉及区间拆分和树状数组操作，复杂度为 ( O(Q \log Q) )，其中 ( Q ) 为操作数（( \leq 5 \times 10^4 )）。
• 空间复杂度：set 和树状数组的空间复杂度为 ( O(Q) )，适用于题目约束。

通过上述方法，高效处理了大规模数组的修改与查询操作，避免了直接存储数组的空间限制，实现了在规定时间内的高效计算。