义乌中学暑假集训 2021.07.15 B

(Updated: )
oi
, ,

白云建立了 $n$ 个商店，白兔打算按照编号 $1\sim n$ 的顺序访问这些商店。商店 $i$ 有一个价格 $ai$ 表示交易商品所需的代价。

白兔在按顺序走时，每到达一个商店，可以花费代价购买一件商品，并放入自己手中。也可以出售手上的商品，并获得利润。

白兔的力量有限，同一时刻只能携带一个商品。问它遍历完所有商店后能够获得的利润最大是多少？

白兔的精力也有限，所以，在最大化利润的前提下，它想让交易次数尽可能地少。

当然，白云不想让白兔轻松获利，它有时会命令一段区间内的商店把价格同时加上一个数。

$T\leq 5,1\leq n,Q\leq 10^5,c\leq 10^5$。

Sol

第一问十分简单，直接贪心考虑，$\forall i \in [1,n)$，若 $a_i<a_{i+1}$，则在 $i$ 买入，在 $i+1$ 卖出一定是最优的。

第二问考虑线段树，其实就是在第一问差分的基础上，求所有极长非负整数区间且区间和大于 $0$ 的个数。直接线段树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define int long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(int x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e5+10;
int Tt,n,q,a[N];
class SegmentTree{
    private:
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n-1
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x].S=T[x<<1].S+T[x<<11].S,T[x].SS=T[x<<1].SS+T[x<<11].SS-(T[x<<11].pre>0&&T[x<<1].suf>0),T[x].pre=T[x<<1].pre?T[x<<1].pre:T[x<<11].pre,T[x].suf=T[x<<11].suf?T[x<<11].suf:T[x<<1].suf)
    public:
        struct node{int S,SS,pre,suf;}T[N<<2];
        I void B(PT){
            if(l==r) return T[x].pre=T[x].suf=a[l+1]-a[l],T[x].S=max(T[x].pre,0LL),T[x].SS=(T[x].pre>0LL),void();
            B(LT),B(RT),PU(x);
        }
        I void U(CI p,CI v,PT){
            if(l==r) return T[x].pre+=v,T[x].suf+=v,T[x].S=max(T[x].pre,0LL),T[x].SS=(T[x].pre>0LL),void();
            p<=mid?U(p,v,LT):U(p,v,RT),PU(x);
        }
}S;
signed main(){
    RI i,o,x,y,z;read(Tt);W(Tt--){
        for(read(n),read(q),i=1;i<=n;i++) read(a[i]);
        for(S.B(),i=1;i<=q;i++) read(o),o?write(S.T[1].S),pc(' '),write(S.T[1].SS<<1),pc('\n'):(read(x),read(y),read(z),x>1&&(S.U(x-1,z),0),y<n&&(S.U(y,-z),0));
    }return 0;
}