题解 P1083 【借教室】

为啥都是前缀和，差分不是更显而易见么？ 考虑维护各天剩余教室数量，差分后区间减时只用dt[l]-=c, dt[r+1]+=c。 然后从第一天开始累加dt[]，即某一天剩余教室数量，若<0，就从第m个请求开始撤销（区间加），同时--m，此时注意区间与当前天的关系，具体看代码for里面的if。 最终n天扫完，此时m即为满足n天剩余教室均非负的最大请求数，加1即为答案，当然若等于原m需输出0。 由于m单调不增，时空复杂度均为O(n+m) 代码中使用了指针而不是直接--m ```cpp const int N = 1000003; const int M = 1000003; struct Q_{int c,l,r;}ss[M], *sp = ss; int w[N]; ll dt[N]; int main() { int n = i_(), m = i_(); for(int i = 1; i <= n; ++i) dt[i] = (w[i] = i_())-w[i-1]; for(int i = 1; i <= m; ++i) { int c = i_(), l = i_(), r = i_(); *sp++ = (Q_){c, l, r}; dt[l] -= c, dt[r+1] += c; } ll cur = 0; for(int i = 1; i <= n; ++i) for(cur += dt[i]; cur < 0 && --sp; ) if(sp->l > i) dt[sp->l] += sp->c, dt[sp->r+1] -= sp->c; else if(sp->r >= i) cur += sp->c, dt[sp->r+1] -= sp->c; if(sp-ss == m) puts("0"); else printf("-1\n%d\n", (int)(sp-ss)+1); return 0; } ```