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

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

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

B-出租_2023牛客OI赛前集训营-提高组（第二场） (nowcoder.com)

题目大意

在一条路上有 $n$ 个栋楼，每栋楼上有 $k$ 个房间出租。

现在有 $m$ 次询问，每次有两个数字 $x,y$ ，询问区间 $[x,x+d]$ 上是否有 $y$ 个房间空闲。

思路

先思考一下 $NO$ 的情况

如果存在 $[l,r]$ 租户人数的和大于 $k\ast (r-l+1+d)$ ，说明无解

作差得到 ${\sum }_l^r(val-k)>k\ast d$

所以我们只需要用线段树维护最大字段和和 $k\ast 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 () {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 > k * d) puts ("NO");else puts ("YES");}return 0;
}

这篇关于2023牛客OI赛前集训营-提高组（第二场）B.出租的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---