义乌中学暑假集训 2021.07.15 B

白云建立了 $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$ 的个数。直接线段树即可。

#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<<1|1,mid+1,r
        #define PU(x) (T[x].S=T[x<<1].S+T[x<<1|1].S,T[x].SS=T[x<<1].SS+T[x<<1|1].SS-(T[x<<1|1].pre>0&&T[x<<1].suf>0),T[x].pre=T[x<<1].pre?T[x<<1].pre:T[x<<1|1].pre,T[x].suf=T[x<<1|1].suf?T[x<<1|1].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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