今天很偶然看到了一个挺好的关于差分数组的讲解，之前打比赛也遇到过，只是没有很系统的了解过这个神奇的东西。
讲解博客地址：https://rpdreamer.blog.luogu.org/ci-fen-and-shu-shang-ci-fen
学完之后真的觉得这种思想真的是十分的巧妙，然后就做了一下讲解里的例题。
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6+10; int diff[maxn],need[maxn],d[maxn],sum[maxn],l[maxn],r[maxn],rest[maxn],n,m; bool Check(int mid) { memset(diff,0,sizeof(diff)); for(int i = 1;i <= mid; i++) { diff[l[i]] += d[i]; diff[r[i]+1] -= d[i]; } for(int i = 1;i <= n; i++) { need[i] = need[i - 1] + diff[i]; if(need[i] > rest[i]) return false; } return true; } signed main() { //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1;i <= n; i++) cin >> rest[i]; for(int i = 1;i <= m; i++) cin >> d[i] >> l[i] >> r[i]; int ll = 0,rr = m; if(Check(rr)) cout << 0 << endl; else { while(ll < rr) { int mid = ll + (rr - ll) / 2; if(Check(mid)) ll = mid + 1; else rr = mid; } cout << "-1" << endl << ll << endl; } return 0; }
