题目链接

https://www.luogu.com.cn/problem/P1083

解题思路

第一种方法，也是我用的方法，因为另一种没想到。
线段树，维护区间最小值，比较简单，就是代码冗长
不会戳这里
第二种才是好方法，差分数组+二分
这道题就是我点差分数组才找到的，说来惭愧我并没用差分数组。
将二分请求出错是第几次，
check函数的话，从第一次请求到二分的这次请求循环，用差分数组记录，再循环1 ~ n求和，并比较与房间个数的大小关系，比房间多说明不可行，否则可行。

AC代码

//线段树 维护最小值 区间修改 区间查询
//提醒用scanf，printf否则可能超时
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;

int n,m,d,s,t,ans,j,rm[N];

struct TREE
{
    int l,r,lazy,m;    
}tr[N<<2];


void Build(int i,int l,int r)
{
    tr[i].l=l;
    tr[i].r=r;
    tr[i].lazy=0;
    tr[i].m=INF;
    if(l==r)
    {
        tr[i].m=rm[l];
        return ;
    }
    int mid=l+r>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m);
    return ;
}

void PushDown(int i)
{
    if(tr[i].lazy==0) return ;
    tr[i<<1].lazy+=tr[i].lazy;
    tr[i<<1|1].lazy+=tr[i].lazy;
    tr[i<<1].m-=tr[i].lazy;
    tr[i<<1|1].m-=tr[i].lazy;
    tr[i].lazy=0;
}

void Update(int i,int l,int r,int sub)
{
    if(l<=tr[i].l && tr[i].r<=r)
    {
        tr[i].lazy+=sub;
        tr[i].m-=sub;
        return ;
    }
    PushDown(i);
    if(tr[i<<1].r>=l) Update(i<<1,l,r,sub);
    if(tr[i<<1|1].l<=r) Update(i<<1|1,l,r,sub);
    tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m);
    return ;
}

int Query(int i,int l,int r)
{
    if(l<=tr[i].l && tr[i].r<=r) return tr[i].m;
    if(tr[i].r<l || tr[i].l>r) return INF;
    int res=INF;
    PushDown(i);
    if(tr[i<<1].r>=l) res=min(res,Query(i<<1,l,r));
    if(tr[i<<1|1].l<=r) res=min(res,Query(i<<1|1,l,r));
    tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m);
    return res;
}

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

    for(j=1;j<=m;j++)
    {
        scanf("%d%d%d",&d,&s,&t);
        if(d>Query(1,s,t))//d大于区间最小值 break 
        {
            ans=j;
            break;
        }
        Update(1,s,t,d); //维护区间最小值 
    } 
    if(j>m) puts("0");
    else puts("-1"),printf("%d\n",ans);
    return 0;
}

//差分数组+二分
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int diff[N],rm[N],d[N],l[N],r[N],sum[N];
int n,m;

bool check(int x)
{
    memset(diff,0,sizeof diff);//！
    for(int i=1;i<=x;i++)
    {
        diff[l[i]]+=d[i];
        diff[r[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+diff[i];
        if(sum[i]>rm[i]) return 0;
    }
    return 1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&rm[i]);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&l[i],&r[i]);
    if(check(m)) puts("0");
    else 
    {
        int ll=1,rr=m;
        while(ll<rr)
        {
            int mid=ll+rr>>1;
            if(check(mid)) ll=mid+1;
            else rr=mid;
        }
        puts("-1");printf("%d",ll);
    }
    return 0;
}