1.语文成绩
差分
普及-
洛谷地址：https://www.luogu.com.cn/problem/P2367
思路：
本题被放到了一个二分题单，越看越不对，感觉需要用d[]数组来累计区间改变值。于是发现本题其实是经典差分。注意前缀和差分都需要初始化，然后把d[l]加上对应的值z，这样l后加得的a[]都会加上z，但由于有右区间，遂把d[r+1]处-z，这样就改变了整个区间。
ac代码：
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;const int N = 5e6 + 5;
int a[N],d[N];
int n,p,mn=INT_MAX;signed main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>p;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1]; while(p--){int x,y,z; cin>>x>>y>>z;d[x]+=z; d[y+1]-=z;}for(int i=1;i<=n;i++){a[i]=a[i-1]+d[i];if(mn>a[i]) mn=a[i];}cout<<mn;return 0;
}
2.数列分段 Section II
二分答案+贪心
普及/提高-
洛谷地址：https://www.luogu.com.cn/problem/P1182
思路：
经典二分答案。首先本题做法是猜每段和最大值最小可能能不能是mid，答案在右侧，如果可以，r=mid，不可以，l=mid，也即l是最大的非答案值，r是最小的答案值，check()用贪心实现，每段累加到最大为止。需要注意一开始需要处理初始化l和r范围，特别注意l的值一定要减一，因为是非答案值。
ac代码：
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;const int N = 1e5 + 5;
int a[N];
int n,m,l,r; int check(int x){int sum=0;int cnt=1;for(int i=1;i<=n;i++){int num=a[i];if(sum+num>x){cnt++;sum=num;if(cnt>m) return 0;}else sum+=num;}return cnt<=m;
}signed main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];l=max(l,a[i]);r+=a[i];}l--; while(l+1<r){int mid=(l+r)>>1;if(check(mid)) r=mid;else l=mid;}cout<<r;return 0;
}
3.[NOIP 2012 提高组] 借教室
二分答案+差分
普及/提高-
洛谷地址：https://www.luogu.com.cn/problem/P1083
思路：
超级好题！其实涉及区间用线段树更好奈何本人不会zzz，其实看出了差分没看出二分答案怎么用。本题最关键的是二分答案思路，二分答案可以用于任何可以舍弃一半取值区间的题里，不一定像二分查找一样保证单调性。本题的二分是判断前n单是否能完成，也即答案在左侧，lft表示能完成的最大单，rgt表示不能完成的第一单。
故本题大框架是先check m单是否都能完成，能完成直接输出0，不能的话输出-1，开始二分check不能完成的那一单。check()内部使用差分判定。
此外，需要注意的是本题差分是在check()内部使用！每次都得清空diff[]数组，根据mid单重新算diff[]，这时候check()复杂度在O(m+n)，二分的复杂度是log2m，所以不会超时！然后再把需求数组aa[]算出，再与原数组比较，判定check的结果。
ac代码：
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;const int N = 1e6 + 5;
int a[N],diff[N],d[N],l[N],r[N],aa[N];
int n,m;int check(int x){memset(diff,0,sizeof diff);for(int i=1;i<=x;i++){ //差分 diff[l[i]]+=d[i];diff[r[i]+1]-=d[i];}for(int i=1;i<=n;i++){aa[i]=aa[i-1]+diff[i];if(aa[i]>a[i]) return 0;}return 1;
}signed main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){cin>>d[i]>>l[i]>>r[i];}int lft=0,rgt=m; //答案在左 if(check(m)){cout<<0; return 0;}cout<<-1<<endl;while(lft+1<rgt){int mid=(lft+rgt)>>1;if(check(mid)) lft=mid;else rgt=mid;}cout<<rgt;return 0;
}