复盘 SFLSOJ 20260707 coach 原题 CSU1913 一条龙送礼物

意到输出只有一个数我们在头脑风暴中尝试二分求这个数。问题变成求最小的数x 使得ak​x。我们把数组里的数分成x 和xx 用1表示x 用0表示ak​x 就是替代操作完后0ak​0。这时会发现操作11 就不需要排序了因为操作完11 就被挪到区间的左右两边了00 在中间这个可以用区间修改完成由此我们就想到了线段树。复杂度(2)O(nlog2n)。#includebits/stdc.husing namespace std;typedef long long ll;const ll N5e59;ll n,m,k,x[N],a[N],op1[N],op2[N],cnt;struct Node{ll l,r,sum,tag;}tr[N4];void pushup(ll u){if(tr[u].ltr[u].r) return;tr[u].sumtr[u2].sumtr[u21].sum;}void pushdown(ll u){if(tr[u].ltr[u].r) return;if(tr[u].tag-1) return;tr[u2].sumtr[u].tag*(tr[u2].r-tr[u2].l1);tr[u21].sumtr[u].tag(tr[u21].r-tr[u21].l1);tr[u2].tagtr[u].tag,tr[u21].tagtr[u].tag;tr[u].tag-1;}void build(ll u,ll l,ll r){tr[u].ll,tr[u].rr,tr[u].tag-1;if(lr){tr[u].suma[l];return;}ll mid(lr)/2;build(u2,l,mid);build(u21,mid1,r);pushup(u);}ll query(ll u,ll l,ll r){pushdown(u);if(rtr[u].l||tr[u].rl) return 0;if(ltr[u].ltr[u].rr) return tr[u].sum;return query(u2,l,r)query(u21,l,r);}void upd(ll u,ll l,ll r,ll v){pushdown(u);if(rtr[u].l||tr[u].rl) return;if(ltr[u].ltr[u].rr){tr[u].sumv*(tr[u].r-tr[u].l1);tr[u].tagv;return;}upd(u2,l,r,v);upd(u21,l,r,v);pushup(u);}int main(){freopen(“coach.in”,“r”,stdin);freopen(“coach.out”,“w”,stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cinnmk;for(ll i1;in;i) cinx[i];for(ll i1,op,l,r,val;im;i){cinop;if(op1) cinlr,cnt,op1[cnt]l,op2[cnt]r;else cinval,cntmax(0ll,cnt-val);}ll L0,R200000,mid,ans200000;while(LR){mid(LR)/2;for(ll i1;in;i) a[i](x[i]mid);build(1,1,n);for(ll i1;icnt;i){ll lop1[i],rop2[i],cnt1query(1,l,r);upd(1,l,l(cnt11)/2-1,1);upd(1,r-cnt1/21,r,1);upd(1,l(cnt11)/2,r-cnt1/2,0);}if(query(1,k,k)) Lmid1;else ansmid,Rmid-1;}coutansendl;return 0;}