借教室

NOIP

首先科普个数据结构，差分序列

举个栗子

    arr = {1, 2, 3, 4};
    s   = {1, 1, 1, 1};

差分序列：s[i] = arr[i] - arr[i-1];

两项之差，相对于前缀和就是

差分序列--(sum)--> 原数组--(sum)--> 前缀和数组

很容易理解，差分序列前k项和即为原数组第k项的值

回忆一下，求前缀和目的是加速求区间和

那么，差分的好处，区间修改的加速

update0(l, r, x){
    for (...){
        arr[i] += x;
    }
}
update1(l, r, x){
    s[l] -= x;
    s[r+1] += x;
}

效率高下立判

好的，基础科普完了，下面说说这题怎么做：

二分答案

题中有m次区间修改，答案便是能修改多少次

二分ans = 修改次数（可以满足订单条数）

举个栗子：

假设执行前x次修改

则执行x次update1(), 每次复杂度为O(1)，时间为x，总复杂度O(m)

随后检查arr[1..n]中是否有负，return true/false

检查：差分序列求第k项只要sum(s[1..k])即可，想到了什么，前缀和

那么检查就变成O(n)的了

最后一次check的复杂度就是O(n)，二分复杂度为log

总复杂度nlogn，完工

提前说，不回炸int，wa了就是写残了