HDU6971. I love max and multiply
题意：
给出长度为\(n\)的两个序列\(\{a_n\},\{b_n\}\)(下标为\(0\)到\(n-1\))。设\(c_k=\max\limits_{i\&j\geq k}(a_ib_j)\)，求\(\sum\limits_{k=0}^{n-1}c_k\)
分析：
关键是如何快速求解所有的\(c_k\)。
为了方便叙述，先对使用到的符号及定理作阐述，在分析的结尾会对定理进行证明。
- 定义1：一个整数\(a\)的二进制表示的第\(x\)位记作\(a[x]\)，显然\(a[x]\in\{0,1\}\)
- 定义2：对于整数\(a,b\)，定义符号\(\subseteq\)为
- 定理1：\(k\subseteq i\&j\iff k\subseteq i \land k\subseteq j\)
- 定理2：\(a \subseteq b \implies a \leq b\)
- 定理3：若\(a_l=\min a,a_r=\max a,b_l=\min b,b_r=\max b\)，则\(\max(ab) =\max\{a_lb_l,a_lb_r,a_rb_l,a_rb_r\}\)
设\(C_k=\{a_ib_j\mid k\leq i\& j\}\)，则有\(c_k=\max C_k\)，发现这难以处理。
我们可以先考虑\(M_k=\{a_i b_j\mid k\subseteq i\&j\}\)
由定理1发现\(M_k=\{a_i b_j\mid k\subseteq i \land k\subseteq j\}\)
设\(A_k=\{a_i\mid k\subseteq i\}\)，\(B_k=\{b_i\mid k\subseteq i\}\)，\(m_k=\max M_k\)
由定理3，可得
\(m_k=\max\{\max A_k\cdot\max B_k,\min A_k\cdot\max B_k,\max A_k\cdot\min B_k,\min A_k\cdot\min B_k\}\)
而所有的\(\max A_k,\min A_k,\max B_k,\min B_k\)通过动态规划很容易在\(O(n\log n)\)的时间内处理，再花\(O(n)\)的时间可以将所有的\(m_k\)处理出来。
由定理2，有\(k \subseteq i \& j \implies k \leq i \& j\)，
进一步思考发现
所以很容易产生一个想法\(C_k=\bigcup\limits_{i=k}^{n-1}M_i\)，如果这个想法成立，就有\(c_k=\max\limits_{k\leq i\leq n-1}m_i\)成立
事实上，这个想法确实成立，写成定理4。
- 定理4：若\(C_k=\{a_ib_j\mid k\leq i\& j\}\)，\(M_k=\{a_i b_j\mid k\subseteq i\&j\}\)，则有\(C_k=\bigcup\limits_{i=k}^nM_i\)
于是可以花费的\(O(n)\)的时间处理出所有的\(c_k\)，再用\(O(n)\)的时间可以算出答案，总的时间复杂度为\(O(n\log n)\)。
接下来证明上面4个定理（其实没必要看证明）：
-
定理1：
\[\begin{aligned} k\subseteq i\&j&\iff\forall x(k[x]=0\lor(i\&j)[x]=1)\\ &\iff\forall x(k[x]=0\lor (i[x]=1\land j[x]=1))\\ &\iff\forall x((k[x]=0\lor i[x]=1)\land (k[x]=0\lor j[x]=1))\\ &\iff\forall x(k[x]=0\lor i[x]=1)\land \forall x(k[x]=0\lor j[x]=1)\\ &\iff k\subseteq i \land k\subseteq j \end{aligned} \] -
定理2：
\[\begin{aligned} a\subseteq b \iff\forall x(a[x]=0\lor b[x]=1)\\ \end{aligned} \]由于\(a[x],b[x]\in\{0,1\}\)，所以
\[a[x]=0\lor b[x]=1 \iff a[x] \leq b[x] \]从而有
\[\begin{aligned} a\subseteq b &\iff\forall x(a[x]\leq b[x])\\ \end{aligned} \]而\(\forall x(a[x]\leq b[x])\implies a\leq b\)（显然逆命题不成立）
\[a\subseteq b\implies a \leq b \]
则有证毕
-
定理3：
-
若\(0\leq a_l\leq a_r,b_r\geq 0\)
- 当\(b<0\)时，\(ab\leq0\)
- 当\(b\geq 0\)时，\(ab\leq a_rb\leq a_r b_r\)
所以\(\max(ab) = a_r b_r\)
-
若\(0\leq b_l\leq b_r,a_r\geq 0\)，同1，\(\max(ab) = a_r b_r\)
-
若\(a_l\leq a_r\leq 0,b_l\leq 0\)
则有\(0\leq -a_r\leq -a_l,-b_l\geq 0\)- 当\(-b<0\)时，\(ab\leq 0\)
- 当\(-b \geq 0\)时，\(ab=(-a)(-b)\leq (-a_l)(-b)\leq (-a_l)(-b_l)\leq a_lb_l\)
所以\(\max(ab) = a_l b_l\)
-
若\(b_l\leq b_r\leq 0,a_l\leq 0\)，同3，\(\max(ab) = a_l b_l\)
-
若\(a_l \leq a_r\leq 0,0\leq b_l\leq b_r\)，则\(ab\leq ab_l\leq a_rb_l\)，所以\(\max(ab) = a_r b_l\)
-
若\(b_l \leq b_r\leq 0,0\leq a_l\leq a_r\)，同5，\(\max(ab) = a_l b_r\)
-
若\(a_l<0<a_r,b_l<0<b_r\)，
- 当\(a\geq0,b\leq0 \lor a\leq0,b\geq0\)时，\(ab\leq0\)
- 当\(a>0,b>0\)时，同1，\(\max(ab) = a_r b_r\)
- 当\(a<0,b<0\)时，同3，\(\max(ab) = a_l b_l\)
所以\(\max(ab)=\max\{a_lb_l,a_rb_r\}\)
综上，\(\max(ab) =\max\{a_lb_l,a_lb_r,a_rb_l,a_rb_r\}\)
-
-
定理4：
\[\begin{aligned} \bigcup\limits_{p=k}^{n-1}M_p&=\{a_ib_j\mid k\subseteq i\&j\lor k+1\subseteq i\&j\lor k+2\subseteq i\&j\lor...\lor n\subseteq i\&j\}\\ &=\{a_i b_j\mid\exists x(x\geq k \land x\subseteq i\&j)\} \end{aligned} \]所以对于任意的\(i,j\)有
\[\begin{aligned} a_ib_j\in\bigcup\limits_{p=k}^{n-1}M_p&\iff\exists x(x\geq k \land x\subseteq i\&j)\\ a_ib_j\in C_k&\iff k\leq i\& j \end{aligned} \]-
先证\(\bigcup\limits_{i=k}^nM_i\subseteq C_k\)
因为\(\exists x(x\geq k \land x\subseteq i\&j)\)
不妨设\(a\geq k \land a\subseteq i\&j\)
由定理2可知，\(a\leq i\&j\)
又有\(a\geq k\)，所以\(k\leq i\&j\)
从而有\(\exists x(x\geq k \land x\subseteq i\&j) \implies k\leq i\&j\)
即\(a_ib_j\in\bigcup\limits_{p=k}^{n-1}M_p \implies a_ib_j\in C_k\)
亦即\(\bigcup\limits_{i=k}^nM_i\subseteq C_k\)
-
再证\(C_k\subseteq \bigcup\limits_{i=k}^nM_i\)
因为\(k\leq i\&j\)
又有\(i\&j \subseteq i \& j\)
故存在\(a=i\&j\)，使得\(a\geq k \land a \subseteq i \& j\)
所以\(k\leq i\&j \implies\exists x(x\geq k \land x\subseteq i\&j)\)
即\(a_ib_j\in C_k\implies a_ib_j\in\bigcup\limits_{p=k}^{n-1}M_p\)
亦即\(C_k\subseteq \bigcup\limits_{i=k}^nM_i\)
综上，\(C_k=\bigcup\limits_{i=k}^nM_i\)，证毕。
-
代码：
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long Lint;
const int maxn = (1 << 20) + 10;
const int mod = 998244353;
const int MAX_INT = (int)0x7fffffff;
const int MIN_INT = (int)0x80000000;
const Lint MIN_LINT = (Lint)0x8000000000000000;
int n;
int a[maxn], b[maxn];
int min_a[maxn], max_a[maxn];
int min_b[maxn], max_b[maxn];
Lint res[maxn];
void solve() {
scanf("%d", &n);
int m = 1;
while (m < n) m <<= 1;
for (int i = 0; i < m; i++) {
min_a[i] = min_b[i] = MAX_INT;
max_a[i] = max_b[i] = MIN_INT;
}
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
min_a[i] = max_a[i] = a[i];
}
for (int i = 0; i < n; i++) {
scanf("%d", b + i);
min_b[i] = max_b[i] = b[i];
}
// i|j：把i中j是1的那一位变成1，很显然有i包含于i|j，自然也有i<=i|j
// 所以要计算包含i的最值，得从大到小
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < m; j <<= 1) {
max_a[i] = max(max_a[i], max_a[i | j]);
max_b[i] = max(max_b[i], max_b[i | j]);
min_a[i] = min(min_a[i], min_a[i | j]);
min_b[i] = min(min_b[i], min_b[i | j]);
}
}
// 计算m_k，千万不要在这取模
res[n] = MIN_LINT;
for (int i = n - 1; i >= 0; i--) {
res[i] = MIN_LINT;
res[i] = max(res[i], (Lint)max_a[i] * max_b[i]);
res[i] = max(res[i], (Lint)max_a[i] * min_b[i]);
res[i] = max(res[i], (Lint)min_a[i] * max_b[i]);
res[i] = max(res[i], (Lint)min_a[i] * min_b[i]);
}
// 计算c_k
for (int i = n - 1; i >= 0; i--) {
res[i] = max(res[i], res[i + 1]);
}
// 别忘取模
Lint ans = 0;
for (int i = 0; i < n; i++) {
ans += res[i] % mod;
}
printf("%lld\n", (ans % mod + mod) % mod);
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}