二分&倍增

二分搜索

整数二分

• 后继

      while(left<right){
          int mid=(left+right)>>1;
          if(arr[mid]>=target)right=mid;
          else left=mid+1;
      }
      return left;
      ```
  
  - 前继
  ```cpp
      while(left<right){
          int mid=(left+right+1)>>1;
          if(arr[mid]<=target)left=mid;
          else right=mid-1;
      }
      return right;
      ```
  - 两种模式会使用不同的中位数，注意正负数除法靠拢方向存在差异，可以使用>>或left+（right-left）/2避免（均向下取整）
  
  ### 实数二分
  
  ```c++
    while(right-left>1e-7){
        double mid=left+(right-left)/2;
        if(check(mid))right=mid;
        else left=mid;
    }
    ```
    - 可以通过while来直接控制精度，也可以通过for来控制循环次数来间接控制精度
  - [P1419 寻找段落](https://www.luogu.com.cn/problem/P1419)
  
  ### 获取最大最小值
  
  - 把求解最大&最小值的问题转化为二分判断合法性，从而找到满足条件的最大&最小值。
  #### 例题
  - [1760. 袋子里最少数目的球](https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/)
  
  - [1231. 分享巧克力](https://leetcode.cn/problems/divide-chocolate/)
  
  - [6290. 最大化城市的最小供电站数目](https://leetcode.cn/problems/maximize-the-minimum-powered-city/)
  
    - 合法性判断较为困难（使用滑动窗口）
  
    - ```c++
      class Solution {
      public:
          long long maxPower(vector<int>& stations, int R, int K) {
              int n = stations.size();
  
              auto check = [&](long long LIM) {
                  vector<long long> vec;
                  for (int x : stations) vec.push_back(x);
  
                  // 初始化滑动窗口的和
                  long long sm = 0;
                  for (int i = 0; i <= R && i < n; i++) sm += vec[i];
  
                  // 表示还有几个供电站可以新建
                  long long rem = K;
                  // 从左到右计算每个城市的电量，同时维护滑动窗口 [l, r]
                  for (int i = 0, l = 0, r = R; ; i++) {
                      if (sm < LIM) {
                          // 当前城市电量不足
                          long long delta = LIM - sm;
                          // 新供电站不够，返回 false
                          if (delta > rem) return false;
                          // 新供电站足够，建在滑动窗口最右边
                          rem -= delta;
                          vec[r] += delta;
                          sm += delta;
                      }
                      if (i == n - 1) break;
  
                      // 滑动窗口向前移动一个城市
                      if (i >= R) sm -= vec[l], l++;
                      if (r != n - 1) sm += vec[r + 1], r++;
                  }
                  return true;
              };
  
              // 二分答案
              long long head = 0, tail = 2e10;
              while (head < tail) {
                  long long mid = (head + tail + 1) >> 1;
                  if (check(mid)) head = mid;
                  else tail = mid - 1;
              }
              return head;
          }
      };
      ```
  ### 例题
  - [154. 寻找旋转排序数组中的最小值 II](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/)
      - 两边相同时移动一边就可以，既可以缩小范围又不会损失最大值
  - [1901. 寻找峰值 II](https://leetcode.cn/problems/find-a-peak-element-ii/)
      - 二维转化为一维，难想：每一行的最大值有可能是峰值，对每一行的最大值做一维寻找峰值即可
  - [287. 寻找重复数 ](https://leetcode.cn/problems/find-the-duplicate-number/)
  - [4. 寻找两个正序数组的中位数 ](https://leetcode.cn/problems/median-of-two-sorted-arrays/)
      - log(m+n)时间内获取第k大的元素
      - 二分思想，很难
  - [378. 有序矩阵中第 K 小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/)
      - 特殊，矩阵中的二分
  - [面试题 10.03. 搜索旋转数组](https://leetcode.cn/problems/search-rotate-array-lcci/description/?company_slug=baidu)
  - [P1868 饥饿的奶牛 ](https://www.luogu.com.cn/problem/P1868)
      - 二分优化区间dp
  
  ### 0/1分数规划
  
  -  <img src="https://thdlrt.oss-cn-beijing.aliyuncs.com/image-20230915223802946.png" alt="image-20230915223802946" style="zoom:33%;" />
  - 猜一个数$x$使得$\max{\frac{\sum_{i=1}^na_is_i}{\sum_{i=1}^nb_is_i}}>=x$即$f=\sum_{i=1}^n(a_i-xb_i)s_i>=0$
  - 取$f=a_i-xb_i$，$k=1$时$max\frac{a_i}{b_i}$就是要找的最大值$x$
    - ​   <img src="https://thdlrt.oss-cn-beijing.aliyuncs.com/image-20230915224626375.png" alt="image-20230915224626375" style="zoom: 33%;" />
  
  - 猜测结果M的值，如过偏左则f<0偏右则f>0
  
    - 需要先对所有直线进行排序
  
  - 复杂度约为$nlogn$（瓶颈在直线的排序）
  
  - ```c++
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    struct Pair{ int a, b;  double y;} p[1005];
    bool cmp(Pair a, Pair b){ return a.y > b.y; }
    int n, k;
    bool check(double x) {
        for(int i=0; i<n; i++)   p[i].y = p[i].a * 1.0 - x * p[i].b;  //计算y=a-xb
        sort(p, p + n, cmp);                       //按y值排序，非常重要(对于每一个x都要重新排序，因为函数的大小关系不是固定的)
        double f = 0;
        for (int i=0; i<k; i++)  f += p[i].y;      //对前k个直线的y值求和
        return f < 0;                              // f < 0：竖线在M的右侧
    }
    int main() {
        while (scanf("%d%d", &n, &k) == 2 && n + k) {
            k = n - k;               //改为选出k对
            for (int i = 0; i < n; i++)  scanf("%d", &p[i].a);
            for (int i = 0; i < n; i++)  scanf("%d", &p[i].b);
            double L = 0, R = 0;
            for (int i = 0; i < n; i++)  R += p[i].a;  //R的初值
            for (int i = 0; i < 50; i++) {       //二分50次，本题足够了（决定精度）
                double mid = L+(R-L)/2;
                if (check(mid))   R = mid;        //竖线在M的右侧，需要左移
                else              L = mid;        //竖线在M的左侧，需要右移
            }
            printf("%d\n", (int)(100 * (L + 0.005)));  //四舍五入
        }
        return 0;
    }
  
    ```
  
  #### 应用
  
  - 与01背包结合为最优比例背包
  
    - [P4377 Talent Show G ](https://www.luogu.com.cn/problem/P4377)
  
      - 不再直接排序而是通过01背包规划进行选择
  
      - ```c++
        #include<bits/stdc++.h>
        using namespace std;
        const int INF=0x3f3f3f3f,N=255,WW=1005;
        int n,W;
        struct{int w, t; double y;}cow[N];
        double  dp[WW]; //dp[i],背包容量为i时最大的价值(y值之和)
        bool check(double x){         // 0/1背包
          int i,j;
          for(i=1;i<=n;i++) cow[i].y=(double)cow[i].t-x*cow[i].w;
          for(i=1;i<=W;i++) dp[i]=-INF; //初始化为负无穷小
          dp[0] = 0;               //背包容量为0时价值为0
          for(i=1;i<=n;i++)
              for(j=W;j>=0;j--){   // 滚动数组，比较特殊的背包，大于等于W都放在这一项，转移比较特殊
                  if(j+cow[i].w>=W)  dp[W]=max(dp[W],dp[j]+cow[i].y); //大于W时按W算
                 else               dp[j+cow[i].w]=max(dp[j+cow[i].w],dp[j]+cow[i].y);
              }
          return dp[W]<0;          // dp[W] < 0，x大了；= dp[W] ≥ 0，x小了
        }
        int main(){
        cin>>n>>W;
        for(int i=1;i<=n;i++)   cin>>cow[i].w>>cow[i].t;
            double L=0,R=0;
            for (int i = 1; i <= n; i++)  R += cow[i].t;  //R的初值
        for(int i=0;i<50;i++){
        double mid = L+(R-L)/2;
        if(check(mid))    R = mid;  //缩小
        else          L = mid;  //放大
        }
        cout<<(int)(L*1000)<<endl;
        return 0;
        }
        ```
  
  - 最优比率生成树
  
  - 最有比率环
  
  - 最大密度子图（网络流）
  
  ## 三分搜索
  
  ### 实数三分
  
  - 可以用于寻找函数的极值，两个点将函数分成三段，通过比较两的点的大小实现每次舍去1/3的区域
  
  - 三等分法
  
    - 取区间lr的三等分点mid1、mid2
  
    - 较慢log~3~n
  
    - ```c++
      while(R-L > eps){        //用for也行
              double k =(R-L)/3.0;
              double mid1 = L+k, mid2 = R-k;
              if(f(mid1) > f(mid2))  R = mid2;
              else   L = mid1;
          }
      ```
  
  ### 整数三分
  
  - ```c++
    while(right-left>2){
        int mid1=left+(right-left)/3;
        int mid2=right-(right-left)/3;
        if(check(mid1)>check(mid2))//具体移动与凹凸性相关
            right=mid2;
        else
            left=mid1;
    }
    ```
  
  - l-r**这几个数**都可能是最大值，要枚举计算
  
    - 即由于while条件为`right-left`因此最终得到的为一个区间，还需要在区间中选取到最终结果
  
  
  ### 例题
  
  - [P1883 函数](https://www.luogu.com.cn/problem/solution/P1883)
  - [P3745 期末考试 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P3745)
  
  ```c++
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int N = 100005;
  int n,m,t[N],b[N];
  ll A,B,C,ans;
  ll calc1(int p){
      ll x=0,y=0;
      for(int i=1;i<=m;i++){
          if(b[i]<p) x+=p-b[i];
          else y+=b[i]-p;
      }
      if(A<B)return min(x,y)*A+(y-min(x,y))*B;
      else return y*B;
  }
  ll calc2(int p){
      ll sum=0;
      for(int i=1;i<=n;i++){
          if(t[i]<p) sum+=(p-t[i])*C;
      }
      return sum;
  }
  int main()
  {
      cin>>A>>B>>C>>n>>m;
      for(int i=1;i<=n;i++) cin>>t[i];
      for(int i=1;i<=m;i++) cin>>b[i];
      sort(t+1,t+n+1);
      sort(b+1,b+m+1);
      ans=1e19;
      int l=1,r=N;
      while(r-l>2){
          int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
          if(calc1(mid1)+calc2(mid1)<=calc1(mid2)+calc2(mid2)) r=mid2;
          else l=mid1;
      }
      for(int i=l;i<=r;i++) ans=min(ans,calc1(i)+calc2(i));
      cout<<ans<<endl;
      return 0;
  }
  

