题意:给m个计划,和每天有多少个房间,然后问计划和房间有没有冲突,如果有冲突,最早在第几天发生冲突
题解:

step1线段树区间更新

用每天能提供的教室数,建立线段树,然后对于每个计划进行区间更新,如果区间更新后的区间最小值小于0,结束,否则处理完之后输出0

#include<iostream>
#include<cstdio>
#include<cstring>
#define min(a,b) (a<b?a:b)
const int maxn=1000010;
struct segment{
    int l,r,minn,minus;
}tree[maxn<<2];
int a[maxn],n,m,l,r,s;
void build(int l,int r,int now)
{
    tree[now].l=l,tree[now].r=r;
    if(l==r)
    {
        tree[now].minn=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
    tree[now].minn=min(tree[now<<1].minn,tree[now<<1|1].minn);
}
void update(int now)
{
    tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn-tree[now<<1].minus,tree[now<<1|1].minn-tree[now<<1|1].minus)); 
}
void change(int l,int r,int now,int num)
{
    if(tree[now].l==l&&tree[now].r==r)
    {        
        tree[now].minus+=num;
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(r<=mid) change(l,r,now<<1,num);
    else if(l>mid) change(l,r,now<<1|1,num);
    else change(l,mid,now<<1,num),change(mid+1,r,now<<1|1,num);
    update(now);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s,&l,&r);
        change(l,r,1,s);
        if(tree[1].minn-tree[1].minus<0)
        {
            printf("-1\n%d",i);
            return 0;
        }
    }
    printf("0");
}

step2差分加二分答案

把可能最先不够要求的任务的编号给二分
然后用差分判断是否达标,如果不达标右边界左移,否则相反

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxx=1e6+5;
struct node{
 int d,s,e;
}mp[maxx];
int n,m;
int r[maxx],t[maxx];
int work(int k)
{
    memset(t,0,sizeof(t));
    for(int i=1;i<=k;i++)
    {
        t[mp[i].s]+=mp[i].d;
        t[mp[i].e+1]-=mp[i].d;

    }
    for(int i=1;i<=n;i++)
    {
        t[i]+=t[i-1];
        if(t[i]>r[i]) return 0;

    }
    return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>r[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>mp[i].d>>mp[i].s>>mp[i].e;
    }
    int l=1,r=m;
    while(l<r)
    {
        int mid=l+r>>1;
        if(work(mid))
        {
            l=mid+1;
        }
        else r=mid;
    }
    if(l==m) cout<<0<<endl;
    else cout<<-1<<endl<<l<<endl;

    return 0;
}