为什么$l$要从0开始

我想到一种极端极端情况，n和m都为1，且这一天都不能满足，正确答案应该是-1 1，但若从1开始，则不会进入while循环，直接puts0了，但若从0开始，则会将r变为0，输出-1 0+1

Orz

Orz

这一点太难想了

我想的是因为 可能没有一个订单可以满足，但是我们后面输出的是r+1 所以从0开始

l r最后会指向最大的满足条件的订单数，如果从1开始，那么第一个订单满足或没订单满足都会指向1，需要特判才可解决，为了避免这种麻烦，从零开始

tql

其实从1开始也可以，不进入while循环的话只要加个特判就好了，判断这一天是否满足

二分左端点写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n, m;
int w[N];
int d[N], s[N], t[N];
LL b[N];

bool check(int mid)
{
    for(int i=1;i<=n;i++) b[i]=w[i]-w[i-1]; 
    for (int i = 1; i <= mid; i ++ )//订单
    {
        b[s[i]] -= d[i];
        b[t[i] + 1] += d[i];
    }

    LL s = 0;//相当于a[0] 
    for (int i = 1; i <= n; i ++ )
    {
        s += b[i];//获得前缀和数组  
        if (s <0) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &d[i], &s[i], &t[i]);

    int l = 1, r = m;
    while (l < r)
    {
        int mid = l + r  >> 1;
        if (check(mid)) r= mid;// mid 后面都可以满足，那么就应该在左区间
        else l = mid + 1;// 在 右区间
    }

    if (!check(m)) puts("0");
    else printf("-1\n%d\n", r );

    return 0;
}

这个差分法用的b[N]是不是可以用int而不担心报错呀？(因为我看这个是两个10的9的数相减不是多个10的9相加)，不知道我这样想对不对…

大佬，可不可以把倒数第三行的!check(m)改成r==m呀，我改了一下有一个数据过不了

为啥这里不需要check 中不需要memset

因为check里把b重新赋值了

我感觉这么写和y总的思路是比较像的

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll a[N],l[N],r[N],b[N];
ll d[N];
int n,m;
bool check(int x)
{
    memset(d,0,sizeof d);
    for(int i=1;i<=x;i++)
    {
        d[l[i]]+=b[i];
        d[r[i]+1]-=b[i];
    }
    for(int i=1;i<=n;i++)
    {
        d[i]+=d[i-1];
        if(d[i]>a[i]) return true;
    }
    return false;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i]>>l[i]>>r[i];
    l[m+1]=0,b[m+1]=0,r[m+1]=0;

    int l=1,r=m+1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) 
        {
            r=mid;
        }
        else 
        {
            l=mid+1;
        }
    }
    if(l==m+1) cout<<"0"<<endl;
    else cout<<"-1"<<endl<<l<<endl;

    return 0;
}

为什么和y总一样不写出差分出b数组的过程？新人不明白求指教

b数组储存的是教室借出的天数，不需要差分计算出什么数据，如果你说的是d数组的话，在check数组里面对该数组进行了差分操作。

为什么说每天可用教室单调下降呢？订单结束的时候不是会返还可用教室吗？

每天的教室数量是固定的

不固定吧，这点我也理解不了

是随着订单数量的增加，教室的数量单调下降

感觉不对

应该找到最后一单没有使天数出现负数的订单吧

我看y总也是二分的订单呀

我也开始这么想，应该是把n天看成一个线段，这样的话每次操作线段的一个区间，返还其实就是区间的右端点，随着订单数量增加，线段上每个点的值都是单减的

我的意思是，每天是数量都是一个已知的数字，并不是每天数量相同

懂了，感谢感谢

我好像明白了，每一天的教室数量是固定的，这m份订单共用这些教室，不存在某一份订单的教室到时间后返还给另一个订单使用

也就是说在一个区间里面，可以使用的房间是单调递减的？

用了差分，然后暴力找出订单编号最小的哪个= = 没想明白怎么用二分

哭了 自己想想不出来 看题解秒懂 真的好愧疚

