2024.8.8 test

A

对于长度为 \(2^n\) 的序列 \(A,B\)，求 \(c_{k}=\max_{i|j}a_i+b_j\)，\(n\le 18\)。

考虑分治：每次分成 \(A_0,A_1,B_0,B_1\)。
那么，\(C_0=\max(A_0+B_0),C_1=\max(A_0+B_1,A_1+B_0,A_1+B_1)\)。
我们继续分治下去，即上面四种情况每种都要做一遍。
不妨合并同类项，\(C_1=\max(A_1+\max(B_0,B_1),B_1+\max(A_0,A_1))\)。
把 \(B_1\) 跟 \(B_0\) 取 \(\max\)，\(A_1\) 跟 \(A_0\) 取 \(\max\)，这样只需要做三种情况。主定理算出 \(O(3^n)\)。
还有一种想法是：枚举 \(k,i\)，那么就是要查询某些位强制填 \(0\)，某些填 \(1\)，某些任意这个集合的 \(\max\)。
可以写成 \(01?\) 这种形式，总共只有 \(3^n\) 种询问。
还有一种想法是：枚举 \(k\)，把所有 \(i\cap j=0,i\cup j=k\) 的写出来，把 \(j\) 做一个后缀 \(\max\) 即可。
感觉对这类问题一窍不通。

C

有向图，求 \(s\to t\) 的最短路，可以走一次 \(u\to v\)（这条边可以没有），代价为 \((u-v)^2\)。

注意到直接做边数是 \(O(n^2)\)，所以我们要分层图。
先做一遍最短路，整体转移，用李超树维护转移，然后再松弛一遍即可。

D

三个序列 \(A,B,C\)，定义 \(f_A(l,r)=\min(A_l\sim A_r)\)，求所有区间的 \(f_A\times f_B\times f_C\) 的和。
\(n\le 10^5\)。

扫描线，单调栈，线段树维护 \(ABC,AB,AC,BC,A,B,C\) 的和即可，只需区间加。