UOJ Logo Universal Online Judge

UOJ

#119. 【UR #8】决战圆锥曲线

统计

数学考试,一道圆锥曲线的题难住了你,你开始疯狂地笔算。但是,这题实在太难,于是你决定每种思路多尝试尝试。

你的思维过程可以转化为如下过程:

  • 有一个随机数产生器,有个内部变量 $x$ 初始时为 $x_0$,每次产生随机数时它会将 $x$ 变为 $(100000005x+20150609) \bmod 998244353$,然后返回 $\lfloor \frac{x}{100} \rfloor$。($a \bmod b$ 表示 $a$ 除以 $b$ 的余数,该运算的优先级高于加减法。$\lfloor \alpha \rfloor$ 表示 $\alpha$ 向下取整后的结果。)
  • 初始时有 $n$ 个点,分别编号为 $1, \dots, 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 \leq t$。($a, b, c$ 均为非负整数)

输入格式

第一行三个整数 $n, m, x_0$。保证 $n, m \geq 1$,$0 \leq x_0 < 998244353$ 且 $x_0 \neq 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 \leq a, b < 10^6$,$0 \leq c < 40$,保证查询操作的出现次数不超过 $10^5$

测试点编号 $n$的规模 $m$的规模 特殊限制
1$n \leq 100$$m \leq 100$
2$n \leq 10^5$$m \leq 10^6$所有查询操作中 $a = c = 0$
3
4$n \leq 10^5$$m \leq 2 \times 10^5$所有查询操作中 $c = 0$
5
6$n \leq 10^5$$m \leq 2 \times 10^5$
7
8$n \leq 10^5$$m \leq 10^6$
9
10

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载