昨天 10:36 已编辑北京大学 C++ 发布于北京

关注

【题解】牛客挑战赛 85 / Sadness Fan Club Round 4

A. 「SFCOI-4」剑客花木兰

我们发现 $a, b$ 的数据范围均很小，这说明我们可以通过一些比较暴力的方式解决此题。

这道题的做法很多，其中一种是我们先处理出全用轻剑所需要的轻剑使用次数和体力。考虑不断用重剑代替轻剑是否会使答案更优，暴力执行这一操作，即每次先减去一次轻剑操作，然后不断加上重剑操作直到能斩杀敌人。显然加上的重剑操作不会超过 $b$ 次，这样我们就得到了一个时间复杂度 $O(nb)$ 的做法，足以解决本题。

B. 「SFCOI-4」序列与变换

一个数的经过一系列变换之后只有两种变化情况： $a_i \to 0/1 \to \cdots \to 1/0$ ，或者由于这个数太大根本无法变成 $1$ 或 $0$ 。

接下来我们可以证明这一点，当一个数变为 $1$ 或 $0$ 之后我们再对其进行操作 $k$ 后这个数至多变成 $k$ ，再进行操作 $k-1$ 之后这个数又会回归 $1$ 或 $0$ 。又由于进行的最后一次操作一定是操作 $1$ ，那么最后这个数一定是 $1$ 或 $0$ 。

综上，我们就可以得出这道题的解法：

先判断这个数能否一直缩小变为 $1$ 或 $0$ 。
如果能的话，由于最终结果的奇偶性与 $a_i + \dfrac{m(m + 1)}{2}$ 一致，我们只需要判断这个数是奇数还是偶数，就能知道最后它变为 $0$ 还是 $1$ 。

C. 「SFCOI-4」生活在树上

首先特判 $k = 0$ ，此时只有 $n = 1$ 的情况有解。

符号约定：

$\operatorname{highbit}(x)$ 表示正整数 $x$ 在二进制表示下最高位 $2^p$ 对应的 $p$ 。特别地，令 $\operatorname{highbit}(0) = -1$ 。

令 $s = \operatorname{and}_{i = 1}^n a_i$ ，首先将 $a_i$ 异或上 $s$ 以去除不影响 $a_u \operatorname{xor} a_v$ 的“公共部分”，然后将 $a$ 排序，随后分类讨论：

$\forall i, \operatorname{highbit}(a_i) < \operatorname{highbit}(k)$ ：任意构造 BST 均为合法解。
$\exists i, \operatorname{highbit}(a_i) > \operatorname{highbit}(k)$ ：无解。
$\text{otherwise}$ ：合法的必要条件是 $\exists (u, v), \operatorname{highbit}(a_u) < \operatorname{highbit}(k), \operatorname{highbit}(a_v) = \operatorname{highbit}(k)$ 使得 $a_u \operatorname{xor} a_v \leq k$ 。
但这个条件是充要的吗？

设 $\forall 1 \leq i \leq x, \operatorname{highbit}(a_i) < \operatorname{highbit}(k)$ ，且 $\forall x < i \leq n, \operatorname{highbit}(a_i) = \operatorname{highbit}(k)$ 。

不妨令 $u < v$ ：

若给出的 $u = x$ ，则可以构造从祖先到后代的左链 $x \to x - 1 \to \cdots \to 1$ ，右向边 $x \to v$ ，从祖先到后代的左链 $v \to v - 1 \to \cdots \to x + 1$ ，和从祖先到后代的右链 $v \to v + 1 \to \cdots \to n$ 。
$v = x + 1$ 同理。

但若不存在满足 $u = x \lor v = x + 1$ 的可行边 $(u, v)$ ，我们还可以构造吗？

事实上并不能，下面是一个简要的证明：

考虑反证法：假设有解，取 BST 上一条满足 $u < x, v > x + 1$ 的边 $(u, v)$ 。这样的 $(u, v)$ 应当存在，因为 $[1, x], [x + 1, n]$ 之间一定存在至少一条边，且不存在从 $x$ 连向 $[x + 1, n]$ 和从 $x + 1$ 连向 $[1, x]$ 的边。
不妨认为这是一条左向边 $v \to u$ ，则 $u$ 的右子树包含了区间 $[u + 1, v - 1]$ ，且 $x, x + 1 \in [u + 1, v - 1]$ 。我们要求仅考虑这一区间时有解。
这是一个递归结构，即：对于一个满足 $l < x, r > x + 1$ 的区间 $[l, r]$ ，其有解的必要条件为 $\exists [l', r'], \text{s.t. } l < l' < x, x + 1 < r' < r$ 且 $[l', r']$ 有解。
我们已知 $\forall x + 1 \leq r \leq n, [x, r]$ 和 $\forall 1 \leq l \leq x, [l, x + 1]$ 无解，而不难归纳出上述递归一定会终于这两类无解区间，故上述递归的初始区间 $[1, n]$ 无解，假设不成立。

综上，时间复杂度为 $O(Tn)$ 。

D. 「SFCOI-4」丰饶的小镇

解法一

$n \leq 62, q = \dfrac{n(n - 1)}{2}$

打表 / 观察可知 $O(n)$ 次后所求集合不变，故暴力模拟即可。

时间复杂度为 $O(qn^2)$ 。

$n, q \leq 500$

注意到 $p$ 互不相同，若最终 $T \neq \emptyset, a_i = \displaystyle\sum_{x \in T} 2^x$ ，则不难发现 $2^{\max(T)} \leq a_i \leq \displaystyle\sum_{i = 1}^{\max(T)} 2^i < 2^{\max(T) + 1}$ ，故 $\lfloor \log_2 a_i \rfloor = \max(T)$ 。

