[luogu]P1083：借教室

原题链接

分析

题意： m个订单，n天，第i天可用的教室数量为ri，第j个订单包含三个信息dj,sj,tj分别表示租借教室数量，租借的起讫日期。
要求每一天租出去的教室不得超过可用的教室，订单按照先来后到原则，若订单不合法（要求的教室超过当日的教室），那么该订单无效，要求输出第一个无效的订单。

1.纯暴力
只需要求第一个无效的订单，我们逐个加入订单，加入订单的时候检查是否合法。
遍历订单的时间为O(m)，加入订单的时间为O(n)，总时间复杂度为O(n*m)，显然不行。

2.二分+前缀和优化

枚举所有的订单时间为O(m)，有没有方法可以减少枚举的时间呢？
注意到，当第一个不合法的订单加入区间后，后面的订单不论怎么加入，都是不合法的，也就是说，订单的合法与否具有单调性。
我们二分第一个出问题的订单位置，时间为O(log m)。

如何检查订单是否合法，如果我们一个个订单加入，每个订单加入的时间为O(n^{2)，检查最后区间的时间为T(n)，总时间复杂度为O((n}2+n)log m)，显然不行。

考虑前缀和优化，区间元素的增加和单点查询，我们可以利用前缀和优化。
操作1：区间[x,y]的所有元素都增加n，令a[x]+=n，a[y+1]-=n。
操作2(ask(x))：查询点x的值，查询x的前缀和即可。
正确性很显然，操作1中a[x]+=n影响了从x到数组尾，使所有ask(i),x<=i<=len都增加了n，而a[y+1]-=n可以消除y+1<=i<=len的影响。

第一遍的时候我使用了树状数组进行前缀和，跑了95分。
后来发现根本不需要，区间的值是不需要动态添加的，只需要花O(n)的时间跑一遍预处理即可，用朴素的前缀和效率反而更高。

ps:这件事也告诉我们有些数据结构没有优劣之分，优秀的数据结构也许更平衡（指查询和修改），但是某些朴素的数据结构的偏向性（查询慢，修改快或查询快，修改慢），可能对具体问题更加的方便。所以我们还是要具体问题具体分析。

代码


#include <bits/stdc++.h>
using namespace std;
int read(){
    char c;int num;
    while(c=getchar(),!isdigit(c));num=c-'0';
    while(c=getchar(), isdigit(c)) num=num*10+c-'0';
    return num;
}
struct que{
    int d,s,t;
} q[1000009];
int n=read(),m=read();
int na[1000009],nu[1000009];
bool check(int mid);
int main()
{
    for(int i=1;i<=n;i++)
        nu[i]=read();
    for(int i=1;i<=m;i++){
        q[i].d=read();
        q[i].s=read();
        q[i].t=read();
    }
    int l=0,r=m,mid;
    if(check(m)){
        printf("0
");
        return 0;
    }
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    printf("-1
%d
",r+1);
    return 0;
}
bool check(int mid){
    memset(na,0,sizeof(na));
    for(int i=1;i<=mid;i++){
        na[q[i].s]+=q[i].d;
        na[q[i].t+1]-=q[i].d;
    }
    for(int i=1;i<=n;i++){
        na[i]=na[i-1]+na[i];
        if(na[i]>nu[i])return false;
    }
    return true;
}