倍增

• 将数字以二进制按位拆分，预处理后实现对任意大小的快速计算，类似快速幂的思想
• 即计算1,2,4...2^k作为“跳板”
• 常用递归式
• \(f[x][i]=f[f[x][i-1]][i-1]\)

快速幂

• c++ inline long long ksm(long long x,long long p) { long long res=1; for(;p;p>>=1,x=x*x%mod) if(p&1)res=res*x%mod; return res; }

后缀数组

• 字符串的所有后缀经过排序后得到的数组
• 

• 

• 

• ```c++ / Problem: JZOJ1598(询问一个字符串中有多少至少出现两次的子串) Content: SA's Code and Explanation Author : YxuanwKeith /

#include #include #include

using namespace std;

const int MAXN = 100005;

char ch[MAXN], All[MAXN]; int SA[MAXN], rank[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m; char str[MAXN]; //rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP //tax[i] 计数排序辅助数组; tp[i] rank的辅助数组(计数排序中的第二关键字),与SA意义一样。 //a为原串 void RSort() { //rank第一关键字,tp第二关键字。 for (int i = 0; i <= m; i ++) tax[i] = 0; for (int i = 1; i <= n; i ++) tax[rank[tp[i]]] ++; for (int i = 1; i <= m; i ++) tax[i] += tax[i-1]; for (int i = n; i >= 1; i --) SA[tax[rank[tp[i]]] --] = tp[i]; //确保满足第一关键字的同时，再满足第二关键字的要求 } //计数排序,把新的二元组排序。

int cmp(int *f, int x, int y, int w) { return f[x] == f[y] && f[x + w] == f[y + w]; } //通过二元组两个下标的比较，确定两个子串是否相同

void Suffix() { //SA for (int i = 1; i <= n; i ++) rank[i] = a[i], tp[i] = i; m = 127 ,RSort(); //一开始是以单个字符为单位，所以(m = 127)

  for (int w = 1, p = 1, i; p < n; w += w, m = p) { //把子串长度翻倍,更新rank

      //w 当前一个子串的长度; m 当前离散后的排名种类数
      //当前的tp(第二关键字)可直接由上一次的SA的得到
      for (p = 0, i = n - w + 1; i <= n; i ++) tp[++ p] = i; //长度越界,第二关键字为0
      for (i = 1; i <= n; i ++) if (SA[i] > w) tp[++ p] = SA[i] - w;

      //更新SA值,并用tp暂时存下上一轮的rank(用于cmp比较)
      RSort(), swap(rank, tp), rank[SA[1]] = p = 1;

      //用已经完成的SA来更新与它互逆的rank,并离散rank
      for (i = 2; i <= n; i ++) rank[SA[i]] = cmp(tp, SA[i], SA[i - 1], w) ? p : ++ p;
  }
  //离散：把相等的字符串的rank设为相同。
  //LCP
  int j, k = 0;
  for(int i = 1; i <= n; Height[rank[i ++]] = k) 
      for( k = k ? k - 1 : k, j = SA[rank[i] - 1]; a[i + k] == a[j + k]; ++ k);
  //这个知道原理后就比较好理解程序

}

void Init() { scanf("%s", str); n = strlen(str); for (int i = 0; i < n; i ++) a[i + 1] = str[i]; }

int main() { Init(); Suffix();

  int ans = Height[2];
  for (int i = 3; i <= n; i ++) ans += max(Height[i] - Height[i - 1], 0);
  printf("%d\n", ans);

} ```