于是我们只需记录 $\max(T)$ ，时间复杂度不变。

方便起见，下面的 $a_i$ 均表示 $\max(T)$ 。

$n, q \leq 5 \times 10^3$

Observation 1：足够长时间后， $a$ 中留下的非零连续段长度只能为 $2$ 。

设连续段下标范围为 $[l, r]$ ，钦定 $a_0 = a_{n + 1} = 0$ ，证明如下：

长度为 $2$ 时，由于 $a_{l - 1} = a_{l + 2} = 0$ ，每一轮 $l$ 和 $r$ 中的人会“交换”，即 $\operatorname{swap}(a_l, a_r)$ ，满足条件。
长度为 $3$ 时，由于 $a_{l - 1} = a_{l + 3} = 0$ ，下一轮中 $l, r$ 中的人会进入 $l + 1$ ，而 $l + 1$ 中的人会进入 $l, r$ 之一，此时非零连续段长度变为 $2$ ，舍去。
长度 $\geq 4$ 时，令时间流逝一秒，若连续段长度不变，则“每个位置都有人换进来”，即 $\forall i \in [l, r]$ ，有 $i > l, a_i > a_{i - 2}$ 或 $i < r, a_i > a_{i + 2}$ 。
若连续段长度为奇数，有 $a_l > a_{l + 2} \Rightarrow a_{l + 2} > a_{l + 4} \Rightarrow \cdots \Rightarrow a_{r - 2} > a_r$ ，而 $r$ 别无选择只能要求 $a_r > a_{r - 2}$ ，矛盾，舍去。
若连续段长度为偶数，有 $a_l > a_{l + 2} \Rightarrow a_{l + 2} > a_{l + 4} \Rightarrow \cdots \Rightarrow a_{r - 1} > a_{r + 1}$ ，即下标奇偶性同 $l$ 的位置的值单调递减，同理有下标奇偶性同 $r$ 的位置的值单调递增。但在本次移动结束后，下标奇偶性同 $l$ 的位置的值将单调递增，有下标奇偶性同 $r$ 的位置的值单调递减，不再满足非零连续段长度不变的条件，故舍去。

