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

意到输出只有一个数，我们在头脑风暴中尝试二分求这个数。

问题变成求最小的数
�
x 使得
�
�
<

�
a
k
​
<=x。

我们把数组里的数分成

�

x 和
<
=
�
<=x，

�

x 用1表示，
<
=
�
<=x 用0表示，
�
�
<
=
�
a
k
​
<=x 就是替代操作完后
�
�
=
0
a
k
​
=0。

这时会发现，操作
1
1 就不需要排序了，因为操作完
1
1 就被挪到区间的左右两边了，
0
0 在中间，这个可以用区间修改完成，由此，我们就想到了线段树。复杂度
�
(
�
�
�
�
2
�
)
O(nlog
2
n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+9;
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].l==tr[u].r) return;
tr[u].sum=tr[u2].sum+tr[u2+1].sum;
}
void pushdown(ll u){
if(tr[u].ltr[u].r) return;
if(tr[u].tag-1) return;
tr[u2].sum=tr[u].tag*(tr[u2].r-tr[u2].l+1);
tr[u2+1].sum=tr[u].tag(tr[u2+1].r-tr[u2+1].l+1);
tr[u2].tag=tr[u].tag,tr[u2+1].tag=tr[u].tag;
tr[u].tag=-1;
}
void build(ll u,ll l,ll r){
tr[u].l=l,tr[u].r=r,tr[u].tag=-1;
if(lr){tr[u].sum=a[l];return;}
ll mid=(l+r)/2;
build(u2,l,mid);
build(u2+1,mid+1,r);
pushup(u);
}
ll query(ll u,ll l,ll r){
pushdown(u);
if(r<tr[u].l||tr[u].r<l) return 0;
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
return query(u2,l,r)+query(u2+1,l,r);
}
void upd(ll u,ll l,ll r,ll v){
pushdown(u);
if(r<tr[u].l||tr[u].r<l) return;
if(l<=tr[u].l&&tr[u].r<=r){
tr[u].sum=v*(tr[u].r-tr[u].l+1);
tr[u].tag=v;
return;
}
upd(u2,l,r,v);
upd(u2+1,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);
cin>>n>>m>>k;
for(ll i=1;i<=n;i++) cin>>x[i];
for(ll i=1,op,l,r,val;i<=m;i++){
cin>>op;
if(op1) cin>>l>>r,cnt++,op1[cnt]=l,op2[cnt]=r;
else cin>>val,cnt=max(0ll,cnt-val);
}
ll L=0,R=200000,mid,ans=200000;
while(L<=R){
mid=(L+R)/2;
for(ll i=1;i<=n;i++) a[i]=(x[i]>mid);
build(1,1,n);
for(ll i=1;i<=cnt;i++){
ll l=op1[i],r=op2[i],cnt1=query(1,l,r);
upd(1,l,l+(cnt1+1)/2-1,1);
upd(1,r-cnt1/2+1,r,1);
upd(1,l+(cnt1+1)/2,r-cnt1/2,0);
}
if(query(1,k,k)) L=mid+1;
else ans=mid,R=mid-1;
}
cout<<ans<<endl;
return 0;
}