题目
题目描述
数学考试，一道圆锥曲线的题难住了你，你开始疯狂地笔算。但是，这题实在太难，于是你决定每种思路多尝试尝试。
你的思维过程可以转化为如下过程：
-
有一个随机数产生器，有个内部变量 $x$ 初始时为 $x0$，每次产生随机数时它会将 $x$ 变为 $(100000005x+20150609)\bmod 998244353$，然后返回 $⌊\frac{x}{100}⌋$。（$a\bmod b$ 表示 $a$ 除以 $b$ 的余数，该运算的优先级高于加减法。$⌊α⌋$ 表示 $α$ 向下取整后的结果。）
-
初始时有$n$个点，分别编号为$1,…,n$，按编号从小到大顺序生成第$i$个点的坐标：
- 把横坐标赋为 $i$。
- 产生一个随机数 $\hat y$，把纵坐标赋为 $\hat y\bmod 100001$。
-
有$m$个操作，表示你的思路过程。操作共有三种：
- C：按顺序产生随机数 $\hat p,\hat y$，令 $p=\hat p\bmod n+1,y=\hat y\bmod 100001$，然后把第 $p$ 个点的纵坐标修改为 $y$。
- R：按顺序产生随机数 $\hat p,\hat q$，令$p=min{\hat p\bmod n+1,\hat q\bmod n+1},q=max{\hat p\bmod n+1,\hat q\bmod n+1}$，把编号大于等于 $p$ 小于等于 $q$ 的点的纵坐标 $y$ 改为 $100000−y$。
- Q $a$ $b$ $c$：查询操作。按顺序产生随机数 $\hat p,\hat q$，令 $p=min{\hat p\bmod n+1,\hat q\bmod n+1},q=max{\hat p\bmod n+1,\hat q\bmod n+1}$，求最小的整数 $t$ 使得：对于所有编号大于等于 $p$ 小于等于 $q$ 的点 $(x,y)$ 都满足 $ax+by+cxy≤t$。（$a,b,c$ 均为非负整数）
输入格式
第一行三个整数 $n,m,x0$。保证 $n,m≥1$，$0≤x0<998244353$ 且 $x0≠340787122$。
接下来 $m$ 行，每行表示一个操作，格式如前所述。
输出格式
对于每个查询操作输出一个整数表示最小的 $t$。
样例一
input
3 3 2705443
C
R
Q 872784 195599 7
output
13035048532
explanation
最开始三个点的坐标分别是 $(1,91263),(2,33372),(3,10601)$。
第一个操作把第三个点的坐标改成了 $(3,94317)$。
第二个操作修改了区间 $[2,3]$，第二个点变成了 $(2,66628)$，第三个点变成了 $(3,5683)$。
最后一个操作询问区间 $[2,3]$，可以发现最小的 $t$ 是 $13035048532$。
样例二
见样例数据下载。
限制与约定
所有数据中，对于所有查询操作保证 $0≤a,b<10^6$，$0≤c<40$，保证查询操作的出现次数不超过 $10^5$。
| 测试点编号 | $n$的规模 | $m$的规模 | 特殊限制 |
|---|---|---|---|
| 1 | $n≤100$ | $m≤100$ | 无 |
| 2,3 | $n≤10^5$ | $m≤10^6$ | 所有查询操作中 $a=c=0$ |
| 4,5 | $n≤10^5$ | $m≤2×10^5$ | 所有查询操作中 $c=0$ |
| 6,7 | $n≤10^5$ | $m≤2×10^5$ | 无 |
| 8,9,10 | $n≤10^5$ | $m≤10^6$ | 无 |
时间限制：$2s$
空间限制：$256MB$
题解
数据随机！挺有意思的一道题
测试点$1$：$O(nm)$暴力
测试点$2,3$：直接线段树维护区间$y$最小值即可
测试点$4,5$：发现要维护区间$ax+by$最小值，可以上凸壳二分求解，因为数据随机，一个区间的凸包的点只有$\log n$个，直接线段树上暴力合并凸包即可，因为有个区间取反操作所以还要维护下凸壳
测试点$6,7$，发现如果$a\le b$并且$y_a\le y_b$，点对$(a,y_a)$就没有贡献了，所以线段树维护一个单调上升序列和单调下降序列，$O(n\log^2 n)$
因为数据随机，上面那个算法只有$\log n$个节点能产生贡献，所以维护区间最大最小$y$值，然后类似$K-D$ $Tree$的查询，先计算右边，更新完再计算左边，叶子节点才可以更新答案
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=1e5+5;
struct p{
int mx,mi;
bool tags;
}s[MAX<<2];
int n,m,xs;
LL ans;
int a[MAX];
char S[5];
int GO() {return (xs=(100000005ll*xs+20150609)%998244353)/100;}
void GET_REV(int k) {s[k].tags^=1,swap(s[k].mx,s[k].mi),s[k].mx=1e5-s[k].mx,s[k].mi=1e5-s[k].mi;}
void down(int k) {if(s[k].tags) s[k].tags=0,GET_REV(tl),GET_REV(tr);}
void pus(int k) {s[k].mx=max(s[tl].mx,s[tr].mx),s[k].mi=min(s[tl].mi,s[tr].mi);}
void change(int l,int r,int k,int d,int x)
{
if(l==r) return void(s[k].mx=s[k].mi=d);
down(k);
if(x<=mid) change(l,mid,tl,d,x);
else change(mid+1,r,tr,d,x);
pus(k);
}
void changed(int l,int r,int k,int L,int R)
{
if(r<L||R<l) return;
if(l>=L&&r<=R) return void(GET_REV(k));
down(k),changed(l,mid,tl,L,R),changed(mid+1,r,tr,L,R),pus(k);
}
LL calc(int x,int y,int a,int b,int c) {return 1ll*x*a+1ll*y*b+1ll*c*x*y;}
void ask(int l,int r,int k,int a,int b,int c,LL &ans)
{
if(l==r) return void(ans=calc(l,s[k].mx,a,b,c));
down(k);
if(calc(r,s[tr].mx,a,b,c)>ans) ask(mid+1,r,tr,a,b,c,ans);
if(calc(mid,s[tl].mx,a,b,c)>ans) ask(l,mid,tl,a,b,c,ans);
}
void ask(int l,int r,int k,int L,int R,int a,int b,int c,LL &ans)
{
if(r<L||R<l) return;
if(l>=L&&r<=R)
{
if(calc(r,s[k].mx,a,b,c)>ans) ask(l,r,k,a,b,c,ans);
return;
}
down(k),ask(l,mid,tl,L,R,a,b,c,ans),ask(mid+1,r,tr,L,R,a,b,c,ans);
}
int ask(int l,int r,int k,int x)
{
if(l==r) return s[k].mx;
down(k);
if(x<=mid) return ask(l,mid,tl,x);
return ask(mid+1,r,tr,x);
}
void build(int l=1,int r=n,int k=1)
{
if(l==r) return void(s[k].mx=s[k].mi=a[l]);
build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),m=read(),xs=read();
for(int i=1;i<=n;++i)
a[i]=GO()%100001;
build();
for(int i=1,a,b,c,p,q;i<=m;++i)
{
scanf("%s",S);
if(S[0]=='C') change(1,n,1,GO()%100001,GO()%n+1);
else if(S[0]=='R') p=GO()%n+1,q=GO()%n+1,changed(1,n,1,min(p,q),max(p,q));
else if(S[0]=='Q') p=GO()%n+1,q=GO()%n+1,a=read(),b=read(),c=read(),ask(1,n,1,min(p,q),max(p,q),a,b,c,ans=0),printf("%lld\n",ans);
}
return 0;
}
