HDU6971. I love max and multiply题解

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：

  1. 若\(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\)?

  2. 若\(0\leq b_l\leq b_r,a_r\geq 0\)，同1，\(\max(ab) = a_r b_r\)

  3. 若\(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\)?

  4. 若\(b_l\leq b_r\leq 0,a_l\leq 0\)，同3，\(\max(ab) = a_l b_l\)

  5. 若\(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\)

  6. 若\(b_l \leq b_r\leq 0,0\leq a_l\leq a_r\)?，同5，\(\max(ab) = a_l b_r\)

  7. 若\(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;
}

HDU6971. I love max and multiply题解

原文：https://www.cnblogs.com/Bamboo-Wind/p/15059655.html