• 五分钟搞懂后缀数组！后缀数组解析以及应用

应用

• 最大重复子串（就是height数组最大值）

ST算法

• 查询静态数组内区间的最值

• \(O(nlogn)\)时间预处理，\(O(1)\)时间完成查询

• 划分为长度为1 2 4 ...的区间，预处理最值

• dp[s][k]表示左端点为s区间长度为2^k的区间内的最值

• 维护最大最小值

  void st_init(){       
       for(int i=1;i<=n;i++){    //初始化区间长度为1时的值
           dp_min[i][0] = a[i];
           dp_max[i][0] = a[i];
       }
  int p=log2(n);//可倍增区间的最大次方: 2^p <= n
    for(int k=1;k<=p;k++)   //倍增计算小区间。先算小区间，再算大区间，逐步递推
          for(int s=1;s+(1<<k)<=n+1;s++){
              dp_max[s][k]=max(dp_max[s][k-1], dp_max[s+(1<<(k-1))][k-1]);
              dp_min[s][k]=min(dp_min[s][k-1], dp_min[s+(1<<(k-1))][k-1]);
    }
  }
  int st_query(int L,int R){
  int k = log2(R-L+1);
      int x = max(dp_max[L][k],dp_max[R-(1<<k)+1][k]); //区间最大
      int y = min(dp_min[L][k],dp_min[R-(1<<k)+1][k]); //区间最小
      return...
  }

