P5874 题解

Problem Link

题目大意

你有 $1$ 只马，第 $i$ 年后马的数量会变成原来的 $p_i$ 倍，每年你可以以 $q_i$ 每只的价格售出任意数量的马。

求 $n$ 年后你的最大收益 $\bmod 10^9+7$ 的余数。支持 $m$ 次修改 $p_i/q_i$。

数据范围 $n\le 5\times 10^5,m\le 10^5,p_i,q_i\le 10^9$。

思路分析

记 $V=\max{q_i}\le 10^9$。

注意到一个观察：所有的马都会在同一时刻 $t$ 卖出，此时的 $t$ 最大化 $q_t\prod_{i\le t} p_i$，否则把其他时间卖出的向 $t$ 调整一定会更优。

考虑如何求 $t$ 满足 $q_t\prod_{i\le t}p_i$ 最大，首先考虑 $t=n$ 的情况，对于另一个 $i$ 来说，$t=i$ 时优于 $t=n$ 当且仅当 $q_i>q_n\prod_{j>i}p_j$，因此此时 $\prod_{j>i}p_j<\dfrac{q_i}{q_n}\le V$。

根据一个经典的结论，我们知道此时 $p_{i+1}\sim p_n$ 中 $>1$ 的元素只有 $\mathcal O(\log V)$ 个，因此对应的 $\prod_{i\le t}p_i$ 只有 $\mathcal O(\log V)$ 个。

用 std::set 维护所有非 $1$ 的位置，得到相同前缀积对应的区间，此时我们求出对应区间里 $q_i$ 的最大值即可，用线段树维护此操作。

比较时两个位置的取值注意到 $\prod_{j>i}p_j<V$，因此可以直接用 $\dfrac{q_i}{\prod _{j>i} p_j}$ 比较，求答案的时候算一下乘法逆元即可。

时间复杂度 $\mathcal O(q\log n\log V)$。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+5,MOD=1e9+7,LIM=1e9;
int n,m,p[MAXN],q[MAXN];
class SegmentTree {
    private:
        int tr[MAXN<<2];
        inline int L(int p) { return p<<1; }
        inline int R(int p) { return p<<1|1; }
        inline void pushup(int p) { tr[p]=max(tr[L(p)],tr[R(p)]); }
    public:
        inline void Build(int l=1,int r=n,int p=1) {
            if(l==r) return (void)(tr[p]=q[l]);
            int mid=(l+r)>>1;
            Build(l,mid,L(p)),Build(mid+1,r,R(p));
            pushup(p);
        }
        inline void Modify(int u,int l=1,int r=n,int p=1) {
            if(l==r) return (void)(tr[p]=q[l]);
            int mid=(l+r)>>1;
            if(u<=mid) Modify(u,l,mid,L(p));
            else Modify(u,mid+1,r,R(p));
            pushup(p);
        }
        inline int Query(int ul,int ur,int l=1,int r=n,int p=1) {
            if(ul<=l&&r<=ur) return tr[p];
            int mid=(l+r)>>1;
            if(ur<=mid) return Query(ul,ur,l,mid,L(p));
            if(mid<ul) return Query(ul,ur,mid+1,r,R(p));
            return max(Query(ul,ur,l,mid,L(p)),Query(ul,ur,mid+1,r,R(p)));
        }
}    TQ;
set <int,decltype(greater<int>())> pos;
int P=1;
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?ret*a%p:ret),a=a*a%p,b=b>>1;
    return ret;
}
inline int calc() {
    int prod=1,qres=0,pres=0;
    for(auto it1=pos.begin(),it0=it1++;it1!=pos.end();++it0,++it1) {
        int l=*it1,r=*it0-1;
        int tmp=TQ.Query(l,r);
        if(!pres||pres*tmp>qres*prod) pres=prod,qres=tmp;
        prod=prod*p[l];
        if(prod>=LIM) break;
    }
    return P*ksm(pres)%MOD*qres%MOD;
}
signed main() {
    freopen("horses.in","r",stdin);
    freopen("horses.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) {
        scanf("%lld",&p[i]),P=P*p[i]%MOD;
        if(p[i]>1) pos.insert(i);
    }
    pos.insert(1),pos.insert(n+1);
    for(int i=1;i<=n;++i) scanf("%lld",&q[i]);
    TQ.Build();
    printf("%lld\n",calc());
    scanf("%lld",&m);
    for(int op,i,v;m--;) {
        scanf("%lld%lld%lld",&op,&i,&v),++i;
        if(op==1) {
            P=P*ksm(p[i])%MOD*v%MOD;
            if(i>1&&p[i]>1) pos.erase(i);
            if((p[i]=v)>1) pos.insert(i);
        } else q[i]=v,TQ.Modify(i);
        printf("%lld\n",calc());
    }
    return 0;
}

线段树题一遍就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);
	}
}