二分详解

二分详解

Part 1 例题

T1. Group

Description

给定 n n n个数，询问最少需要改变多少个数才能使得这 n n n个数的方差不超过 m m m。

Solution

本题是典型的暴力启发正解的好题，这里一步步进行讲解。

算法1: 贪心+暴力枚举

我们枚举每个数是否被改变；贪心地，这些数都被改变为一个值，使得这些数对答案均没有贡献。

所以，我们只需要将那些未被改变的数求出方差即可。时间复杂度 O ( 2 n n ) O(2^nn) O(2nn)。

算法2: 贪心

可以发现，在排序后，我们保留的数一定是一段连续的区间。

为什么呢？因为，对于一个连续的区间 [ l , r ] [l,r] [l,r]，现在使这个区间不再连续， [ l , r ] [l,r] [l,r]变为 [ l , r − 1 ] , r + k ( 0 ＜ k ≤ n − r ) [l,r-1], r+k(0＜k≤n-r) [l,r−1],r+k(0＜k≤n−r)，此时可以发现，后者的方差一定比前者的方差大。

于是，我们先将整个序列排序，枚举我们留的数的个数，然后扫一遍所有区间暴力求方差即可。

时间复杂度 O ( n 3 ) O(n^3) O(n3)。

算法3: 贪心+数学+前缀和

考虑如何快速查询一个区间的方差。

这是一个套路

首先，一个区间的平均数就是该区间的和除以该区间的长度，前者可以用前缀和 O ( 1 ) O(1) O(1)查询，后者就是 ( r − l + 1 ) (r-l+1) (r−l+1)。

已知平均数为 a v e r aver aver，那么方差就是

∑ i = l r ( a v e r − a i ) 2 sum_{i=l}^r (aver-a_i)^2 ∑i=lr​(aver−ai​)2

= ∑ i = l r a v e r 2 − 2 a v e r a i + a i 2 =sum_{i=l}^r aver^2-2 aver a_i+a_i^2 =∑i=lr​aver2−2 aver ai​+ai2​

= ∑ i = l r a i 2 − 2 ∑ i = l r a i a v e r + ( r − l + 1 ) a v e r 2 =sum_{i=l}^r a_i^2-2 sum_{i=l}^r a_i aver + (r-l+1)aver^2 =∑i=lr​ai2​−2∑i=lr​ai​ aver+(r−l+1)aver2

于是，我们预处理一个关于平方和的前缀和，第一项 ∑ i = l r sum_{i=l}^r ∑i=lr​即可 O ( 1 ) O(1) O(1)查询；第二项用普通前缀和，第三项直接计算即可。

此时，方差可以 O ( 1 ) O(1) O(1)求出。时间复杂度 O ( n 2 ) O(n^2) O(n2)。

算法4: 二分+贪心+数学+前缀和

回顾一下，我们目前的算法是：

枚举我们留下的数的个数，每次判断这种个数是否可行。 color {red} text{枚举我们留下的数的个数，每次判断这种个数是否可行。} 枚举我们留下的数的个数，每次判断这种个数是否可行。

是否可行在一些情况中是有单调性的，那我们这里有没有呢？

显然是有的。如果留下 3 3 3个数可行，那么留下 10 10 10个数也可行；如果留下 8 8 8个数可行，留下 5 5 5个数不一定可行。

所以，我们直接二分，每次 O ( n ) O(n) O(n)判断当前这个 m i d mid mid是否可行即可。时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)。

---

至此，本题全部完结。我们总结一下二分的套路:

二分仅仅是一种手段，我们要想到二分，就要发现问题的单调性；而我们二分往往优化的是外层的枚举，前提是内层有单调性。

T2: Best Cow Fences

LOJ10112

本题与 T 1 T1 T1类似，大家应该都能切掉吧~~~

T3: [TJOI2016]排序

Description

给定一个 1 − n 1-n 1−n的排列，要求支持区间排序(升序或降序)，最终询问数列中第 k k k的位置的值。