• 维护最大次打值

• ```c++ pairdp_max[N][20],dp_second_max[N][20]; void st_init() { for (ll i = 1; i <= n; i++) { dp_max[i][0] = {arr[i].h,arr[i].i}; dp_second_max[i][0] = {0,0}; } ll p = log2(n); for (ll k = 1; k <= p; k++) { for (ll s = 1; s + (1 << k) <= n + 1; s++) { dp_max[s][k] = max(dp_max[s][k - 1], dp_max[s + (1 << (k - 1))][k - 1]); pair max1 = dp_max[s][k - 1]; pair max2 = dp_max[s + (1 << (k - 1))][k - 1]; pair min1 = dp_second_max[s][k - 1]; pair min2 = dp_second_max[s + (1 << (k - 1))][k - 1]; if (max1 > max2) { dp_second_max[s][k] = max(min1, max2); } else { dp_second_max[s][k] = max(max1, min2); } } } }

pair,pair\> st_query(ll L, ll R) { if(L==R) return {dp_max[L][0],{0,0}}; ll k = log2(R - L + 1); pair max1 = dp_max[L][k]; pair max2 = dp_max[R - (1 << k) + 1][k]; pair min1 = dp_second_max[L][k]; pair min2 = dp_second_max[R - (1 << k) + 1][k]; pair max_val = max(max1, max2),second_max_val; if(max_val==max1){ if(max_val!=max2){ second_max_val=max(max2,min1); } else second_max_val=max(min1,min2); } else{ second_max_val=max(max1,min2); } return {max_val,second_max_val}; }

```

