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\)和\(\subset\)?为
? 由定义2显然有\(a\subseteq b\iff a\subset b \lor a = b\)?
- 定理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 \land i < n \land j < n\}\)??，则有\(c_k=\max C_k\)??，发现难以处理\(c_k\)。
我们可以先考虑\(M_k=\{a_i b_j\mid k\subseteq i\&j\land i<n\land j<n\}\)
由定理1发现\(M_k=\{a_i b_j\mid k\subseteq i \land k\subseteq j\land i<n\land j<n\}\)??
设\(A_k=\{a_i\mid k\subseteq i\land i<n\}\)，\(B_k=\{b_i\mid k\subseteq i\land i<n\}\)，\(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\land i< n\land j< n\}\)?，\(M_k=\{a_i b_j\mid k\subseteq i\&j\land i< n\land j< n\}\)?，则有\(C_k=\bigcup\limits_{i=k}^{n-1}M_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} N_p=\{a_ib_j\mid k\subset i\&j \land i < n \land j < n\}\P_p=\{a_ib_j\mid k= i\&j \land i < n \land j < n\} \end{aligned} \]由于\(a\subseteq b\iff a\subset b \lor a = b\)?，则\(M_p=N_p\cup P_p\)?，故?
\[\begin{aligned} \bigcup\limits_{p=k}^{n-1}M_p &=\bigcup\limits_{p=k}^{n-1}N_p\cup\bigcup\limits_{p=k}^{n-1}P_p\&=C_k\cup\bigcup\limits_{p=k}^{n-1}N_p\&\supseteq C_k \end{aligned} \]又因为
\[\begin{aligned} k \subseteq i \& j \implies &k \leq i \& j\k+1 \subseteq i \& j \implies &k+1 \leq i \& j\implies k \leq i \& j\k+2 \subseteq i \& j \implies &k+2 \leq i \& j\implies k \leq i \& j\k+3 \subseteq i \& j \implies &k+3 \leq i \& j\implies k \leq i \& j\&...\n-1 \subseteq i \& j \implies &n-1 \leq i \& j\implies k \leq i \& j\\end{aligned} \]所以有
\[\forall p\in[k,n),M_p\subseteq C_k \]从而有
\[\bigcup\limits_{p=k}^{n-1}M_p\subseteq C_k \]综上
\[C_k=\bigcup\limits_{i=k}^{n-1}M_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;
}