【JLOI】01
新年首讲，不是吗？

二分答案！

CCF NOIP 普及组基础知识
接下来我们将用2节课时间来讲一下二分以及二分答案
【引入例题】
给定一个长度为n的序列，保证是从小到大排的。有m次询问，每次询问数组中x第一次出现的位置。如果没有出现x就输出-1
n、m<=100000
【思路】
普通做法
无脑n×m模拟，时间复杂度O(nm)，0分
高级做法
二分答案
首先二分是有局限性的：当且仅当数组有序时才能二分答案
观察到题目中数组从大到小排
可以二分答案
来一个可爱的小图：
【JLOI】01新年首讲-二分答案

有两个指针，名字叫L和R，而它们则代表了答案所在的区间
十分容易理解？对吗？
接着，它们~~生了个小宝宝~~叫MID
而MID等于（L+R）/2 ~~父母各取一半~~
【JLOI】01新年首讲-二分答案
现在我们判断一下MID所在元素是否小于等于x！
如果不合法：对不起，区间缩小，变成左区间！
否则：OK，再接再厉，变成右区间！
代码片：

int l=1,r=n,ans=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]<=x) ans=mid,l=mid+1;
	else r=mid-1; 
}

我们分析一下时间复杂度
n个数（n）
m次询问+二分查找（mlogn）
总时间复杂度：（n+mlogn）
如果m>n怎么办？
若数据规模为：m<=10000000，n<=100000，还行吗？
明显不行
怎么办？
预处理。
离散化每个数字，例如
原数组：1，1，2，3，5，8
离散化的值：1，1，2，3，4，5
没错，离散化的值就是这个序列去重后这个数字的排名
然后对于-1，我们可以用哈希的方式判断，也可以用map来判重，这些都不是重点！
入门结束！
【例题1】数列分段Section II
十分明显：我们可以二分他的答案，然后对MID判断，判断方式可以用贪心
贪心方法：超了就自建一组，没超就归进最后一组
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100001]; 
int l=1,r=0,ans=0;
bool check(int mid)
{
 int sum=1,k=0;
 for(int i=1;i<=n;i++)
 {
  k+=a[i];
  if(k>mid) 
  {
   sum++;
   k=a[i];
  }
 }
 return sum>m;
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]),l=max(l,a[i]),r+=a[i];
 while(l<=r)
 {
  int mid=(l+r)>>1;
  if(check(mid)==1) l=mid+1;
  else r=mid-1;
 }
 printf("%d\n",l);
 return 0;
}

【例题2】P1083 借教室
难题
别怕！
首先你可以二分答案，对与二分出来的MID进行判断
但是…
怎么判断啊！
差…差分？逗我吧，我才不会？！
就是差分
很遗憾，不会差分的请出门！
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct node{
 int st;
 int ed;
 int nd;
}s[N];
int n,m;
int d[N];
int l=1,r;
int ans=-1;
int k[N]; 
bool check(int u){
 memset(k,0,sizeof(k));
 for(int i=0;i<n;i++) k[i]=d[i+1]-d[i];
 for(int i=1;i<=u;i++){
  k[s[i].st-1]-=s[i].nd;
  k[s[i].ed]+=s[i].nd;
 }
 int p=0;
 for(int i=1;i<=n;i++){
  p+=k[i-1];
  if(p<0) return 0;
 }
 return 1;
}
int main(){
 d[0]=0;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++) scanf("%d",&d[i]);
 for(int i=1;i<=m;i++) scanf("%d%d%d",&s[i].nd,&s[i].st,&s[i].ed);
 if(check(m)){
  printf("0\n");
  return 0;
 }
 r=m;
 while(l<=r){
  int mid=(l+r)>>1;
  if(check(mid)) l=mid+1;
  else r=mid-1; 
 }
 printf("-1\n%d\n",l);
 return 0;
}

【二分其他的奇奇怪怪的用处】
这里…我就默认你们都学过最长上升子序列了。

二分优化的最长上升子序列

【普通最长上升子序列】
令f[i]表示到达i的最长上升子序列的长度
f[i]=for(j,1,i-1) if(j合法) max(f[i],f[j]+1)
时间复杂度：O(n^2)
【二分优化的最长上升子序列】
令f[i]为：

长度为i的最长上升子序列的末尾的最小值

则有如下代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],m=0,x;
int main(){    
	a[0]=-1;    
	scanf("%d",&n);    
	for(int i=1;i<=n;i++){        
		scanf("%d",&x);        
		if(x>a[m]) a[++m]=x;        
		else{           
			int l=1,r=m;            
			while(l<=r){                
				int mid=(l+r)/2;                
				if(x>a[mid]) l=mid+1;                
				else r=mid-1;            
			}            
			a[l]=x;        
		}    
	}    
	cout << m << endl;    
	return 0;
}

easy?

二分答案优化插入排序

duang!
思考一下插入排序
你每次去找要差的位置
O(n)的时间复杂度
乘上之前便利的时间复杂度O(n)
O(n^2)
慢死了！
但是！
寻找插入的位置可以用二分答案！
这样寻找就变成了O(logn)的时间复杂度
~~但是你还要移动，所以时间复杂度仍是O(n^2)~~
虽说排序复杂度没有优化，但是还是十分有用滴

二分答案优化分块

事实上分块中找块内比k小的个数可以这样：

预处理：将快内排序
do it！：有序数组二分答案，求出k在快内的排名
return 排名-1；
cool!

最后：二分答案优化dp

【例题：跳房子】
思路：二分答案，对于每个答案用单调队列优化的dp进行判定即可
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
struct node{
 int pos;
 ll value;
};
int n;
ll d;
ll k;
node s[N];
ll sum=0;
ll l=0,r=1000000000005;
ll ans=-1;
ll f[N];
int q[N],h,t;
int p=0;
ll max(ll x,ll y){
 return x>y?x:y;
}
bool check(ll opt){
 ll L=max(1,d-opt);
 ll R=d+opt;
 memset(q,0,sizeof(q));
 memset(f,128,sizeof(f));
 p=0;
 f[0]=0;
 h=1,t=0;//cout<<endl <<L<< endl;
 for(int i=1;i<=n;i++){
  while(p<i&&s[i].pos-s[p].pos>=L){
   while(h<=t&&f[p]>=f[q[t]]) t--;
   q[++t]=p;
   p++;
  }
  while(h<=t&&s[i].pos-s[q[h]].pos>R) h++;
  
  //cout << endl;
  if(h<=t) f[i]=f[q[h]]+s[i].value;
  if(f[i]>k) return 1;
  //cout << f[i] << " ";
 }
 //cout << endl;
 return 0;
}
int main(){
 //freopen("a.in","r",stdin);
 //freopen("a.ans","w",stdout);
 scanf("%d%lld%lld",&n,&d,&k);
 s[0].pos=0,s[0].value=0;
 for(int i=1;i<=n;i++){
  scanf("%d%lld",&s[i].pos,&s[i].value);
  if(s[i].value>0) sum+=s[i].value;
 }
 if(sum<k){
  printf("-1\n");
  return 0;
 }
 while(l<=r){
  ll mid=(l+r)>>1;
  //cout << mid << endl;
  if(check(mid)){
   r=mid-1;
   ans=mid;
  }
  else l=mid+1;
 }
 printf("%lld\n",ans);
 return 0;
}

【JLOI】01新年首讲-二分答案