题目重述

维护一个长度为 $n$ 的数组（$n$ 可达 $10^9$），支持 $6$ 种操作：

1. 单点赋值
2. 全局加
3. 全局乘
4. 全局赋值
5. 单点查询
6. 全局求和

但输入方式特殊：先给 $q$ 个标准操作，再给 $t$ 组 $(a_i,b_i)$，实际执行 $t \times q$ 次操作。

---

核心挑战

1. $n$ 太大：不能直接存储整个数组
2. 操作序列长：$t \times q$ 最多 $10^7$ 次操作
3. 操作相互影响：全局操作会影响单点值的计算

---

关键思路：线性变换 + 懒标记

基本思想

用线性变换来表示全局操作：

• 维护 $mul$（乘法标记）和 $add$（加法标记）
• 任意值 $x$ 的实际值 = $x \times mul + add$

全局赋值处理

全局赋值可以看作：$mul=1, add=0$，然后所有元素 = $assign\_val$

但需要区分：一个位置是在全局赋值之前还是之后被单独修改过。

---

数据结构设计

懒标记系统

ll mul = 1, add = 0;          // 线性变换参数
ll assign_val = 0;            // 最近全局赋值的原始值
int assign_time = -1;         // 全局赋值的时间戳
int global_time = 0;          // 全局操作计数器

单点修改记录

由于 $n$ 很大，用哈希表记录被修改过的位置：

unordered_map<int, int> last_modify;  // 位置 -> 最后修改时间
unordered_map<int, ll> single_val;    // 位置 -> 原始值（在mul=1,add=0体系下）

---

操作处理

1. 单点赋值 1 i val

需要将目标值转换到"原始值"体系：

// 解方程：x * mul + add = val
// => x = (val - add) * inv(mul)
ll x = (val - add + MOD) % MOD;
x = (x * inv_mul) % MOD;  // inv_mul 是 mul 的逆元
update_single(i, x);

2. 全局加 2 val

add = (add + val) % MOD;

3. 全局乘 3 val

if (val == 0) {
    // 乘0相当于全局赋值为0
    apply_global_assign(0);
} else {
    mul = (mul * val) % MOD;
    add = (add * val) % MOD;
}

4. 全局赋值 4 val

void apply_global_assign(ll val) {
    assign_val = val;
    assign_time = global_time;
    mul = 1;
    add = 0;
    // 清空单点修改记录（或保留但用时间戳判断）
    last_modify.clear();
    single_val.clear();
}

---

查询处理

单点查询 5 i

ll query_point(int i) {
    if (last_modify.count(i) && last_modify[i] > assign_time) {
        // 在全局赋值后被单独修改过
        return (single_val[i] * mul + add) % MOD;
    } else {
        // 使用全局赋值的基础值
        return (assign_val * mul + add) % MOD;
    }
}

全局求和 6

维护总和 $sum$：

// 方法1：实时计算（较慢）
// 方法2：维护基准值体系（推荐）

ll base;           // 未被单独修改的元素的值（在mul=1,add=0体系下）
ll single_sum;     // 被单独修改的元素原始值之和
int cnt;           // 被单独修改的元素个数

ll query_sum() {
    // 总和 = base*(n-cnt) + single_sum*mul + add*n
    ll res = (base * (n - cnt)) % MOD;
    res = (res + single_sum * mul) % MOD;
    res = (res + add * n) % MOD;
    return res;
}

---

操作对总和的影响

全局赋值

base = val;
single_sum = 0;
cnt = 0;

全局加

base = (base + val) % MOD;

全局乘

base = (base * val) % MOD;
single_sum = (single_sum * val) % MOD;

单点赋值

void update_single(int i, ll x) {
    // 先撤销该位置之前的贡献
    if (last_modify.count(i) && last_modify[i] > assign_time) {
        single_sum = (single_sum - single_val[i] + MOD) % MOD;
        cnt--;
    }
    
    // 添加新贡献
    last_modify[i] = global_time;
    single_val[i] = x;
    single_sum = (single_sum + x) % MOD;
    cnt++;
}

---

时间复杂度

• 每个操作：$O(1)$ 均摊（哈希表操作）
• 总复杂度：$O(t \times q)$
• 空间复杂度：$O(\text{单点修改次数})$

---

关键优化点

1. 时间戳判断：用 global_time 和 assign_time 判断单点修改是否在全局赋值之后
2. 逆元预处理：由于 MOD 是质数，可以用费马小定理求逆元
3. 总和维护：避免每次查询都遍历所有元素

这种设计完美解决了 $n$ 过大无法存储的问题，同时保证了操作的高效性。