首先将所有方案中 $\vert\sum B_i\vert$ 和最大转化成 $\max(\sum B_i,-\sum B_i)$。

于是问题转化成了，每个点可以选择以 $B_i,-B_i,-A_i$ 计入贡献，对于之间有边的一对点 $(u,v)$，要么 $u$ 以 $-A_u$ 或 $v$ 以 $-A_v$ 计入贡献（被删掉），要么同时以 $B_u,B_v$ 或同时以 $-B_u,-B_v$ 计入贡献。

这是一个类似最大权独立集的问题。考虑转化为最小割模型，将点 $u$ 拆为 $u_+,u_-$，源 $S$ 向 $u_+$ 连边，$u_-$ 向汇 $T$ 连边。

源 $S$ 向 $u_+$ 的边不被割表示 $u$ 以 $B_u$ 计入贡献，$u_-$ 向 $T$ 的边不被割表示 $u$ 以 $-B_u$ 计入贡献，两条边都被割表示 $u$ 以 $-A_u$ 计入贡献。为了保证两条边不会都不被割，需要连边 $(u_+,u_-,+\infty)$；同理，对于之间有边的一对点 $(u,v)$，需要连边 $(u_+,v_-,+\infty)$ 和 $(u_-,v_+,+\infty)$。

对于某个点 $u$，设 $S$ 到 $u_+$ 的边权为 $x$，$u_-$ 到 $T$ 的边权为 $y$，$u$ 的贡献为 $z$ 减去最小割中连向 $u_+$ 的和从 $u_-$ 出发的容量，联立三种情况得

$$\displaylines{\begin{cases} z-y=B_u\\ z-x=-B_u\\ z-x-y=-A_u \end{cases} }$$

解得

$$\displaylines{\begin{cases} x=A_u+B_u\\ y=A_u-B_u\\ z=A_u \end{cases} }$$

求 $\max$ 式的最小值，首先二分答案，问题转化为单点修改，区间查询是否所有颜色都出现过。

二分后这个问题可以归约到三维数点，带上二分是 $O((n+q)\log^3(n+q))$ 的复杂度。

不过显然这个问题是比三维数点弱的，因为查询的是所有颜色是否都出现过，而非求颜色个数。沿用区间数颜色的记每个位置 $i$ 的上一次为该颜色的位置 $p_i$ 的想法，不难发现区间 $[l,r]$ 中所有颜色均出现，当且仅当对于所有颜色有 $p_i\le l$，其中 $i$ 为该颜色在 $r$ 之后第一次出现的位置（为了让每个颜色都出现，需要在序列末尾把每个颜色都添加一遍），当且仅当对于所有 $i>r$ 都有 $p_i\le l$。

所以用线段树维护后缀 $p_i$ 最小值，在线段树上二分即可做到 $O(q\log n)$。

将答案序列看作一条平面上由 $(n,m)$ 到 $(0,0)$ 的路径，某次答案为 Yes 则往左走，否则往下走。于是每道题都与某条边一一对应；而每次答题人所面对的状态，即目前两种答案分别剩 $x,y$ 个，则与平面上某个点 $(x,y)$ 一一对应。

那么答题人的最优策略是显然的，当目前在直线 $y=x$ 以下时，猜答案为 Yes；当目前在直线 $y=x$ 以上时，猜答案为 No；当恰好落在直线上时，随便怎么猜，猜对的概率均为 $\frac12$。

我们来考察某种答案序列所对应的路径，假设 $n\ge m$，将整条路径在所有 $x=y$ 点处断开，形成多个段。

$n>m$ 时第一个段一定在 $y=x$ 下，这个段中每次询问都会得到回答 Yes，其中所有向左走的路径对应的问题是正确的，于是这段中答对问题的数量等于这部分路径的 $x$ 坐标跨度。

其余段中，除了段首第一个询问恒定有 $\frac12$ 的概率是正确的，其余所有边朝向直线 $y=x$ 的问题都是回答正确的。而这些段中起点终点均在 $y=x$ 上，所以 $x$ 坐标跨度等于 $y$ 坐标跨度，所以这些段中回答正确的问题数量期望都等于 $x$ 坐标跨度加 $\frac12$。

于是总答案等于 $n+\frac k2$，其中 $k$ 为回答的第二类段的期望数量，等于该路径与直线 $y=x$ 的交点个数减一。

那么对于每个点 $(x,x)$ 计算路径经过它的概率，计算相应贡献即可。

一次冒泡排序后区间内的最大值一定会到区间末尾，所以至少会出现一个分割点。那么每个元素对于答案的贡献就等于这个元素进入递归的层数。

不难发现一个元素不再进入下一层递归，当且仅当这个元素左右两侧均有分割点。所以这个元素进入递归的层数等于左右两侧分割点出现时间的较大值。于是我们转而考察每个分割点出现的时间。

而一个位置出现分割点当且仅当所有所有排序后在它左侧的数都在它左侧。考虑到这个目标达成以前，每一次递归，排序后在分界点左侧，此时却在分界点右侧的所有数，都会恰好想左移动一格。也即该分界点第一次出现的时间，等于排序后在分界点左侧的，最靠右的点到分界点的距离。

图中存在一条起点、中转点、终点之间的点不重路径，当且仅当在该图的广义圆方树上，中转点所在的某一个点双对应的方点在起点和终点对应的圆点之间的路径上。

那么给广义圆方树上所有方点赋权为该点代表的点双连通分量大小，圆点赋权为 $-1$，这样选定起点、终点后，中转点的方案数等于起点、终点在广义圆方树上对应的点之间的路径上所有点的点权和。路径上两个方点之间的原点的 $-1$ 可以减去两个点双中该圆点的重复贡献；路径的起点和终点的两个 $-1$ 可以减去中转点和起点、终点重合的情况。

首先以 $m$ 条 special restrictions 为边建一幅无向图，对于某一分钟的选取方案，我们定义关键边为两侧的点一个被选中，另一个未被选中的边。

然后考察任意一条 $1\to n$ 的路径，不难发现，点 $1$ 总需要被选取，点 $n$ 不可以被选取，因此任何一种选取朋友的方案的任意一刻，这条路径上至少有一条关键边。而在一种游戏方案中，每一条边为关键边的时间不超过它的边权。于是游戏时长不可能超过 $1\to n$ 的任意一条路径的长度，也就不可能超过 $1\to n$ 的最短路。

证明了游戏时长存在一个上界，现在需要构造一种方案使得游戏时长能够达到这个上界。记 $d_i$ 为 $1\to i$ 的最短路，点 $i$ 在 $[1,d_i)$ 这个时间段不被选取，在 $[d_i,d_n]$ 的时间段被选取，于是任意一条边权为 $w$ 的边 $(u,v)$ 满足 $|d_u-d_v|\le w$（最短路的性质），而前者即这条边作为关键边的时长，从而保证了题目的 special restrictions 成立。

然后就可以如此构造答案。

一种做法是，为等价类（颜色）寻找代表元，即待统计区间中最靠后者。

然后将询问按照右端点排序，保证统计区间为一个前缀。

如果区间中存在某种颜色，那么这种颜色的代表元一定在区间中，于是用树状数组维护当前前缀代表元数目，单点改、区间求和即可。

---

另一种做法：区间二维数点

对于数列中某个位置 $i$，记 $p_i$ 为 $i$ 之前最后一个颜色与 $i$ 相同的位置。

于是我们所求的，区间颜色数量，等价于求满足 $i\in[l,r],p_i<r$ 的位置数量。即代表元数量。

直接扫描线。