2023牛客OI赛前集训营-提高组（第二场）B.出租
B-出租_2023牛客OI赛前集训营-提高组（第二场） (nowcoder.com)
题目大意
在一条路上有 \(n\) 个栋楼，每栋楼上有 \(k\) 个房间出租。
现在有 \(m\) 次询问，每次有两个数字 \(x , y\) ，询问区间 \([x , x +d]\) 上是否有 \(y\) 个房间空闲。
思路
先思考一下 \(NO\) 的情况
如果存在 \([l , r]\) 租户人数的和大于 \(k * (r - l + 1 + d)\) ，说明无解
作差得到 \(\sum_l^r(val - k) > k *d\)
所以我们只需要用线段树维护最大字段和和 \(k *d\) 比大小就好了
注意： 即便不能满足某组租户也要把它们记录下来。
#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define lp p << 1
#define rp p << 1 | 1
using namespace std;
const int N = 5e5 + 5;
const LL mod = 1e18 + 5;
int n , m , k , d;
struct Tr {
LL ml , mr , mx , v;
} tr[N << 2];
void build (int p , int l , int r) {
if (l == r) tr[p].v = -k;
else {
int mid = l + r >> 1;
build (lp , l , mid);
build (rp , mid + 1 , r);
tr[p].v = tr[lp].v + tr[rp].v;
}
}
void change (int p , int l , int r , int x , LL val) {
if (l == r && l == x) {
tr[p].v += val;
tr[p].ml = tr[p].mr = tr[p].mx = tr[p].v;
}
else {
int mid = l + r >> 1;
if (x <= mid) change (lp , l , mid , x , val);
else change (rp , mid + 1 , r , x , val);
tr[p].v = tr[lp].v + tr[rp].v;
tr[p].ml = max (tr[lp].ml , tr[rp].ml + tr[lp].v);
tr[p].mr = max (tr[rp].mr , tr[lp].mr + tr[rp].v);
tr[p].mx = max (tr[lp].mr + tr[rp].ml , max (tr[lp].mx , tr[rp].mx));
}
}
int main () {
// freopen ("11.in" , "r" , stdin);
// freopen ("111.out" , "w" , stdout);
int x;
LL y;
scanf ("%d%d%d%d" , &n , &m , &k , &d);
build (1 , 1 , n);
fu (i , 1 , m) {
scanf ("%d%lld" , &x , &y);
change (1 , 1 , n , x , y);
if (tr[1].mx > 1ll * k * d) puts ("NO");
else puts ("YES");
}
return 0;
}