2023牛客OI赛前集训营-提高组（第二场）出租

本文主要是介绍2023牛客OI赛前集训营-提高组（第二场）出租，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

你有 $n$ 栋楼，编号为 $1\sim n$ ，每栋楼都有 $k$ 个房间可以出租，一个房间只能住一个人。每个人都有一个喜好位置 $x$ ，表示他想要在 $x\sim x+d$ 这些楼中住下。

现在有 $m$ 次询问，每次询问给出两个数字 $x, y$ ，表示来了 $y$ 个喜好位置为 $x$ 的租户想要租房。如果 $y$ 为负数，则表示离开了 $- y$ 个喜好位置为 $x$ 的租户。保证离开后喜好位置为 $x$ 的租户不为负数。

对于每次询问，输出 $Y ES$ 或 $NO$ 表示你能否染每个租户分配到理想的房间。

你可以随时更换租户的房间，但前提是新房间也要符合租户的喜好。

$1\leq n,m,d\leq 5\times 10^5,0\leq k,y\leq 10^9,1\leq x\leq n-d$

题解

我们考虑什么时候输出 $NO$ 。

当存在一段区间 $[l, r]$ ，使得喜好位置（这里指 $x$ ，不是 $x\sim x+d$ ）在这段区间上的租户的人数大于 $k\times (r-l+1+d)$ 的时候，则无论如何都无法给这些租户安排理想的房间。

设喜好位置为 $i$ 的租户个数为 $v_i$ ，则有上文可得输出 $NO$ 的条件为存在区间 $[l, r]$ 使得 $\sum_{i=l}^r(v_i-k)>k\times d$ 。

设 $w_i$ 表示喜好位置为 $i$ 的租户个数减去 $k$ 之后的值，即 $v_x-k$ ，则输出 $NO$ 的条件为存在区间 $[l, r]$ 使得 $\sum_{i=l}^rw_i>k\times d$

用线段树维护 $w_i$ 的最大子段和，每次操作只需进行单点修改并将 $[1, n]$ 的最大子段和 $k\times d$ 比较大小即可。

时间复杂度为 $O((n+m)\log n)$ 。

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
int n,m,K,d;
long long tr[4000005],wl[4000005],wr[4000005],mx[4000005];
void build(int k,int l,int r){if(l==r){tr[k]=-K;return;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);tr[k]=tr[lc]+tr[rc];
}
void ch(int k,int l,int r,int x,int y){if(l==r&&l==x){tr[k]+=y;wl[k]=wr[k]=max(0ll,tr[k]);return;}int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y);else ch(rc,mid+1,r,x,y);wl[k]=max(wl[lc],tr[lc]+wl[rc]);wr[k]=max(wr[rc],tr[rc]+wr[lc]);mx[k]=max(wr[lc]+wl[rc],max(mx[lc],mx[rc]));tr[k]=tr[lc]+tr[rc];
}
int main()
{scanf("%d%d%d%d",&n,&m,&K,&d);build(1,1,n);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);ch(1,1,n,x,y);if(mx[1]<=1ll*K*d) printf("YES\n");else printf("NO\n");}return 0;
}