「SDOI2019」快速查询 题解

题目大意

给定一个长度为 $n$ 的整数数列，初始全为零。需要处理六种操作：

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

由于 $n$ 可达 $10^9$，无法直接存储整个序列。

核心思路

标记维护法

使用全局标记和哈希表来高效处理操作：

int multag = 1, addtag;           // 全局乘法、加法标记
unordered_map<int, int> c;        // 哈希表存储单点赋值
int sum;                          // 当前序列总和
const int MOD = 1e7 + 19;         // 模数

关键操作实现

1. 单点赋值

void cov(int pos, int val) {
    int old_val = query(pos);      // 获取原值
    sum = (sum - old_val + MOD) % MOD;  // 更新总和
    
    // 计算逆变换：val = multag × c[pos] + addtag
    int inv_mul = qpow(multag, MOD-2);  // 费马小定理求逆元
    c[pos] = 1ll * (val - addtag + MOD) * inv_mul % MOD;
    
    sum = (sum + query(pos)) % MOD;  // 加上新值
}

2. 全局赋值

void covt(int x) {
    multag = 1, addtag = x;        // 重置标记
    sum = 1ll * n * x % MOD;       // 更新总和
    c.clear();                     // 清空哈希表
}

3. 全局乘（含乘0特判）

void mul(int x) {
    if (!x) { 
        covt(0);                   // 乘0相当于全局赋0
        return; 
    }
    addtag = 1ll * addtag * x % MOD;
    multag = 1ll * multag * x % MOD;
    sum = 1ll * sum * x % MOD;
}

4. 查询操作

int query(int pos) {
    // 应用当前变换：值 = multag × 哈希表值 + addtag
    return (1ll * c[pos] * multag + addtag) % MOD;
}

算法优势

• 时间复杂度：每次操作平均 $O(1)$
• 空间复杂度：只存储被修改过的位置，极大节省空间
• 数学优化：通过逆元避免直接除法，保证模运算正确性

总结

这种方法通过巧妙的数学变换，将序列操作转化为标记维护，完美解决了序列过长无法直接存储的问题，是处理大规模数据操作的经典技巧。