Observation 2：在初始状态 $\{2^{p'_i}\}$ 的基础上，时间流逝一秒后，每个非零连续段中下标为奇数和下标为偶数的项分别构成的子序列均是单峰的。

注：这里的单峰指对于一个长为 $n$ 的 $\{a_i\}$ 而言， $\exists i \in [1, n]$ ，使得 $\forall j \in [1, i), a_j > a_{j + 1}$ 且 $\forall j \in (i, n], a_j < a_{j + 1}$ ，即包含了 $a$ 单调的退化情况。

证明：

注意到对初始状态而言，若 $i$ 满足 $2 < i < n - 2, a_i < \min(a_{i - 2}, a_{i + 2})$ 即 $i$ 是“谷底”，则 $a_i$ 将变为 $0$ ，左右连续段将从 $i$ 点被分割开，无论 $i$ 将会移动到 $i - 1$ 还是 $i + 1$ ，都只能是左右连续段的边界，不可能再成为“谷底”。
原本不是“谷底”者显然也不会再转化为新的“谷底”。请读者自行就这一项所处位置（峰顶或单调区间内）分类讨论以完成证明。

Observation 3：在初始状态 $\{2^{p'_i}\}$ 的基础上，时间流逝一秒后，对于一个长度 $\geq 2$ 的非零连续段，再经过足够长时间后，其不可能从中间被划分开，且留下的只有下标为偶数处的最大值和下标为奇数处的最大值。

证明：不妨假设 $l, r$ 奇偶性相同，且 $a_l < a_{l + 2} < \cdots < a_{l + 2k} > \cdots > a_{r - 2} > a_r$ ，则时间流逝一秒后（忽略 $k = 0, \dfrac{r - l}{2}$ 的 corner case）：

$a_{l + 1}$ 变为原 $a_l$ 或 $a_{l + 2}$ 。
$a_{l + 3}$ 变为原 $a_{l + 2}$ 或 $a_{l + 4}$ 。
$\cdots$
$a_{l + 2k - 1}$ 变为原 $a_{l + 2k - 2}$ 或 $a_{l + 2k}$ 。
$a_{l + 2k + 1}$ 变为原 $a_{l + 2k}$ 或 $a_{l + 2k + 2}$ 。
$a_{r - 3}$ 变为原 $a_{r - 4}$ 或 $a_{r - 2}$ 。
$a_{r - 1}$ 变为原 $a_{r - 2}$ 或 $a_r$ 。

此时新的 $\{a_{l + 1}, a_{l + 3}, \cdots, a_{r - 3}, a_{r - 1}\}$ 子序列显然仍为单峰序列，峰值位于 $l + 2k \pm 1$ 处。

另一单峰子序列 $a_{l + 1} < a_{l + 3} < \cdots < a_{l + 2k' + 1} > \cdots > a_{r - 3} > a_{r - 1}$ 的变化，以及 $l, r$ 奇偶性不同的情况同理，不再赘述。

又由于最后剩下的非零连续段长度只能为 $2$ ，且下标为偶数处的最大值和下标为奇数处的最大值一定不会消失，则只能留下它们。

Observation 4：非零连续段中下标为偶数处和下标为奇数处的最大值会一步一步地“相互靠近”，在两者相邻后将会一直互换下去。

证明：设这两个最大值的位置分别为 $x, y$ ，不妨取 $x < y$ 。

当 $y - x = 1$ ， $a_x, a_y$ 将互换。
当 $y - x > 1$ ，我们考察 $a_x$ 。注意到 $a_{x - 1} < a_{x + 1} < \cdots < a_y$ ，则 $a_x$ 会向右，即向 $a_y$ 的方向移动一步。 $a_y$ 则同理。

综上，我们暴力模拟第一秒的流逝，随后考虑直接统计答案：

设第一秒后某一个非零连续段中，下标为偶数处和下标为奇数处的最大值分别位于 $x, y$ 。
取 $\text{mid} = \lfloor \dfrac{x + y}{2} \rfloor$ ，则 $a_x$ 在再过偶数秒后会来到 $\text{mid} + 1$ 的位置，在再过奇数秒后会来到 $\text{mid}$ 的位置。

时间复杂度为 $O(qn)$ 。

$c_i = 1$

根据上面的观察，现在我们只关心第一秒后有几个连续段留下来。

首先特判区间长度为 $2, 3$ 的情况，此时答案为 $2$ 。

接下来，一个自然的想法是利用 $[1, n]$ 经过一秒后的信息。

忽略某些可能存在的边界情况后，我们发现：

若处理 $[1, n]$ 所得的一个非零连续段 $[L, R] \subseteq [l + 1, r - 1]$ ，我们“几乎”可以直接利用 $[L, R]$ 的信息。
原因是 $[l + 1, r - 1]$ 中的项只可能来自于 $[l, r]$ 。

但事实上有时候我们并不能这样做，如下面这种情况（记为 $S_1$ ）：

原本存在连续段 $[l - 1, l], [l + 2, \cdots]$ 。
现在考察 $[l, r]$ ，由连续段分布可知 $a_{l - 1} > a_{l + 1}$ 。
但此时 $a_{l - 1}$ 不存在了， $a_l$ 会被迫到达 $l + 1$ 。
因此，最终存在的是连续段 $[l + 1, \cdots (+1)]$ 。
这里 $(+1)$ 是因为右端点可能是 $r - 2$ ，下面同理。

另一种相似的情况（记为 $S_2$ ）是：

原本存在连续段 $[l - 1, l], [l + 3, \cdots]$ 。
现在考察 $[l, r]$ ，由连续段分布可知 $a_{l - 1} > a_{l + 1}$ 。
但此时 $a_{l - 1}$ 不存在了， $a_l$ 会被迫到达 $l + 1$ 。
因此，最终存在的是连续段 $[l, l + 1], [l + 3, \cdots (+1)]$ 。

注意到第一秒结束时，全零连续段的长度不超过 $2$ ，因此我们无需讨论全零连续段更长的情况。

我们还需考虑的另一种情况是若处理 $[1, n]$ 所得的一个非零连续段 $[L, R]$ 满足 $L < l \leq R < r$ 或 $l < L \leq r < R$ ，以前者为例。

若 $R = l$ ，即 $S_1, S_2$ 两种情况。
若 $R > l$ ，连续段将变为 $[l, R]$ （ $S_3$ ）。

综上，时间复杂度为 $O(n + q)$ 。

无特殊限制

前缀和记录某个范围内的连续段的答案之和，我们只需额外考虑边界上的变化。

$S_1$ ：考虑实际上的连续段中右端点来自哪里，转化为对单个连续段的询问。
$S_2$ ： $a_l, a_{l + 1}$ 反复交换，这是容易处理的。
$S_3$ ：考虑连续段中 $R$ 是来自 $a_{R - 1}$ 还是 $a_{R + 1}$ ，然后转化为对单个连续段的询问。

在上面三种情况中，我们需要通过询问奇偶位上的最大值求出单个连续段的情况。

综上，我们通过 ST 表支持区间最大值查询，时间复杂度为 $O(n \log n + q)$ 。

似乎比楼下解法二的线段树好写一些？

解法二

$n, q \leq 500$

直接暴力模拟这一过程，我们可以发现每次搬迁必然会使起码两堆人合并，那么只需要在整个过程维持稳定后用任意一次偶数次操作的结果即可得到最终答案。最后需要偶数次操作的结果是因为我们发现最后由空建筑相隔开的每一组有人的建筑都一定只有两堆人相互交换，只有这种情况是稳定的。

无特殊限制

正解之一。我们考虑什么情况下一个建筑物会变成空的，然后我们就会发现当进行一次操作后，将奇数位和偶数位数字拆开来看每一组建筑物一定会形成单峰。而在这之后奇数位的最大值和偶数位的最大值又一定会由于单峰的原因相互靠近，最后形成的稳定“二人转”模式的数字和位置我们就都知道了。

我们考虑使用一个大线段树维护这一结果。这个线段树中初始存储的信息就是第一轮操作之后的每个位置的数字，那么在合并的时候我们需要注意两个区间之间是否有零，合并过程时是否要加贡献等（实则这部分分讨十分麻烦，建议直接看代码）。对于一个询问只需要进行单点修改加区间查询即可。

#include<bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int N=1e6;
int n,q,cnt;
int a[N],aft[N],b[N];
long long qpow[N];
struct node{
    long long sum;
    int lmaxji,lmaxou,rmaxji,rmaxou,l0,r0;
    node(){
        sum=0;
        lmaxji=lmaxou=rmaxji=rmaxou=0;
        l0=r0=1;
    }
};
node tr[N],w;
long long cocu(int ji,int ou){
	int m=(ji+ou)/2;
	if(m%2==1){
		return qpow[m]*aft[ou]+qpow[m+1]*aft[ji];
	}else{
		return qpow[m]*aft[ji]+qpow[m+1]*aft[ou];
	}
}
int max1(int num1,int num2){
	if(aft[num1]>aft[num2])return num1;
	else return num2;
}
node merge(node x,node y){
	node z;
	z.sum=x.sum+y.sum;
	z.l0=x.l0;
	z.r0=y.r0;
	if(x.r0==1){
		z.lmaxji=x.lmaxji;
		z.lmaxou=x.lmaxou;
		z.rmaxji=y.rmaxji;
		z.rmaxou=y.rmaxou;
		if(y.lmaxji!=y.rmaxji&&y.lmaxou!=y.rmaxou){
			z.sum+=cocu(y.lmaxji,y.lmaxou);
		}
	}else if(y.l0==1){
		z.lmaxji=x.lmaxji;
		z.lmaxou=x.lmaxou;
		z.rmaxji=y.rmaxji;
		z.rmaxou=y.rmaxou;
		if(x.lmaxji!=x.rmaxji&&x.lmaxou!=x.rmaxou){
			z.sum+=cocu(x.rmaxji,x.rmaxou);
		}
	}else if(x.lmaxji==x.rmaxji&&x.lmaxou==x.rmaxou&&y.lmaxji==y.rmaxji&&y.lmaxou==y.rmaxou){
		z.lmaxji=max1(x.lmaxji,y.lmaxji);
		z.rmaxji=z.lmaxji;
		z.lmaxou=max1(x.lmaxou,y.lmaxou);
		z.rmaxou=z.lmaxou;
	}else if(x.lmaxji==x.rmaxji&&x.lmaxou==x.rmaxou){
		z.rmaxji=y.rmaxji;
		z.rmaxou=y.rmaxou;
		z.lmaxji=max1(x.lmaxji,y.lmaxji);
		z.lmaxou=max1(x.lmaxou,y.lmaxou);
	}else if(y.lmaxji==y.rmaxji&&y.lmaxou==y.rmaxou){
		z.lmaxji=x.lmaxji;
		z.lmaxou=x.lmaxou;
		z.rmaxji=max1(x.rmaxji,y.rmaxji);
		z.rmaxou=max1(x.rmaxou,y.rmaxou);
	}else{
		z.lmaxji=x.lmaxji;
		z.lmaxou=x.lmaxou;
		z.rmaxji=y.rmaxji;
		z.rmaxou=y.rmaxou;	
		z.sum+=cocu(max1(x.rmaxji,y.lmaxji),max1(x.rmaxou,y.lmaxou));
	}
	return z;
}
void cge(int s,int l,int r,int pos){
	if(l==r){
		if(l%2==1){
			tr[s].lmaxji=pos;
			tr[s].rmaxji=pos;	
		}else{
			tr[s].lmaxou=pos;
			tr[s].rmaxou=pos;
		}
		if(aft[pos]==0)tr[s].l0=1,tr[s].r0=1;
		else tr[s].l0=0,tr[s].r0=0;
		tr[s].sum=0;
		return;
	}
	if(pos<=mid)cge(s*2,l,mid,pos);
	else cge(s*2+1,mid+1,r,pos);
	tr[s]=merge(tr[s*2],tr[s*2+1]);
}
node ans(int s,int l,int r,int ll,int rr){
	if(ll<=l&&rr>=r){
		return tr[s];
	}
	if(rr<=mid)return ans(s*2,l,mid,ll,rr);
	else if(ll>mid)return ans(s*2+1,mid+1,r,ll,rr);
	else return merge(ans(s*2,l,mid,ll,rr),ans(s*2+1,mid+1,r,ll,rr));
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>qpow[i];
	}
	for(int i=1;i<=n;i++){
		if(a[i-1]>a[i+1]){
			aft[i-1]=max(aft[i-1],a[i]);
		}else{
			aft[i+1]=max(aft[i+1],a[i]);
		}
	}
	int ll=3,rr=4;
	for(int i=1;i<=n;i++){
		cge(1,1,n,i); 
	}
	for(int i=1;i<=q;i++){
		cin>>ll>>rr;
		b[ll+1]=a[ll];
		if(a[ll+2]<a[ll]||ll+2>rr){
			b[ll]=a[ll+1];
		}
		if((a[ll+3]<a[ll+1]||ll+3>rr)&&ll+2<=rr){
			b[ll+1]=max(b[ll+1],a[ll+2]);
		}
		b[rr-1]=a[rr];
		if(a[rr-2]<a[rr]||rr-2<ll){
			b[rr]=a[rr-1];
		}
		if((a[rr-3]<a[rr-1]||rr-3<ll)&&rr-2>=ll){
			b[rr-1]=max(b[rr-1],a[rr-2]);
		}
		if(rr-ll>=3){
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
			swap(b[rr],aft[rr]);
			swap(b[rr-1],aft[rr-1]);
		}else if(rr-ll==2){
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
			swap(b[rr],aft[rr]);
		}else{
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
		}
		if(b[ll]!=aft[ll])cge(1,1,n,ll);
		if(b[ll+1]!=aft[ll+1])cge(1,1,n,ll+1);
		if(b[rr]!=aft[rr])cge(1,1,n,rr);
		if(b[rr-1]!=aft[rr-1])cge(1,1,n,rr-1);
		node w=ans(1,1,n,ll,rr),w2;
		cout<<merge(w2,merge(w,w2)).sum<<"\n";
		if(rr-ll>=3){
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
			swap(b[rr],aft[rr]);
			swap(b[rr-1],aft[rr-1]);
		}else if(rr-ll==2){
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
			swap(b[rr],aft[rr]);
		}else{
			swap(b[ll],aft[ll]);
			swap(b[ll+1],aft[ll+1]);
		}
		if(b[ll]!=aft[ll])cge(1,1,n,ll);
		if(b[ll+1]!=aft[ll+1])cge(1,1,n,ll+1);
		if(b[rr]!=aft[rr])cge(1,1,n,rr);
		if(b[rr-1]!=aft[rr-1])cge(1,1,n,rr-1);
		b[ll]=0;
		b[rr]=0;
		b[ll+1]=0;
		b[rr-1]=0;
	}
	return 0;
}

（并不建议写又臭又长的线段树，不过线段树做法可以支持单点修改操作，为了避免这道题太过毒瘤就没加上去。）

E. 「SFCOI-4」大户爱的草

解法一

$n \leq 5 \times 10^3$

在绝对值函数的凸性之外，解决此类问题的另一常见思路是拆贡献。

考虑将 $a$ 离散化为 $c_1, c_2, \cdots, c_k$ ，则 $\forall t \in [1, k)$ ，一个合法的方案 $a'$ 需要满足：

$\forall b_i = 1, [a'_i > c_t] \leq [a'_{i \bmod n + 1} > c_t]$ 。
$\forall b_i = 2, [a'_i > c_t] \geq [a'_{i \bmod n + 1} > c_t]$ 。

且此次我们计入的贡献为 $(c_{t + 1} - c_t) \displaystyle\sum_{i = 1}^n [[a'_i > c_t] \neq [a_i > c_t]]$ 。

如果忽略当前 $t$ 之外的其他限制，我们很容易给出一个就当前 $t$ 而言 $O(n)$ 的 dp 解法：

枚举 $[a'_1 > c_t] \in \{0, 1\}$ 。
设 $dp_{i, j = 0/1}$ 表示 $[a'_1 > c_t] = j$ 时 $1 \sim i$ 部分的最小贡献。
转移略去，答案需根据 $b_n$ 统计。

但放眼全局，我们能确保一个全局的最优方案在只考虑 $t$ 的限制的前提下也是最优方案之一吗？

原问题本身是一个 $L_1$ 的保序回归问题。

根据保序回归问题的性质（参见《IOI2018 中国国家候选队论文集》中《浅谈保序回归问题》一文），在 $\{a_i\}$ 的初始状态下一个最优的方案 $\{a'_i\}$ ，满足在 $\{\max(\min(a_i, c_t), c_{t + 1})\}$ 的初始状态下 $\{\max(\min(a'_i, c_t), c_{t + 1})\}$ 也是一个最优的方案。

因此，对于每个 $t$ 分别 dp，并将贡献求和，将取得答案下界，并且根据上面的性质，存在相应的一组解。

时间复杂度为 $O(n^2)$ 。

无特殊限制

从小到大遍历 $c$ ，则我们需要维护的操作为下面两类各 $n$ 次：

将某个位置从 $1$ 变成 $0$ 。
对两种不同的初值 $(dp_{1, 0}, dp_{1, 1}) = (0, +\infty), (+\infty, 0)$ 分别求 $(dp_{n, 0}, dp_{n, 1})$ 。

不难发现 dp 转移可以表示为 $2 \times 2$ 矩阵的 $(\min, +)$ 卷积，故线段树维护矩阵乘法即可。

时间复杂度为 $O(n \log n)$ ，非常好写。

解法二

$n \leq 5 \times 10^3$

直接跑保序回归的一般解法（即整体二分 + 最大权闭合子图），时间复杂度为 $O(n \operatorname{Flow}(n, 2n))$ 。

注意到最大权闭合子图可以换成 $O(n)$ 的 dp，时间复杂度降至 $O(n^2)$ 。

无特殊限制

注意到我们其实并没有必要在 dp 中算完整个环的情况：

若要求 $a'_s \leq a'_t \geq a'_u$ 或 $a'_s \geq a'_t \leq a'_u$ ，但 $t$ 不再出现在当前讨论的集合里，我们可以从 $t$ 处断开。
由于当前讨论的集合中的数是连续的一段，不存在 $a'_s \leq a'_t \leq a'_u$ 或 $a'_s \geq a'_t \geq a'_u$ 但 $t$ 不再出现在当前讨论的集合里的情况。

因此我们对断开的每一段分别 dp，若离散化则时间复杂度为 $O(n \log n)$ 。

F. 「SFCOI-4」追忆的残响

符号约定：

记 $u = \min(n, m)$ ，值域 $w = \max(n, m)$ 。
对于正整数 $n \geq 2$ ，记 $\operatorname{lpf}(n)$ 表示 $n$ 的最小质因数。
特别地，令 $\operatorname{lpf}(1) = +\infty, \operatorname{mpf}(1) = 0$ 。

下设 $S(n, p) = \displaystyle\sum_{i = 1}^n [\operatorname{lpf}(i) \geq p]$ 。

枚举 $d = \operatorname{lca}(i, j) \leq u$ ，令 $i' = \dfrac{i}{d}, j' = \dfrac{j}{d}$ ，则条件为：

$i' \leq \dfrac{n}{d}, j' \leq \dfrac{m}{d}$ 。
$\operatorname{lpf}(i'), \operatorname{lpf}(j') \geq \operatorname{mpf}(d)$ 。
限制 P： $\operatorname{lpf}(i') \neq \operatorname{lpf}(j')$ 。

一个直观但错误的想法是：

设 $f_d$ 表示 $d \mid \operatorname{lca}(i, j)$ 的 $(i, j)$ 对数，这是容易计算的，因为限制 P 被去除了。其为 $S(\lfloor \dfrac{n}{d} \rfloor, \operatorname{mpf}(d)) S(\lfloor \dfrac{m}{d} \rfloor, \operatorname{mpf}(d))$ 。
设 $g_d$ 表示 $d = \operatorname{lca}(i, j)$ 的 $(i, j)$ 对数。
由莫比乌斯反演可知 $f_d = \displaystyle\sum_{d \mid i} g_i \Leftrightarrow g_d = \displaystyle\sum_{d \mid i} \mu(\frac{i}{d}) f_i$ 。
进而易知答案为 $\displaystyle\sum_{d = 1}^u d \times g_d = \sum_{i = 1}^u \varphi(i) f_i$ 。

事实上可以发现：

上面的 $f_d$ 计算式表示的是 $d \mid \operatorname{lca}(i, j) \land \operatorname{lpf}(\dfrac{\operatorname{lca}(i, j)}{d}) \geq \operatorname{mpf}(d)$ 的 $(i, j)$ 对数。
即 $f_d = \displaystyle\sum_{d \mid i} [\operatorname{lpf}(\frac{i}{d}) \geq \operatorname{mpf}(d)] g_i$ 。

考虑容斥：取质数 $p \geq \operatorname{mpf}(d)$ ，则可以发现所有 $f_{dp}$ 所描述的数对没有交集（因为这些数对的 $\operatorname{lca}$ 的质因数分解式中大于 $\operatorname{mpf}(d)$ 的首项不同），且正是我们所需去除的部分。

故 $\forall d > 1, g_d = f_d - \displaystyle\sum_{p \in \operatorname{Prime}, p \geq \operatorname{mpf}(d)} f_{dp}$ 。

进而可以化简得出答案：

\begin{aligned} \operatorname{ans} &= \sum_{d = 1}^u d \times g_d \\ &= \sum_{d = 1}^u d (f_d - \sum_{p \in \operatorname{Prime}, p \geq \operatorname{mpf}(d)} f_{dp}) \\ &= \sum_{d = 1}^u d f_d - \sum_{T = 2}^u \dfrac{T}{\operatorname{mpf}(T)} f_T \\ &= \sum_{d = 1}^u h(d) f_d \end{aligned}

其中 $h(1) = 1$ ， $\forall n > 1, h(n) = n - \dfrac{n}{\operatorname{mpf}(n)}$ 。

对第三到第四行稍加解释：枚举 $T = dp$ ，由 $p \geq \operatorname{mpf}(d)$ 知对应的 $p$ 仅可能为 $\operatorname{mpf}(T)$ ，故 $d = \dfrac{T}{\operatorname{mpf}(T)}$ 。

推式子到此为止，下面讨论其计算方法。

注意到若 $1 \leq n < p^2$ ， $S(n, p) = [n \geq p] (\pi(n) - \pi(p) + 1) + 1$ ，这是可以 $O(1)$ 计算的。

故而我们只需对 $[1, \sqrt[3]{w}]$ 中的 $p$ 预处理所有可能的 $n \in [p^2, \dfrac{w}{p}]$ 的答案即可 $O(1)$ 查询，此处预处理时间复杂度为 $O(w \ln \ln w)$ 。

但直接暴力计算的时间复杂度为 $O(Tw + w \ln \ln w)$ ，还不如 $O(Tw)$ 暴力。下面考虑优化。

$1 \leq T \leq 2 \times 10^3, 1 \leq n, m \leq 10^7$

这部分的思路始于一个观察：

当 $d \leq u, d \operatorname{mpf}(d) > w$ ，对应的答案中只含 $(d, d)$ 一对。
而事实上，满足 $d \operatorname{mpf}(d) \leq w$ 的 $d$ 并不太多。实测其数量在 $w = 10^7$ 时为 $\psi = 44947$ 。
这里提及了 $\psi$ 的渐进估计为 $n \exp(-(1 + o(1)) \sqrt{2 \ln n \ln \ln n})$ 。
事实上，这也是 Min_25 筛 Part 2 的 dfs 写法所会访问到的的状态数。

因此，只需暴力枚举这样的 $d$ 计算即可。时间复杂度为 $O(w \ln \ln w + T \psi)$ 。

无特殊限制

$w = 2 \times 10^7$ 时 $\psi = 73100$ 。

考虑延续前一部分将贡献拆分为 $d \operatorname{mpf}(d) \leq w, d \operatorname{mpf}(d) > w$ 两部分的思路。

Part 1：特殊处理 $(d, d)$

Part 2： $p \leq \lfloor \dfrac{w}{d} \rfloor < p^2$

讨论 $u$ 一方的贡献，可分为：

（A） $1 \leq \lfloor \dfrac{u}{d} \rfloor < p$ ：贡献为 $h_d (\pi(\lfloor \dfrac{w}{d} \rfloor) - \pi(p) + 1)$ 。
（B） $p \leq \lfloor \dfrac{u}{d} \rfloor < p^2$ ：贡献为 $h_d ((\pi(\lfloor \dfrac{w}{d} \rfloor) - \pi(p) + 2)(\pi(\lfloor \dfrac{u}{d} \rfloor) - \pi(p) + 2) - 1)$ 。

这样的 $d$ 的数量同样是 $O(\psi)$ 的。

不妨先考虑计算 A。首先明确我们的问题：

设 $X(d) = d \operatorname{mpf}(d), Y(d) = d \operatorname{mpf}(d)^2$ 。
求满足 $u < X(d) \leq w, Y(d) > w$ 的 $h_d (\pi(\lfloor \dfrac{w}{d} \rfloor) - \pi(p) + 1)$ 之和。

$Y(d)$ 的限制让人非常难受，先不考虑它，我们把它留到 Part 3 来处理。

剩下部分是一个变形的二维数点，我们可以差分后拆一下式子：

$h_d \pi(\lfloor \dfrac{w}{d} \rfloor)$ ：这是一个数论分块的形式，考虑运用 Dirichlet 双曲线法，取 $x_0 y_0 = w$ ，答案转化为 $\displaystyle\sum_{i = 1}^{x_0} [X(i) \leq w] h_i \pi(\lfloor \dfrac{w}{i} \rfloor) + \sum_{i \in \operatorname{Prime}}^{y_0} H(\lfloor \dfrac{w}{i} \rfloor) - H(x_0) \pi(y_0)$ ，其中 $H$ 表示满足 $X(i) \leq w$ 的 $d$ 的 $h_d$ 之前缀和。取 $x_0 = y_0 = \sqrt{w}$ ，离线下来树状数组维护 $H$ 即可。时间复杂度为 $O(T \sqrt{w})$ 。
注：这里当然也可以直接数论分块，但你需要注意把 $\pi(\lfloor \dfrac{w}{d} \rfloor)$ 相同的项钦定到一块，要不然这部分时间复杂度会退化为 $O(T \sqrt{w} \log w)$ 。为使时间复杂度正确，写成数论分块的形式反而更麻烦。
$h_d(1 - \pi(p))$ ：这个只与 $d$ 有关，离线下来树状数组即可。时间复杂度为 $O((\psi + T) \log w)$ 。

接下来考虑计算 B。首先仍然明确我们的问题：

求满足 $X(d) \leq u, Y(d) > w$ 的 $h_d ((\pi(\lfloor \dfrac{w}{d} \rfloor) - \pi(p) + 2)(\pi(\lfloor \dfrac{u}{d} \rfloor) - \pi(p) + 2) - 1)$ 之和。

仍然先忽略 $Y(d)$ 的限制，我们同样可以拆式子得到下面三部分：

$h_d \pi(\lfloor \dfrac{w}{d} \rfloor) \pi(\lfloor \dfrac{u}{d} \rfloor)$
$h_d(2 - \pi(p))(\pi(\lfloor \dfrac{w}{d} \rfloor) + \pi(\lfloor \dfrac{u}{d} \rfloor))$
$h_d((2 - \pi(p))^2 - 1)$

计算方法与 A 基本一致，不再赘述。

综上，该部分时间复杂度为 $O(w + \psi \log w + T \sqrt{w})$ 。

Part 3： $\lfloor \dfrac{w}{d} \rfloor \geq p^2$

这样的 $d$ 只有 $\displaystyle\sum_{i = 2}^w [i \operatorname{mpf}^2(i) \leq w]$ 个。实测该式在 $w = 2 \times 10^7$ 时为 $\vartheta = 6332$ 。

由那篇论文可知 $\vartheta$ 的渐进估计为 $n \exp(-(2 + o(1)) \sqrt{\ln n \ln \ln n})$ 。

枚举 $p \leq w^{\frac{1}{3}}$ ，预处理出 $S(\_, p)$ 后直接遍历即可。时间复杂度为 $O(w \ln \ln w + T \vartheta)$ 。

最后来解决一下 Part 2 中的遗留问题：直接枚举满足 $Y(d) \leq w$ 的 $d$ 并删去其贡献即可，时间复杂度不变。

综上，时间复杂度为 $O(w \ln \ln w + \psi \log w + T(\sqrt{w} + \vartheta))$ 。

代码：

#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

struct Item {
	int d;
	int x;
	
	Item(){}
	
	Item(int _d, int _x){
		d = _d;
		x = _x;
	}
};

struct Query {
	int id;
	int up;
	int type;
	
	Query(){}
	
	Query(int _id, int _up, int _type){
		id = _id;
		up = _up;
		type = _type;
	}
};

const int N = 59728;

struct BIT {
	ll tree[N + 1];
	
	int lowbit(int x){
		return x & (-x);
	}
	
	void add(int x, ll k){
		while (x <= N){
			tree[x] += k;
			x += lowbit(x);
		}
	}
	
	ll get_sum(int x){
		ll ans = 0;
		while (x > 0){
			ans += tree[x];
			x -= lowbit(x);
		}
		return ans;
	}
};

const int M = 1.5e7, K = M / 2, P = 970704, Q = 3872, R = 2.5e4, S = 2355, T = R * 2, V = cbrt(M);
int mpf[M + 1], pi[K + 1], prime[P + 1], h[Q + 1], x[Q + 1], u[R + 1], w[R + 1], perm[R + 1], pre_item[M + 1], s[K + 1], lst[S + 1];
ll ans[R + 1];
bool p[M + 1], vis[K + 1];
Item item[N + 2];
Query query[T + 1];
BIT bit1, bit2, bit3, bit4;

bool operator <(const Item a, const Item b){
	return a.x < b.x;
}

bool operator <(const Query a, const Query b){
	return a.up < b.up;
}

void init(){
	int cnt = 0;
	p[0] = p[1] = true;
	mpf[1] = 0;
	pi[1] = 0;
	for (int i = 2; i <= M; i++){
		if (!p[i]){
			cnt++;
			prime[cnt] = i;
			mpf[i] = i;
		}
		if (i <= K) pi[i] = cnt;
		for (int j = 1; j <= cnt && i * prime[j] <= M; j++){
			int t = i * prime[j];
			p[t] = true;
			mpf[t] = mpf[i];
			if (i % prime[j] == 0) break;
		}
	}
	for (int i = 2; i <= Q; i++){
		h[i] = i - i / mpf[i];
		x[i] = i * mpf[i];
	}
}

ll calcx(int w, int u){
	int wsq = sqrt(w), usq = sqrt(u);
	ll ans = 0;
	for (int i = 2; i <= wsq; i++){
		int tw = w / i, tu = u / i;
		if (x[i] <= u){
			ans += h[i] * (1ll * (2 - pi[mpf[i]]) * pi[tw] + 1ll * pi[tw] * pi[tu] + (i <= usq ? 1ll * (2 - pi[mpf[i]]) * pi[tu] : 0));
		} else if (i <= u && x[i] <= w){
			ans += 1ll * h[i] * pi[tw];
		}
		if (!p[i]) ans += bit2.get_sum(pre_item[min(tw, u)]) + (i <= usq ? bit3.get_sum(pre_item[tu]) : 0);
	}
	ans -= bit2.get_sum(pre_item[wsq]) * pi[wsq] + bit3.get_sum(pre_item[usq]) * pi[usq];
	return ans;
}

ll calcy(int w, int u){
	int sq = sqrt(w);
	int tu = pi[u / (sq + 1)];
	if (tu == 0) return 0;
	int ru = u / prime[tu], tw = pi[w / (sq + 1)], rw = w / prime[tw];
	ll x = bit1.get_sum(pre_item[sq]), y, ans = 0;
	while (tu >= 1){
		int ruw = min(ru, rw);
		y = bit1.get_sum(pre_item[ruw]);
		ans += (y - x) * tu * tw;
		x = y;
		if (ru == ruw && --tu >= 1) ru = u / prime[tu];
		if (rw == ruw && --tw >= 1) rw = w / prime[tw];
	}
	return ans;
}

ll calcz(int w, int u){
	int sq = sqrt(w);
	if (u <= sq) return 0;
	ll ans = 0;
	for (int i = 1; prime[i] <= sq; i++){
		ans += bit1.get_sum(pre_item[min(w / prime[i], u)]);
	}
	ans -= bit1.get_sum(pre_item[sq]) * pi[sq];
	return ans;
}

void solve(int t){
	int item_cnt = 0, query_cnt = 0;
	ll sum = 0;
	for (int i = 1; i <= t; i++){
		perm[i] = i;
		ans[i] = 1ll * u[i] * w[i];
	}
	sort(perm + 1, perm + t + 1, [](const int a, const int b){
		return u[a] < u[b];
	});
	for (int i = 1, j = 1; i <= M && j <= t; i++){
		if (i > 1) sum += i - i / mpf[i];
		while (j <= t && u[perm[j]] == i){
			ans[perm[j]] += sum;
			j++;
		}
	}
	for (int i = 2; i <= M; i++){
		ll x = 1ll * i * mpf[i];
		if (x <= M) item[++item_cnt] = Item(i, (int)x);
		pre_item[i] = item_cnt;
	}
	sort(item + 1, item + item_cnt + 1);
	item[item_cnt + 1].x = M + 1;
	for (int i = 1; i <= t; i++){
		if (u[i] > 1){
			query[++query_cnt] = Query(i, u[i], -1);
			query[++query_cnt] = Query(i, w[i], 1);
		}
	}
	sort(query + 1, query + query_cnt + 1);
	for (int i = 1, j = 1; i <= item_cnt && j <= query_cnt; i++){
		int d = item[i].d, h = d - d / mpf[d], c = 2 - pi[mpf[d]];
		bit1.add(pre_item[d], h);
		bit2.add(pre_item[d], h * (c - 1));
		bit3.add(pre_item[d], h * c);
		bit4.add(pre_item[d], h * (1ll * c * c - 1));
		while (j <= query_cnt && query[j].up < item[i + 1].x){
			int id = query[j].id;
			if (query[j].type == -1){
				ans[id] += calcx(w[id], u[id]) + calcy(w[id], u[id]) - bit2.get_sum(pre_item[u[id]]) + bit4.get_sum(pre_item[u[id]]);
			} else {
				ans[id] += calcz(w[id], u[id]) + bit2.get_sum(pre_item[u[id]]);
			}
			j++;
		}
	}
	for (int i = 1; prime[i] <= V; i++){
		int p = prime[i], lim1 = M / p, lim2 = lim1 / p, cnt = 0;
		if (i > 1){
			int q = prime[i - 1];
			for (int j = q; j <= lim1; j += q){
				vis[j] = true;
			}
		}
		for (int j = 1; j <= lim2; j++){
			if (mpf[j] <= p) lst[++cnt] = j;
		}
		for (int j = 1; j <= lim1; j++){
			s[j] = s[j - 1];
			if (!vis[j]) s[j]++;
		}
		for (int j = 1; j <= t; j++){
			if (u[j] < p) continue;
			int wlim = w[j] / p, ulim = u[j] / p, up1 = min(wlim / p / p, ulim), up2 = ulim / p;
			ll temp = 0;
			for (int k = 1; k <= cnt; k++){
				int x = lst[k];
				if (x > up1) break;
				int tw = wlim / lst[k], tu = ulim / lst[k];
				ll y = 1ll * s[tw] * s[tu] - 1;
				if (x <= up2){
					y -= 1ll * (pi[tw] - i + 2) * (pi[tu] - i + 2) - 1;
				} else {
					y -= pi[tw] - i + 1;
				}
				temp += x * y;
			}
			ans[j] += temp * (p - 1);
		}
	}
}

int main(){
	int t;
	scanf("%d", &t);
	init();
	for (int i = 1; i <= t; i++){
		int n, m;
		scanf("%d %d", &n, &m);
		u[i] = min(n, m);
		w[i] = max(n, m);
	}
	solve(t);
	for (int i = 1; i <= t; i++){
		printf("%lld\n", ans[i]);
	}
	return 0;
}