Solution

不可做

本题与上一题的区别是: 我们这题，刚开始不想二分，似乎无处下手。

此时，我们想到了二分。但是，我们能二分什么呢？似乎只能二分本题的答案QAQ

假设目前二分的答案为 m i d mid mid，那么我们就是要判断，第 k k k个位置上的数经过这些操作后与 m i d mid mid的大小关系。

此时，为了让上述的二分起到简化问题的作用，我们把序列中的所有数表达为 0 0 0或 1 1 1，若 a i < m i d a_i<mid ai​<mid则 a i a_i ai​就表示为 0 0 0，否则表示为 1 1 1；可以发现，最终第 k k k个位置上的数表示了 a k a_k ak​与 m i d mid mid的大小关系。

现在，序列中所有的数都变成 0 0 0或 1 1 1了，我们能怎么办呢？

考虑一次升序排序，我们相当于把 0 0 0归到了左边， 1 1 1归到了右边；更详细地说，假设 0 0 0有 x x x个，那么 [ l , l + x − 1 ] [l,l+x-1] [l,l+x−1]都变成了 0 0 0， [ l + x , r ] [l+x,r] [l+x,r]都变成了 1 1 1。

可以发现，我们查询区间 0 0 0的个数，即 x x x的值相当于区间查询，区间修改为 0 0 0或 1 1 1相当于区间摊平，显然可以用线段树来维护。

于是，时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。

本题，我们通过二分，把原来的排序变为了对 0 , 1 0,1 0,1排序，大大地简化了问题，使可爱的线段树有了用武之地。所以，有的时候，二分不仅是一种手段，也是一种重要的算法。

T4: Odd-Even Subsequence

CF1370D

本题与 T 3 T3 T3做法基本相同，大家都能切掉吧~~~

T5: [ABC155D]Pairs

Description

给定 n n n个数，我们可以做一次这样的操作：任意选择两个不在同一位置的数并求出它们的乘积。求出得到的第 k k k大的乘积是什么。

n ≤ 1 0 5 , k ≤ n ( n − 1 ) 2 n≤10^5, k≤frac {n(n-1)} 2 n≤105,k≤2n(n−1)​

Solution

乍看一眼，毫无思路。

于是，我们考虑简化模型，使用二分。本题的答案有单调性——即，如果一个乘积 p p p是排在第 t t t位的，且 t ＜ k t＜k t＜k，那么答案一定小于 p p p，因为 p p p的排名偏高；否则，答案一定不小于 p p p，因为 p p p的排名偏低。

于是，我们直接二分这个乘积 p p p。现在的难点在于，我们如何对于每一个 p p p，求出它的排名。

可以发现，求出 p p p的排名可以使用双指针做法。我们先将整个序列进行排序，然后对于每一个 p p p，我们扫一遍整个序列，记当前扫到的位置为 i i i，记 j j j为使得 a i a j ≤ t a_ia_j≤t ai​aj​≤t的最大的 j j j。由于该序列是升序的，所以在 i i i的增加过程中， j j j是单调下降的，单次 c h e c k check check的时间复杂度为 O ( n ) O(n) O(n)。

故总时间复杂度为 O ( log ⁡ 1 0 18 n ) O(log{10^{18}}n) O(log1018n)。

对于类似这种排名的题目，我们同样可以找到它的单调性，然后 c h e c k check check函数往往就会简化很多，可以用简单的双指针进行维护。

T6: P6733 间歇泉

与这题类似，大家可以切掉的哦~~~

Part 2 代码

