P5874 [IOI2015]horses 马题解

伟大的王夫子 · 2021-02-20 16:50:17 · 题解

线段树题一遍就A了，写偏题解纪念一下

首先，假设ans,mul分别是区间的答案，以及所有X值的乘积

那么容易得出转移方程首先，

\max\limits_{l \le i \le r}{(\prod_{i=l}^r Y_i})\times X_i =\max(\max\limits_{l \le i \le mid}{(\prod_{i=l}^r Y_i})\times X_i,\max\limits_{mid +1\le i \le r}{(\prod_{i=l}^r Y_i})\times X_i)

而\max\limits_{mid \le i \le r}{(\prod_{i=l}^r Y_i})\times X_i) =\max\limits_{mid +1\le i \le r}{(\prod_{i=mid+1}^r Y_i})\times X_i \times \prod_{i=l}^{mid} X_i

那么转移就很好转移了

由于结果过大，而且取了模会影响比大小，所以我们取对数，乘法变为加法。

询问便直接返回根节点的值

这样写法比许多人写的维护一堆值方便的多，而且代码简洁易懂，目前最优解。

总之，这道题说白了就是道线段树模板题，一定要好好掌握

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 5e5 + 5; 
int n, m;
ll X[N], Y[N];

const ll P = 1e9 + 7;
struct {
    int l, r;
    db sum, mx;
    ll mul, ans;
} t[N << 2];
inline void push_up(int p) {
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    t[p].mx = max(t[p << 1].mx, t[p << 1].sum + t[p << 1 | 1].mx);
    t[p].mul = t[p << 1].mul * t[p << 1 | 1].mul % P;
    if (t[p << 1].mx >= t[p << 1].sum + t[p << 1 | 1].mx) 
        t[p].ans = t[p << 1].ans;
    else t[p].ans = t[p << 1 | 1].ans * t[p << 1].mul % P; 
}
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].mx = log(1.0 * X[l] * Y[l]);
        t[p].sum = log(1.0 * X[l]);
        t[p].ans = X[l] % P * Y[l] % P;
        t[p].mul = X[l] % P;
        return; 
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p); 
}
void change(int p, int x) {
    if (t[p].l == t[p].r) {
        t[p].mx = log(1.0 * X[x] * Y[x]);
        t[p].sum = log(1.0 * X[x]);
        t[p].ans = X[x] % P * Y[x] % P;
        t[p].mul = X[x] % P; 
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) change(p << 1, x);
    else change(p << 1 | 1, x);
    push_up(p);
}
main() {
    cin >> n;
    for (register int i = 1; i <= n; ++i) scanf("%lld", X + i);
    for (register int i = 1; i <= n; ++i) scanf("%lld", Y + i);
    build(1, 1, n);
    printf("%lld\n", t[1].ans);
    cin >> m;
    while (m--) {
        int type, pos;
        ll val;
        scanf("%d%d%lld", &type, &pos, &val);
        if (type == 1) X[pos + 1] = val;
        else Y[pos + 1] = val;
        change(1, pos + 1);
        printf("%lld\n", t[1].ans); 
    }
}

P5874 [IOI2015]horses 马 题解

P5874 [IOI2015]horses 马题解