题解

【关于F题】如果有和过了暴力对拍但是没有AC的提交的话请牛客或洛谷私信我（本人洛谷uid 124721 用户名:Ynoi）

直接模拟，维护所有消息中连续水了多少条和每个人连续水了多少条即可。

B:

考虑贪心。对于某个位置，如果后面的操作完全相同，那么显然这个数越大，最终结果也越大。所以我们每次操作都尽可能让小 $Y$ 实力值最大化。注意到小 $Y$ 实力值可能会很大，考虑因为 $a_i \le 10^9$ ,当小 $Y$ 的实力值大于 $10^9$ 时，如果 $b_i > 1$ 时，选择乘 $b_i$ 肯定是更优的，就不用比较了。

C:

按照 $r$ 从小到大排序，然后尽可能往前放。因为所有 $x$ 都不同，所以这样对后面的区间影响最小。

D:

考虑换根dp。

先任意选一个点为根。

首先定义 $f_i$ 表示以 $i$ 为根的子树必须选节点 $i$ 的连通块个数。

$sf_i$ 表示 $i$ 的子树内所有节点 $f_i$ 之和。

那么 $f_i= \prod (f_s+1)$ (s是i的子节点)（每个子树可以选择包含 $s$ 的连通块或者为空）。

然后假设断的是 $x,y$ 的边， $x$ 是 $y$ 的父节点。那么 $y$ 所在树的答案就是 $sf_y$

算 $x$ 所在树定义 $g_y$ 表示假设以 $y$ 为根， $y$ 在原来的父亲 $x$ 所在子树包含 $x$ 的连通块个数之和。那么 $g_y = (g_x+1)\prod(f_s+1)$ （s是 $x$ 除了 $y$ 之外的子节点）。然后类似 $sf$ 维护 $sg$ ,那么 $sg_y$ 就是 $x$ 所在的子树的答案了。

注意在计算 $\prod(f_s+1)$ 请不要将所有 $f_s+1$ 乘起来之后再乘 $inv(f_y+1)$ ，因为 $f_y+1$ 可能是 $998244353$ 的倍数。

E:

由于数据是随机的，我们考虑对于询问 $l,r,p$ ,我们从 $inv(p-1),inv(p-2)，inv(p-3)....$ 往下枚举，判断对应的数是否在区间 $l,r$ 中，如果是就停止枚举，此数即为最值。

期望复杂度证明如下

序列内随机一个数一个长度为m的区间的概率为 $m/n$

所以期望枚举 $n/m$ 次

长度随机出长度为 $m$ 的区间的概率为 $\frac{2(n-m)}{n*(n-1)}$

所以单次询问枚举的期望次数就是 $\sum_{m=1}^n\frac{n}{m}*\frac{2(n-m)}{n*(n-1)} = \sum_{m=1}^n \frac{2(n-m)}{m(n-1)} \le \sum_{m=1}^{n}\frac{2}{m} = O(lnn)$

所以单次询问期望枚举 $O(logn)$ 次

F:

先说wlwzgkd的判断。

1、2 算 $c_i = 1$ , 3、4操作算 $c_i = -1$ 那么询问 $l,r$ 就是求是否存在一个 $x(l\le x \le r)$ 使得 $\sum_{i=l}^{x}c_i < 0$ 。然后我们设 $c$ 的前缀和为 $s$ ，那么求出s中 $[l,r]$ 的最小值减去 $s_{l-1}$ 与 $0$ 的大小关系即可。

之后的分析都是针对没有pop空deque的情况。

先假设是对于两个栈进行操作。（即假设3操作仅pop1操作进来的,4操作仅pop2操作进来的）假设这两个栈为 $S,T$ (S是操作1，3的，T是操作2，4的)。

那么,我们先搞出一个匹配序列（就求出一个1操作是被哪个3操作pop 24操作同理）。

然后当我们询问 $l,r$ 的时候，我们会发现有若干个操作是失配的。

先上结论，deque内部剩余的节点是所有失配的操作1、2，删去最前面的x个， x是失配的3,4操作的个数。

（下面是证明）

下文中的前面指的是在opt序列里编号小。

我们考虑对于每个失配的pop操作,比如说是一个3操作记作u。

那么它会pop掉T里尚存的最前面的那一个2操作。

那么会有如下两种情况：

1.T中pop了一个失配的2操作那么这个2操作必然在这个3操作的前面并且S里肯定没有比3更靠前的失配1操作了(不然这俩就匹配了）那么pop的就是最前面的失配操作了。

2.T中pop了一个没有失配的2操作那么有一个匹配这个2操作（记作x）的4操作（记作y）。那么T中也没有比y更靠前的失配2操作了（不然如果比x靠前那么被就这个操作被u pop了如果比x靠后那么就和 y匹配了）

然后这个y就只能去匹配x里面的了相当于一个失配的4操作那么多次这样来回匹配之后就会发现最后被pop掉的还是最前面的失配1，2操作。

知道这个结论之后随便搞个数据结构(比如树套树)维护一下就可以了