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

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

• 2023牛客OI赛前集训营-提高组（第二场）B.出租
  • 题目大意
  • 思路

题目大意

在一条路上有 \(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;
}