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
| #include<bits/stdc++.h>
using namespace std;
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=1e5+5;
int ls[maxn<<1],rs[maxn<<1],rev[maxn<<1],mx[maxn<<1],mi[maxn<<1],a[maxn],tot;
void pushup(int&u){
mx[u]=max(mx[ls[u]],mx[rs[u]]);
mi[u]=min(mi[ls[u]],mi[rs[u]]);
}
void pushdown(int&u){
if(rev[u]){
swap(mx[ls[u]],mi[ls[u]]);
mx[ls[u]]=1e5-mx[ls[u]];
mi[ls[u]]=1e5-mi[ls[u]];
rev[ls[u]]^=1;
swap(mx[rs[u]],mi[rs[u]]);
mx[rs[u]]=1e5-mx[rs[u]];
mi[rs[u]]=1e5-mi[rs[u]];
rev[rs[u]]^=1;
rev[u]=0;
}
}
void build(int&u,int l,int r){
u=++tot;
rev[u]=0;
if(l==r){mx[u]=mi[u]=a[l];return;}
build(ls[u],l,ml); build(rs[u],mr,r);
pushup(u);
}
void update1(int&u,int l,int r,int q,int d){
if(l==r){mx[u]=mi[u]=d;return;}
pushdown(u);
if(q<=ml)update1(ls[u],l,ml,q,d);
if(q>=mr)update1(rs[u],mr,r,q,d);
pushup(u);
}
void update2(int&u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
rev[u]^=1;
swap(mx[u],mi[u]); mx[u]=1e5-mx[u]; mi[u]=1e5-mi[u];
return;
}
pushdown(u);
if(ql<=ml) update2(ls[u],l,ml,ql,qr);
if(mr<=qr) update2(rs[u],mr,r,ql,qr);
pushup(u);
}
int A,B,C;
long long f(int x,int y){return 1ll*x*A+1ll*y*B+1ll*x*y*C;}
long long query(int&u,int l,int r,int ql,int qr){
if(mx[u]==mi[u]) return f(r,mx[u]);
pushdown(u);
if(qr<=ml) return query(ls[u],l,ml,ql,qr);
else if(ql>=mr) return query(rs[u],mr,r,ql,qr);
else {
long long f1=f(ml,mx[ls[u]]),f2=f(r,mx[rs[u]]);
long long res=0;
if(f1>f2){
res=query(ls[u],l,ml,ql,qr);
if(f2>res) res=max(res,query(rs[u],mr,r,ql,qr));
}
else{
res=query(rs[u],mr,r,ql,qr);
if(f1>res) res=max(res,query(ls[u],l,ml,ql,qr));
}
return res;
}
}
int x;
int read(){
x=(100000005ll*x+20150609)%998244353;
return x/100;
}
int main(){
int n,m;
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=n;i++) a[i]=read()%100001;
char s[10];
int rt; build(rt,1,n);
while(m--){
scanf("%s",s);
if(s[0]=='C'){
int p=read()%n+1;
int y=read()%100001;
update1(rt,1,n,p,y);
}
else if(s[0]=='R'){
int p=read()%n+1;
int q=read()%n+1;
if(p>q) swap(p,q);
update2(rt,1,n,p,q);
}
else{
scanf("%d%d%d",&A,&B,&C);
int p=read()%n+1;
int q=read()%n+1;
if(p>q) swap(p,q);
printf("%lld\n",query(rt,1,n,p,q));
}
}
}
|
