洛谷P5358 [SDOI2019]快速查询题解

题目链接：洛谷P5358 [SDOI2019]快速查询

题意：

给定一个长度为 $n$ 的整数数列，里面的元素依次编号为 $a_1,~a_2,~a_3,~\dots,~a_n$。初始的时候，所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问，每一次修改或询问一定为以下六种情况之一：

1 i x ：将 $a_i$ 赋值为给定整数 $x$；

2 x ：将所有元素同时加上 $x$；

3 x ：将所有元素同时乘上 $x$；

4 x ：将所有元素同时赋值为 $x$；

5 i ：询问第 $i$ 个元素 $a_i$ 现在的值是多少；

6 ：询问现在所有元素的和。

输入格式：

为了避免读入太大，输入文件采取如下的形式。

第一行给定整数 $n$，表示给定数列长度为 $n$。

第二行给定整数 $q$，并且之后的 $q$ 行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。

我们称上述给定的修改或询问为标准操作。

之后给定一个整数 $t$，并且之后的 $t$ 行每行给定两个正整数 $a_i$ 和 $b_i$，这里的下标 $i$ 依次记为 $1$ 到 $t$ 。

你需要对初始值全为零的长度为 $n$ 的序列做总计 $t\times q$ 次操作。

其中第 $(i-1)q+j$ 次操作形如第 $((a_i + j b_i) \bmod{q}) + 1$ 个给定的标准操作（$1\le i\le t$ 且 $1\le j\le q$）。

输出格式：

输出一个整数，表示所有询问答案的累计和。

因为答案可能很大，只要求输出其结果关于 $p=10^7+19$ 取模后的值。

注意：若最终的累计和 $\mathtt{ans}$ 小于零，你应该输出 $\big((\mathtt{ans} \bmod{p})+p\big)\bmod{p}$。

数据范围：

$1 \le t \le 100,~1 \le n \le 10^9,~1 \le q \le 10^5$ 。

所有在输入中出现的数 $x$ 满足 $|x| \le 10^9$ ，所有的 $a_i,b_i$ 均满足 $0 \le a_i,b_i \le 10^9$ 。

全局维护的数据结构不多见。原因在于只需要几个值就可以维护了（

如果没有单点修改，那这道题就很水了，我们只需要维护个加法、乘法标记，就可以直接做了。

全局赋值在这题里只用加法&乘法标记就能维护，我们只要令 $\mathtt{mulv} \gets 1, \mathtt{addv} \gets x$ 就好了。

单点修改也不难。因为只有单点赋值，所以我们可以直接用一个 $\mathtt{unordered_map}$ 维护所有被修改的点。

注意全局赋值我们要把 $\mathtt{unordered_map}$ 清空，以及每次插入的是 $\frac{x - \mathtt{addv}}{\mathtt{mulv}}$ （需要线性预处理一下逆元）。

时间复杂度 $\mathcal{O}(qt)$ （~~怎么这么丑啊~~）

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const int mod = 1e7 + 19;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void Mod(int &x) { x = (x % mod + mod) % mod; }
#define N ((int)(1e5+15))
#define M ((int)(1e7+1150))

int n,Q,T,res,addv,mulv=1,sumv,a[N],b[N],inv[M];
unordered_map<int,int> mp;
struct query { int op,p,w; } q[N];
int F(int x) { return (1ll * mp[x] * mulv + addv) % mod; }
void work(query q)
{
    switch(q.op)
    {
        case 1 :
            Mod(sumv -= F(q.p));
            mp[q.p] = 1ll * (q.w - addv + mod) * inv[mulv] % mod;
            sumv = (sumv + q.w) % mod; break;
        case 2 : 
            addv = (addv + q.w) % mod;
            sumv = (sumv + 1ll * n * q.w) % mod; break;
        case 3 :
            mulv = 1ll * mulv * q.w % mod; addv = 1ll * addv * q.w % mod;
            sumv = 1ll * sumv * q.w % mod; break;
        case 4 :
            mulv = 1; addv = q.w;
            sumv = 1ll * n * q.w % mod; mp.clear(); break;
        case 5 : 
            res = (res + F(q.p)) % mod; break;
        case 6 : 
            res = (res + sumv) % mod; break;
        default: cout << "Error\n"; exit(0); break;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    inv[1] = 1;
    for(int i=2; i<mod; i++)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    cin >> n >> Q;
    for(int i=1; i<=Q; i++)
    {
        cin >> q[i].op;
        if(q[i].op == 1 || q[i].op == 5) cin >> q[i].p;
        if(q[i].op <= 4) { cin >> q[i].w; Mod(q[i].w); }
        if(q[i].op == 3 && !q[i].w) q[i].op = 4;
    }
    cin >> T;
    for(int i=1; i<=T; i++) cin >> a[i] >> b[i];
    for(int i=1; i<=T; i++)
        for(int j=1; j<=Q; j++) work(q[(a[i] + 1ll * j * b[i]) % Q + 1]);
    cout << res << '\n';
    return 0;
}