• 为了剔除重复元素，需要维护二元组

例题

• P4155 国旗计划
• 朴素贪心：对每一个人都向后遍历一次，每次“跳跃”都尝试跳跃最短的距离，这样一次一次跳跃时间复杂度为\(O(n^2)\)太慢了
• 使用倍增可以进行更加迅速的跳跃，由于数都可以二进制拆分，对二进制拆分后的跳跃距离进行遍历，时间复杂度降低为\(O(nlogn)\)
• 此外本题还将原序列赋值为两倍，即将环展开为链

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+1;
int n,m;
struct warrior{
    int id,l,r;
    bool operator<(const warrior &a)const{
        return l<a.l;
    }  
}w[N*2];
int n2;
int go[N][20];
int res[N];
void init(){
    int nxt=1;
    //计算每个位置跳跃一次后的位置
    for(int i=1;i<=n2;i++){
        while(nxt<=n2&&w[nxt].l<=w[i].r){
            nxt++;
        }
        go[i][0]=nxt-1;
    }
    //递推出跳跃任何二进制距离的项
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n2;j++){
            go[j][i]=go[go[j][i-1]][i-1];
        }
    }
}
void getans(int x){
    int len=w[x].l+m,cur=x,ans=1;
   //从大到小选择，计算出结果
    for(int i=log2(N);i>=0;i--){
        int pos=go[cur][i];
        if(pos&&w[pos].r<len){
            cur=pos;
            ans+=(1<<i);
        }
    }
    res[w[x].id]=ans+1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        w[i].id=i;
        scanf("%d%d",&w[i].l,&w[i].r);
        if(w[i].l>w[i].r) w[i].r+=m;
    }
    sort(w+1,w+n+1);
    n2=n;
    //复制、环展开
    for(int i=1;i<=n;i++){
        n2++;
        w[n2]=w[i];
        w[n2].l+=m;
        w[n2].r+=m;
    }
    init();
    for(int i=1;i<=n;i++){
        getans(i);
    }
    for(int i=1;i<=n;i++){
        printf("%d ",res[i]);
    }
    return 0;
}

• P3509 ZAB-Frog - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
• 先通过滑动窗口求解初始值，然后倍增处理，在\(logm\)时间得到结果
• 此外空间受限需要使用滚动数组