题目描述
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提
供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
输入输出格式
输入格式：
第一行包含两个正整数n,m，表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj,sj,tj，表示租借的数量，租借开始、结束分别在
第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
输出格式：
如果所有订单均可满足，则输出只有一行，包含一个整数 0。否则（订单无法完全满足）
输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。
输入输出样例
4 3 2 5 4 3 2 1 3 3 2 4 4 2 4
-1 2
说明
【输入输出样例说明】
第 1 份订单满足后，4 天剩余的教室数分别为 0，3，2，3。第 2 份订单要求第 2 天到
第 4 天每天提供 3 个教室，而第 3 天剩余的教室数为 2，因此无法满足。分配停止，通知第
2 个申请人修改订单。
【数据范围】
对于10%的数据，有1≤ n,m≤ 10；
对于30%的数据，有1≤ n,m≤1000；
对于 70%的数据，有1 ≤ n,m ≤ 10^5；
对于 100%的数据，有1 ≤ n,m ≤ 10^6,0 ≤ ri,dj≤ 10^9,1 ≤ sj≤ tj≤ n。
NOIP 2012 提高组 第二天 第二题
分析
首先想到的是线段树，维护区间最小值（如果区间内最小的都满足了，其他的就也满足），就写了。在洛谷提交，5分，只过了一个点，调试找错误，然而并没有什么卵用。结果：在vijiosAC！！！orz
code
代码？？，，。
1 #include2 #include 3 using namespace std; 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 #define MAXN 1000100 7 8 int a[MAXN]; 9 int mn[MAXN<<2];10 int add[MAXN<<2];11 int n,t,p;12 13 void putup(int rt)14 {15 mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);16 }17 void putdown(int rt)18 {19 if (add[rt])20 {21 add[rt<<1] += add[rt];22 add[rt<<1|1] += add[rt];23 mn[rt<<1] -= add[rt];24 mn[rt<<1|1] -= add[rt];25 add[rt] = 0;26 }27 }28 void build(int l,int r,int rt)29 {30 if (l==r)31 {32 mn[rt] = a[l];33 return ;34 }35 int m = (l+r)>>1;36 build(lson);37 build(rson);38 putup(rt);39 }40 void update(int l,int r,int rt,int L,int R,int c)41 {42 if (L<=l && r<=R)43 {44 add[rt] += c;45 mn[rt] -= c;46 return ;47 }48 putdown(rt);49 int m = (l+r)>>1;50 if (L<=m) update(lson,L,R,c);51 if (R>m) update(rson,L,R,c);52 putup(rt);53 return ;54 }55 int query(int l,int r,int rt,int L,int R)56 {57 if (L<=l && r<=R)58 {59 return mn[rt];60 }61 int ret = 1e8;62 putdown(rt);63 int m = (l+r)>>1;64 if (L<=m) ret = min(ret,query(lson,L,R));65 if (R>m) ret = min(ret,query(rson,L,R));66 return ret;67 }68 int main()69 {70 scanf("%d%d",&n,&t);71 for (int i=1; i<=n; ++i)72 scanf("%d",&a[i]);73 build(1,n,1);74 for (int w,x,y,z,i=1; i<=t; ++i) 75 {76 scanf("%d%d%d",&z,&x,&y);77 w = query(1,n,1,x,y);78 if (w>=z) update(1,n,1,x,y,z);79 else 80 {81 printf("-1\n%d",i);82 return 0;83 }84 }85 printf("0\n");86 return 0;87 }
正解
后来用二分写：枚举1到m个请求中的一个，如果可以，就说明到目前为止，都能满足，不可以到现在不满足，可能在前面的一个请求中已经不满足了，二分再次寻找。判断是会用到查分的思想。
1 #include2 #include 3 const int MAXN = 1000100; 4 int a[MAXN],s[MAXN],t[MAXN],d[MAXN],c[MAXN]; 5 int n,m,ans = 0; 6 bool work(int x) 7 { 8 int sum = 0; 9 memset(c,0,sizeof(c));10 for (int i=1; i<=x; ++i)11 {12 c[s[i]] -= d[i];13 c[t[i]+1] += d[i];14 }15 for (int i=1; i<=n; ++i)16 {17 sum += c[i];18 if (sum+a[i]<0) return false;19 }20 return true;21 }22 int main()23 {24 scanf("%d%d",&n,&m);25 for (int i=1; i<=n; ++i)26 scanf("%d",&a[i]);27 for (int i=1; i<=m; ++i)28 scanf("%d%d%d",&d[i],&s[i],&t[i]);29 int l = 1, r = m;30 while (l<=r)31 {32 int mid = (l+r)>>1;33 if (!work(mid)) 34 {35 r = mid-1;36 ans = mid;37 }38 else l = mid+1;39 }40 if (ans) printf("-1\n%d",ans);41 else printf("0");42 return 0;43 }
补充：
对于线段树代码，后来发现了另一个思路，上面的代码是先判断能否满足，在更新，一个比较奇妙的思路，可以直接更新，维护最小值，如果mn[1]<0则不满足，维护最小值，找第一个小于0的。可能快一点吧。