我也不知道是什么算法……
听说有人用 unordered_map 没过？我来为它证明！
首先，我们规定标记的顺序：加法 > 乘法 > 单点赋值 > 整体赋值。
然后，打标记的同时，注意一下其他标记的影响。
在单点赋值的时候需要逆元，线性递推相信人均了解（
同时，为了卡常，注意 unordered_map 访问的时候先用 count 判一下（直接访问会造成创建 \(0\)）。
以及全开 int。
代码： 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
using namespace std;
const int Q = 1e5;
const int T = 100;
const int mod = 1e7 + 19;
int n,q,t;
int inv[mod + 5];
int add,mul = 1,reset,sum,ans;
int a[T + 5],b[T + 5];
tr1::unordered_map<int,int> v;
struct note
{
int op,x,val;
} chg[Q + 5];
int main()
{
inv[1] = 1;
for(register int i = 2;i < mod;++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
scanf("%d%d",&n,&q);
for(register int i = 1;i <= q;++i)
{
scanf("%d",&chg[i].op);
if(chg[i].op == 1)
scanf("%d%d",&chg[i].x,&chg[i].val),chg[i].val = (chg[i].val % mod + mod) % mod;
else if(chg[i].op == 5)
scanf("%d",&chg[i].x);
else if(chg[i].op ^ 6)
scanf("%d",&chg[i].val),chg[i].val = (chg[i].val % mod + mod) % mod;
}
scanf("%d",&t);
for(register int i = 1;i <= t;++i)
scanf("%d%d",a + i,b + i),a[i] %= q,b[i] %= q;
for(register int i = 1,num,op,x,val;i <= t;++i)
for(register int j = 1;j <= q;++j)
{
num = (a[i] + (long long)j * b[i] % q) % q + 1;
op = chg[num].op,x = chg[num].x,val = chg[num].val;
if(op == 1)
{
if(v.count(x))
sum = ((sum - (long long)v[x] * mul % mod - add) % mod + mod) % mod;
else
sum = ((sum - (long long)reset * mul % mod - add) % mod + mod) % mod;
v[x] = (long long)(val - add + mod) % mod * inv[mul] % mod;
sum = (sum + val) % mod;
}
else if(op == 2)
add = (add + val) % mod,sum = (sum + (long long)n * val) % mod;
else if(op == 3)
add = (long long)add * val % mod,mul = (long long)mul * val % mod,sum = (long long)sum * val % mod;
else if(op == 4)
add = 0,mul = 1,reset = val,sum = (long long)n * val % mod,v.clear();
else if(op == 5)
{
if(v.count(x))
ans = (ans + (long long)v[x] * mul % mod + add) % mod;
else
ans = (ans + (long long)reset * mul % mod + add) % mod;
}
else
ans = (ans + sum) % mod;
}
printf("%d\n",ans);
}