昨天晚上做完4題還有30分鐘，感覺太晚了就沒繼續寫，不過看了下E題感覺是一個線段樹題目，今天中午看了看發現就是一個線段樹上遞歸的詢問問題，不過我之前沒寫過但是靠著日益強大的亂寫能力竟然水出來了~~

E. Greedy Shopping

不難知道操作1并不改變原數組不升序的性質即非嚴格單調遞減的性質永遠存在。

操作一：在線段樹上二分第一個小于y的數的位置pos，然后區間修改即可$[pos\to x]$
操作二：維護一個區間最小值和區間和，然后遞歸亂搞，由于每次能買則買先往左子樹遞歸，然后記錄一下左子樹的花費，再往右子樹遞歸這時候剩余的錢要減去左子樹的花費，全局變量記錄答案。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=400010; ll a[N]; int n,q; struct node {int l,r;ll sum,mn;ll lazy; }tree[N*4]; void pushup(int u) {tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;tree[u].mn=min(tree[u<<1].mn,tree[u<<1|1].mn); } void pushdown(int u) {if(!tree[u].lazy)return;tree[u<<1].sum=(tree[u<<1].r-tree[u<<1].l+1)*tree[u].lazy;tree[u<<1|1].sum=(tree[u<<1|1].r-tree[u<<1|1].l+1)*tree[u].lazy;tree[u<<1].mn=tree[u<<1|1].mn=tree[u].lazy;tree[u<<1].lazy=tree[u<<1|1].lazy=tree[u].lazy;tree[u].lazy=0; } void build(int u,int l,int r) {tree[u]={l,r};if(l==r) {tree[u].sum=tree[u].mn=a[l];return;}int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int l,int r,ll val) {if(tree[u].l>=l&&tree[u].r<=r){tree[u].lazy=tree[u].mn=val;tree[u].sum=(tree[u].r-tree[u].l+1)*val;return;}pushdown(u);int mid=tree[u].l+tree[u].r>>1;if(l<=mid) modify(u<<1,l,r,val);if(r>mid) modify(u<<1|1,l,r,val);pushup(u); } int findmn(int u,ll val) {if(tree[u].l==tree[u].r) return tree[u].l;pushdown(u);if(tree[u<<1].mn>=val) return findmn(u<<1|1,val);else return findmn(u<<1,val); } int ans; int calc(int u,int l,int r,ll now) {if(tree[u].r<l||tree[u].l>r||!now) return 0;if(tree[u].l>=l&&tree[u].r<=r){if(tree[u].sum<=now){ans+=tree[u].r-tree[u].l+1;return tree[u].sum;}}ll w=0;pushdown(u);int mid=tree[u].l+tree[u].r>>1;if(l<=mid&&tree[u<<1].mn<=now) w+=calc(u<<1,l,r,now);if(r>mid) w+=calc(u<<1|1,l,r,now-w);return w; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n+1);while(q--){int op,x,y;cin>>op>>x>>y;if(op==1){int pos=findmn(1,y);if(pos<=x) modify(1,pos,x,y); }else{ans=0;calc(1,x,n,y);cout<<ans<<'\n';}}}return 0; }

此代碼必須在多開一倍空間，要不然calc函數越界？我也不知道為啥很迷
要加喲哦~

總結

以上是生活随笔為你收集整理的codeforces1440 E. Greedy Shopping的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。