乱搞 $STL$ + 线性筛乘法逆元.
乱搞$STL$ + 线性筛乘法逆元.- 因为只有 $10^5$ 种操作,所以被单独赋值的位置最多也就 $10^5$ 个,这些可以开 $map$ 记录,其他位置可以整体维护.
- 维护 $mul,add,sum,v$ 四个标记, $mul,add$ 表示 $map$ 中存储的值为 $x$ ,实际上是 $mul\cdot x+add$ .
- $sum$ 表示当前所有元素的和. $v$ 表示不在 $map$ 中的数统一的值.
- 初始 $mul=1,add=sum=v=0.$ 几种操作仔细推一下就好了:
- 操作 $1$ :先用操作 $5$ 查询 $a_i$ ,算出新的 $sum$ ,再将 $map$ 中位置 $i$ 改为 $(val-add)\cdot mul^{-1}$ .
- 操作 $2$ : $sum+=val\cdot n,add+=val,v+=val.$
- 操作 $3$ : 若 $val\not = 0,sum\times =val,mul\times =val,add\times =val,v\times =val.$ 若 $val=0$ ,执行操作 $4$ ,将所有值都赋为 $0$,否则会使 $mul=0$ ,要用到 $mul^{-1}$ 时就炸了 .
- 操作 $4$ : 将 $map$ 清空, $sum=val\cdot n,mul=1,add=0,v=val$ .
- 操作 $5$ : 若 $a_i$ 在 $map$ 中有权值 $x$ ,那么就是 $mul\cdot x+add$ ,否则为 $v$ .
- 操作 $6$ : 当前的 $sum$ .
- $O(P)$ 预处理乘法逆元,并使用 $unordered$_$map$ ,时间复杂度即为 $O(tq)$ .
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int P=1e7+19;
int inv[P+10];
void init()
{
inv[1]=1;
for(int i=2;i<P;++i)
{
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
// assert(1LL*inv[i]*i%P==1);
}
}
inline int Add(int a,int b)
{
return (a+b)%P;
}
inline int Mul(int a,int b)
{
return 1LL * a * b % P;
}
const int MAXN=1e5+10;
unordered_map<int,int> mp;
int n,q,t;
int opt[MAXN],qx[MAXN],qy[MAXN];
int add=0,mul=1,sum=0,v=0;
int ans=0;
int query(int x)
{
if(mp.find(x)!=mp.end())
{
int key=mp[x];
return Add(add,Mul(key,mul));
}
else
return v;
}
void operate(int id)
{
int val,op=opt[id],i;
if(op==1)
{
i=qx[id];
val=qy[id];
int org=query(i);
sum=Add(sum,val-org);
mul=Add(mul,P);
int curv=Mul(inv[mul],Add(val,-add));
mp[i]=curv;
return;
}
if(op==2)
{
val=qx[id];
sum=Add(sum,Mul(val,n));
add=Add(add,val);
v=Add(v,val);
return;
}
bool trans=false;
if(op==3)
{
val=qx[id];
if(val)
{
sum=Mul(sum,val);
mul=Mul(mul,val);
add=Mul(add,val);
v=Mul(v,val);
return;
}
else
op=4,trans=true;
}
if(op==4)
{
val=trans?0:qx[id];
mp.clear();
sum=Mul(val,n);
mul=1,add=0;
v=val;
return;
}
if(op==5)
{
i=qx[id];
ans=Add(ans,query(i));
return;
}
if(op==6)
{
ans=Add(ans,sum);
return;
}
}
int main()
{
init();
n=read(),q=read();
for(int i=1;i<=q;++i)
{
opt[i]=read();
if(opt[i]!=6)
qx[i]=read();
if(opt[i]==1)
qy[i]=read();
}
t=read();
while(t--)
{
int a=read(),b=read();
for(int j=1;j<=q;++j)
operate((a+1LL*j*b)%q+1);
}
printf("%d\n",(ans%P+P)%P);
return 0;
}