LOJ#3110. 「SDOI2019」快速查询

发表于 | 阅读次数：

维护全局标记 $(a,b)$ 表示维护的数 $x$ 的实际值为 $ax+b$ ，这里需要始终保证 $a≠0$，初始时 $a=1,b=0$。

单点修改成 $val$ 就把维护的值改成 $\frac{val - b}{a}$。注意需要逆元需要实时维护。

加法直接加。

乘法若 $val≠0$ 就直接乘，注意加法标记也要乘。否则操作就是全部赋值为 $0$。

赋值为 $val$ 就把维护的数组全部清零，然后令 $a=1,b=val $.

查询直接查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define reg register
#define ll long long
using namespace std;
template<class tp>
tp F() {
	tp x = 0, ch = getchar(), f = 0;
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
template<class tp>
bool chkmax(tp &a, tp b) {
	return a < b ? a = b, 1 : 0;
}
template<class tp>
bool chkmin(tp &a, tp b) {
	return a > b ? a = b, 1 : 0;
}
inline void file_io(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
const int MAXN = 1e5 + 10;
const int mod = 1e7 + 19;
int n, m, op[MAXN], x[MAXN], y[MAXN], z[MAXN], o[MAXN << 7], len, f[MAXN], Mul = 1, Pls, inv = 1, sum, ans;
int (*rd)() = F<int>;
int fpw(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % mod;
        b >>= 1, a = 1ll * a * a % mod;
    }
    return res;
}
inline void modify(int x, int y) {
    sum = (sum + 1ll * (mod - f[x]) * Mul + mod - Pls) % mod, f[x] = 1ll * (y - Pls + mod) * inv % mod;
    o[++len] = x, sum = (sum+ + y) % mod;
}
inline void pls(int x) {
    sum = (sum + 1ll * n * x) % mod, Pls = (Pls + x) % mod;
}
inline void cover(int x) {
    while(len) f[o[len--]] = 0;
    Mul = inv = 1, Pls = x, sum = 1ll * n * x % mod;
}
inline void mmul(int x, int y) {
    if(x) sum = 1ll * sum * x % mod, Mul = 1ll * Mul * x % mod, Pls = 1ll * Pls * x % mod, inv = 1ll * inv * y % mod;
    else cover(0);
}
int query(int x = 0) {
    if(x) return (1ll * f[x] * Mul + Pls) % mod;
    else return sum;
}
int main() {
    n = rd() % mod, m = rd();
    for(reg int i = 0; i < m; ++i) {
        op[i] = rd();
        if(op[i] == 1 || op[i] == 5) x[i] = o[++len] = rd();
        if(op[i] <= 4) y[i] = (rd() % mod + mod) % mod, z[i] = fpw(y[i], mod - 2);
    }
    sort(o + 1, o + len + 1), len = unique(o + 1, o + len + 1) - o - 1;
    for(reg int i = 0; i < m; ++i) if(op[i] == 1 || op[i] == 5) x[i]  =lower_bound(o + 1, o + len + 1, x[i]) - o;
    for(reg int i = len = 0, t = rd(); i < t; ++i) {
        int a = rd() % m, b = rd() % m;
        for(reg int j = 0, k = (a + b) % m; j < m; ++j, k = (k + b) % m) {
            if(op[k] == 1) modify(x[k], y[k]);
            if(op[k] == 2) pls(y[k]);
            if(op[k] == 3) mmul(y[k], z[k]);
            if(op[k] == 4) cover(y[k]);
            if(op[k] == 5) ans = (ans + query(x[k])) % mod;
            if(op[k] == 6) ans = (ans + query()) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}