为什么要用memset(b, 0, sizeof b)初始化b[N]为0.我不写这个就不对

可能是脏数据。
如果不写memset（b, 0, sizeof(b)）, 也可以把d数组定义在全局区。全局变量不赋值， 默认为0

谢谢你的回复，但是我本来就是把数组定义为全局变量的情况

因为那个check函数会多次调用，你初始化应该是全局初始的对吧，但是每次check后会对b数组更改，所以每次都要初始一下

y总，为啥在check（）函数里面，我用vector[HTML_REMOVED]v(n+1)来记录差分数组和前缀和是数组越界的，然后我用vector[HTML_REMOVED]v(n+2)就过了，前面数组越界卡了我快一小时都没明白

嗷，我知道了，因为差分数组要+1

是不是说错了，应该找到最后一单没有使天数出现负数的订单吧

不是吧，应该找到第一个超过教室数目的订单编号

为什么最后是输出r+1，而不是r

应该是出循环时l=r，此时他俩的值是满足性质(教室数量满足订单)区间的右边界，但他要求我们输出的是第一个需要修改的订单，就是右边界的下一个。我是这样想的，如果有问题可以订正。

orz

w数组是原数组，b数组是差分数组，那为什么看不到w数组差分成b数组的过程呢？

最后 if (r == m) puts(“0”); 这里用l == m是不是等价的

大佬们，有人知到 什么情况夏mid=l+r+1>>1,什么情况下 ，mid=l+r>>1;. 加一是向上取整，啥情况需要加一呢？？

while(l[HTML_REMOVED]> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}

佬们，为什么 “ if (check(mid)) l = mid;” 这边 “l=mid” , 而不是 “l=mid+1” ?
if (check(mid)) 这段代码不是说明了 1~mid 间的事件都满足教室的要求吗？（包括mid），所以接下来的筛选不应该是从 l=mid+1 开始吗？

最后是输出l+1吧，第一个无法安排的订单

有不满足的订单的情况下，输出为什么是r+1笔订单？

N 为啥等于 1000010呀，题上不是没说吗

数据范围那里说了呀

w[]数组存的r上限不是1e9吗，为什么不开LL？

int类型的最大好像是2e9+哦，不会爆掉的

对哦，我傻了😂

有个地方不太懂啊，为什么y总写的差分数组不需要初始化，类似b[i] = a[i] - a[i - 1],直接对区间操作就可以了？

这样每次二分完都要将b[i]改回a[i] - a[i-1] ，

全部置0也是初始化 只不过是一个新数组的初始化 这个数组的含义是在处理mid个订单的情况下 每天的教室使用情况
你说的那种是对全部教室的情况的 数组进行操作 但其实不是对这个数组进行操作 而是新开了个数组与这个数组比较

有大佬知道为什么l要从0开始吗

二分的是能被满足的订单编号，订单有可能一个都不被满足。
比如说每天只有3间教室，然后每个订单都要借9999999间教室，那么这些订单都不能被满足。

个人对于“为什么每天可用教室单调下降？订单结束的时候不是会返还可用教室吗？”的一些理解，有不对之处麻烦大佬们指正：

举个栗子，第1个，第2个订单分别在2.29的8点整，8点01被处理。其中，第1个订单想霸占3.1 - 3.3 里每一天的所有教室。而第2个订单也想霸占3.1 - 3.3 里每一天的所有教室。那么不可能说，第2个订单就不处理了，它必须乖乖等到3.3结束，第1个订单把所有教室返回后再处理。因为第2个订单早就在2.29的8点01就处理了。一旦处理了，就得减教室

总结就是：上个订单和下个订单虽然有先后顺序，但相比等待其他订单返还教室的时间，它们的处理间隔太短了，短到可以看成是同时在处理。这也就是教室数量单调下降的可能解释

这题和返回教室没有关系，因为教室数量是固定的，不存在到日期返回教室的情况，每天无论如何都是固定那么多教室，所以你一旦借出教室，那么教室数量就会减少，并且不存在返回教室的情况，所以只要借教室一定是单调下降