T1: Group

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;int n,l,r,ans;
double m,a[200005],pre[200005]={0},sqf[200005];int cmp(int a,int b)
{return a<b;
}int check(int len)
{for (int i=1;i<=n-len+1;i++){int l=i,r=i+len-1;double sumv=pre[r]-pre[l-1];double sq_sumv=sqf[r]-sqf[l-1];double aver=sumv*1.0/len;double now=sq_sumv-2*aver*sumv+aver*aver*len;if (now<=m)  return true;}return false;
}int binary_search(int l,int r)
{if (r==l+1)  return l;int mid=(l+r)/2;if (check(mid))  return binary_search(mid,r);else return binary_search(l,mid);
}signed main()
{cin>>n>>m;for (int i=1;i<=n;i++)  cin>>a[i];sort(a+1,a+n+1,cmp);for (int i=1ll;i<=n;i++){pre[i]=1ll*pre[i-1]+1ll*a[i];sqf[i]=1ll*sqf[i-1]+1ll*a[i]*a[i];}if (check(n)){cout<<0<<endl;return 0;} cout<<n-binary_search(1,n)<<endl;return 0;
}

T3. 排序

#include <bits/stdc++.h>
#define rg register
using namespace std;
const int maxlen=100000;int n,m,k;
int a[maxlen+5],tmp[maxlen+5],tree[8*maxlen+5],tag[8*maxlen+5];struct node
{int opt;int l,r;
}q[maxlen+5];inline void pushup(int rt)
{tree[rt]=tree[2*rt]+tree[2*rt+1];
}inline void build_tree(int l,int r,int rt)
{if (l==r){tree[rt]=a[l];return;}int mid=(l+r)>>1;build_tree(l,mid,2*rt);build_tree(mid+1,r,2*rt+1);pushup(rt);
}inline void f(int rt,int l,int r,int k)
{tree[rt]=(r-l+1)*k;tag[rt]=k;
}inline void pushdown(int rt,int l,int r)
{int mid=(l+r)>>1;if (tag[rt]!=-1){f(2*rt,l,mid,tag[rt]);f(2*rt+1,mid+1,r,tag[rt]);tag[rt]=-1;}
}inline void change(int nl,int nr,int l,int r,int rt,int k)
{if (nl>nr)  return;if (nl<=l&&r<=nr){f(rt,l,r,k);return;}pushdown(rt,l,r);int mid=(l+r)>>1;if (nl<=mid)  change(nl,nr,l,mid,2*rt,k);if (nr>mid)  change(nl,nr,mid+1,r,2*rt+1,k);pushup(rt);
}inline int query(int nl,int nr,int l,int r,int rt)
{if (nl>nr)  return 0;pushdown(rt,l,r);if (nl<=l&&r<=nr)  return tree[rt];int mid=(l+r)>>1,tot=0;if (nl<=mid)  tot+=query(nl,nr,l,mid,2*rt);if (nr>mid)  tot+=query(nl,nr,mid+1,r,2*rt+1);return tot;
}inline bool check(int num)
{for (int i=1;i<=n;i++){if (tmp[i]>=num)  a[i]=1;else a[i]=0;}for (int i=1;i<=4*n;i++)  tag[i]=-1;build_tree(1,n,1);for (int i=1;i<=m;i++){int now=query(q[i].l,q[i].r,1,n,1);if (q[i].opt==0){change(q[i].l,q[i].r-now,1,n,1,0);change(q[i].r-now+1,q[i].r,1,n,1,1);}else{change(q[i].l,q[i].l+now-1,1,n,1,1);change(q[i].l+now,q[i].r,1,n,1,0);}}return query(k,k,1,n,1);
}int Binary_search(int l,int r)
{if (r-l<=1){if (l==r)  return l;else{if (check(r))  return r;else return l;}}int mid=(l+r)>>1;if (check(mid))  return Binary_search(mid,r);else return Binary_search(l,mid);
}signed main()
{cin>>n>>m;for (int i=1;i<=n;i++)  cin>>tmp[i];for (int i=1;i<=m;i++)  cin>>q[i].opt>>q[i].l>>q[i].r;cin>>k;cout<<Binary_search(1,n)<<endl;return 0;
}

撒花✿✿ヽ(°▽°)ノ✿撒花