【算法笔记】分治专题

分治

整体结构

分解

对于一些问题，当规模小到某个程度时，会自动得到解决。分治就是利用了这个特性，将问题分解成若干个更小的、相似的子问题，使子问题可以轻松得到解决。在这一步我们还需要确保：子问题确实是原问题的小规模版，可以用与原问题同样的模式对其进行处理，且子问题之间相互独立。

处理

如果需要对分解后的集合单独做一些特定的处理，可以在这一步完成。

合并

如果需要对分解后的集合共同做一些特定的处理，可以在这一步完成。这步既可以先复制子区间，然后直接把结果写入原数组，也可以先把结果写在临时数组，最后再复制回原数组，但不管怎样不能直接在原数组上面排序。

细分类型

着重处理过程

在此类型的题目中，先有分割点的选取，然后重点在于对分割出的子问题们进行处理，分割点的选取没有严格的要求，一般选在中点，但其实选在哪里基本都能解决问题，只是对效率有些影响而已。比较典型的就是归并排序以及以归并排序的结构为模版衍生出的一系列处理方式。

P6001 归并排序

• 【分解&递归】

  ?void mergeSort(vector<int> &arr, int l, int r){
  ? ? ?if(l >= r) return;//递归出口：子问题只有一个元素
  ? ? ?int mid = l + (r - l)/2;//找到当前区间的中点
  ? ? ?mergeSort(arr, l, mid);//对左区间+中点递归处理
  ? ? ?mergeSort(arr, mid +1, r);//对右区间递归处理
  ? ? ?merge(arr, l, mid, r);//合并已经有序了的左右区间
  ?}

• 【合并】

  ?void merge(vector<int> &arr, int l, int mid, int r){
  ? ? ?//计算左右区间的长度
  ? ? ?int n1 = mid - l + 1;
  ? ? ?int n2 = r - mid;
  ? ? ?//把左右区间的元素复制到新空间，一会儿排序要用
  ? ? ?vector<int> arr1(n1 + 10);
  ? ? ?for(int i =1; i <= n1; i++) arr1[i] = arr[l+ i - 1];
  ? ? ?vector<int> arr2(n2 + 10);
  ? ? ?for(int i =1; i <= n2; i++) arr2[i] = arr[i + mid];
  ? ? ?//依次把两个子问题开头元素中较小的那一个存入，直到至少一个子问题解决完毕
  ? ? ?int i=1, j= 1, k=l; 
  ? ? ?while(i <= n1 && j <= n2){ //挨个比较 
  ? ? ? ? ?if(arr1[i] <= arr2[j]) arr[k++] = arr1[i++];
  ? ? ? ? ?else arr[k++] = arr2[j++];
  ? ?  } 
  ? ? ?//处理剩余部分
  ? ? ?while(i <= n1) arr[k++] = arr1[i++];
  ? ? ?while(j <= n2) arr[k++] = arr2[j++];
  ?}

P6002 逆序对的数量

本题其实就是在经典归并排序的基础上增加了一些判断和统计。

当我们将一个数组一分为二时，原数组中的逆序对将会分为三种：两个数都在左区间的、两个数都在右区间的、两个数在左右区间各一个的。该如何对这三种逆序对进行统计呢。

首先，当区间只有一个元素时，不可能存在前两种逆序对。

其次，假设某单元素的左区间和某单元素的右区间形成了一个逆序对，当该层递归走到出口时，这两个区间将会被合并，此时该逆序对成为了区间内部的逆序对，并且在更靠外的任何一层递归内，都是区间内部的逆序对。同理可知，任意一层的跨区间逆序对在更外层都会成为区间内部的逆序对。

这就意味着，如果我们只统计跨区间的逆序对，那么所有逆序对都将只会被统计一次，可以得到正确的结果。

最后，我们还可以利用左右区间各自有序的特性，当左区间某元素和右区间某元素构成逆序对，那么它后面的所有元素一定也可以和该右区间元素构成逆序对。

?long long merge_sort(int l, int r){
? ? ?if( l >= r) return 0;//递归出口
? ? ?long long ans = 0;//计数器
? ? ?int mid = (l + r) >> 1;//分解
? ? ?ans = merge_sort(l, mid) + merge_sort(mid+1, r);//递归
? ? ?//以下逻辑在合并左右区间的同时统计跨区逆序对数量
? ? ?int k=0, i=l, j=mid+1;//分别设置临时数组、左区间、右区间指针
? ? ?while(i <= mid && j <= r){//两个区间都还有剩余元素
? ? ? ? ?if(a[i] <= a[j]) tmp[k++] = a[i++];//左侧较小时只合并，不做别的
? ? ? ? ?else{//左侧较大时
? ? ? ? ? ? ?tmp[k++] = a[j++];//右侧合并
? ? ? ? ? ? ?//其实下面这一行就是本题和归并排序唯一的区别
? ? ? ? ? ? ?ans += mid - i + 1;//左侧区间从i到mid所有元素都可以和a[j]形成逆序对，将数量累计 
? ? ? ?  }
? ?  }
? ? ?//处理剩余部分，至多只有一个区间还有元素，不可能有逆序对，只合并就可以
? ? ?while(i <= mid) tmp[k++] = a[i++];
? ? ?while(j <= r) tmp[k++] = a[j++];
? ? ?//把临时数组内的内容复制回原数组里面
? ? ?for(int i=l,k=0; i <= r; i++, k++) a[i] = tmp[k];
? ? ?return ans;
?}

P6005 最?连续?数组和

用分治的想法看子数组和，被分解后，原数组的和最大的子数组，要么包含在左或右子区间内，要么跨区。

我们只要算出左右子区间的最大子数组和（已经是规模更小的相似问题了，可以递归了）和跨区的最大和，然后选出三者中最大的就可以了。

首先写一个计算跨区最大和的函数，从中点开始分别往左右累加，记录左边和右边的累加最大值再相加即可。

至于区内最大和，递归会帮我们解决的，子数组中只有一个元素时，递归到达出口，返回该元素。

?int fun(int l, int r){ // 求横跨左右的最大字段和，太简单了没什么好注释的
? ? ?int m = (l + r)/2;
? ? ?int sumL = 0, ansL = a[m];
? ? ?int sumR = 0, ansR = a[m+1];
? ? ?for(int i=m; i >=l; i--){
? ? ? ? ?sumL += a[i];
? ? ? ? ?ansL = max(ansL,sumL);
? ?  }
? ? ?for(int i=m+1; i <=r; i++){
? ? ? ? ?sumR += a[i];
? ? ? ? ?ansR = max(ansR,sumR);
? ?  }
? ? ?return ansL+ansR;
?}
?int max_sum(int l, int r){ ?
? ? ?if(l==r) return a[l];//出口
? ? ?int m = (l+r)/2;//分解
? ? ?int L = max_sum(l,m);//子区间递归
? ? ?int R = max_sum(m+1,r);//子区间递归
? ? ?int LR = fun(l,r);//跨区和
? ? ?return max(max(L,R),LR);//三者择优
?}

着重寻找分界点

在此类型的题目中，找到正确的分割点才是目的，对分割出的子问题们进行处理一般只是为了将其中的元素正确地归类，从而通过找到类型转换的临界点来确定分割点的位置，在此类问题中，分割动作的目的在于缩小可能的解的范围，直到范围中只剩一个解时，那就是正解。比较典型的是快速排序以及以快速排序的结构为模版衍生出的一系列处理方式。

快速排序

大致分为选择基准-找到基准值正确位置-递归处理三个步骤，1和3都非常简单，没什么单独拿出来说的必要。

在快排中，正确的分割点=pivot在最终有序数组中该在的位置，所以说找到正确的分割点才是目的。

?void quick_sort(int a[], int l, int r){
? ? ?if(l >= r) return; // 递归出口 
? ? ?int x=a[l]; //选择基准值，此处可以优化，常用操作是每一轮开始时将pivot和后续随机元素交换位置
? ? ?int i = l - 1;
? ? ?int j = r + 1;
? ? ?while( i < j){ // 开始分区操作
? ? ? ? ?do i++; while(a[i] < x); // 从左向右找到第一个大于等于x的数
? ? ? ? ?do j--; while(a[j] > x);// 从右向左找到第一个小于等于x的数
? ? ? ? ?if(i < j) swap(a[i],a[j]);//使两个数都去正确的一边
? ?  } 
? ? ?quick_sort(a,l,j); // 递归地对左半部分进行快速排序
? ? ?quick_sort(a,j+1,r);// 递归地对右半部分进行快速排序
?}

P6003 第k?的数

本题是快速排序的变式。

当快速排序完成一次划分，找到当前pivot的正确位置时，其实此时的left/right指针就表明了pivot是整个序列中第left/right小的数。

我们可以利用这个特性：如果一次划分结束，pivot位置>=目标，那目标在左侧区间（包含mid），反之在右侧区间。

在左侧时，我们从左侧继续寻找第k小的数。

在右侧时，我们从右侧寻找第k-mid小的数，这样加上左侧部分以后，它在整体中就是第k-mid+mid=k小的数。

当区间内只剩一个元素时，找到目标。

?int quick_sort(int l, int r, int k){
? ? ?if(l >= r) return; // 递归出口 
? ? ?int x=a[l]; //选择基准值，此处可以优化，常用操作是每一轮开始时将pivot和后续随机元素交换位置
? ? ?int i = l - 1;
? ? ?int j = r + 1;
? ? ?while( i < j){ // 开始分区操作
? ? ? ? ?do i++; while(a[i] < x); // 从左向右找到第一个大于等于x的数
? ? ? ? ?do j--; while(a[j] > x);// 从右向左找到第一个小于等于x的数
? ? ? ? ?if(i < j) swap(a[i],a[j]);//使两个数都去正确的一边
? ?  } 
? ? ?//以下逻辑是本题和快排的区别
? ? ?int ?m = j - l + 1;//计算左区间长度
? ? ?if(k <= m) return quick_sort(l, j, k); //递归地从左侧继续寻找第k小的数
? ? ?else return quick_sort(j+1, r, k-m); //递归地从右侧寻找第k-mid小的数
?}

二分搜索

二分查找算是比较特殊的分治，特殊的点在于，它一般应用于一个有序的待搜索集上，我们可以利用其有序性，每次舍弃掉一半的数据，借此来提高搜索的效率。

一般分为三步。

确定目标的上下限，保证一定能在搜索范围内找到解，并计算当前区间的中点

判断当前区间的中点是否满足目标要求，解会在它的左侧还是右侧

重新设置区间，回到第一步，在这一步要注意检查，重设的方式在极端的情况下是否会错过解，或者导致区间原地死循环。

不难发现，其实下面五个题目的整体框架是一样的，变化的只有每个题目判断当前中点是否满足条件的方式而已。

P6011 有序数组中查找数

经典二分框架。只有判断条件那一行是根据题意变化的。

?int Find(int a[]){
? ? ?int l = 1, r = n;
? ? ?while(l < r){
? ? ? ? ?int mid = l + r >> 1;
? ? ? ? ?if(a[mid] > a[r]) l = mid + 1;//此时分界点一定在右边
? ? ? ? ?else r = mid; //此时分界点可能是mid可能在mid左边 
? ?  }
? ? ?return a[r];
?}

P6012 有序数组中查找数2

经典二分框架。

增加了一个查找失败的判断，只有在找到左边界时才找右边界。

还更改了一次计算mid的逻辑，配合两次查找方向的不同。

?int Find2(int k){
? ? ?int l = 0, r = n-1; // 确定区间
? ? ?while(l < r){//先找左边界
? ? ? ? ?int mid = l + r >> 1; //lr相邻时mid会落在l
? ? ? ? ?if(a[mid] >= k) r = mid; //分界点在mid或mid的左边 
? ? ? ? ?else l = mid + 1;//分界点在右边
? ? ? ?  } 
? ? ? ? ?if(a[r] == k) {//确认左边界找到的情况下再找右边界，否则直接输出失败信号
? ? ? ? ? ? ?l = l; //可以不写 
? ? ? ? ? ? ?r = n-1;//定义新的区间（从查找到的左边界到整个数组的右边界）
? ? ? ? ? ? ?while(l < r){
? ? ? ? ? ? ? ? ?int mid = l + r + 1 >> 1;//lr相邻时mid会落在r
? ? ? ? ? ? ? ? ?if(a[mid] <= k) l = mid;//分界点在mid或mid的右边
? ? ? ? ? ? ? ? ?else r = mid - 1;//分界点在左边
? ? ? ?  }
? ?  } 
?}

P6013 数的三次?根数

整体还是经典二分框架。

但是由于这次的边界不是整数，很难出现两个浮点数精确相等的情况，结束循环的条件变成了“两个数足够接近”。其他都没差啦。

?int func(double x){
? ? ?double l = -10000, r = 10000;
? ? ?while(r - l > 1e-8){
? ? ? ? ?double mid = (l + r) /2;
? ? ? ? ?if(mid * mid * mid >=x) r = mid;
? ? ? ? ?else l = mid;
? ?  }
? ? ?return l;
?}

P6014 砍树

整体还是经典二分框架。

本题判断中点元素是否满足要求的过程比较复杂，单独拿出来做了一个判断函数。

同时增加了循环内的答案记录，原因写注释里面了，对着代码看更清楚。

?bool check(int n, int k, int l){
? ? ?long long sum = 0;
? ? ?for(int i = 1; i <=n; i++) sum += a[i]/ l;//之前总数+这棵能砍几段 ?
? ? ?return sum >= k;
?}
?int func(){
? ? ?r = max_element(a[i]);//不可能比最长的树更大
? ? ?int ans = 0;
? ? ?while(l < r){
? ? ? ? ?int mid = l + r + 1 >> 1;
? ? ? ? ?if(check(n, k, mid)){//判断当前mid能不能砍出k段
? ? ? ? ? ? ?ans = mid; //由于不知道最后一轮循环传入的mid是否满足答案要求，无法确定正确答案是这轮的mid还是上一轮的mid，所以直接在这里实时的记录下最新的满足要求的mid
? ? ? ? ? ? ?l = mid;
? ? ? ?  }else r = mid - 1;
? ?  }
? ? ?return ans;
?}

P6015 数列分段

和上个题几乎一模一样，判断函数有变化，加了循环内答案记录，其他就不做赘述了。

?bool check(long long k){
? ? ?int cnt = 1; //需要初始化为1，最少有1段 
? ? ?int sum = 0;
? ? ?for(int i = 1; i <= n; i++){
? ? ? ? ?if( a[i] > k) return false;//有元素比总和还大，肯定不可能
? ? ? ? ?if(sum + a[i] > k){//下一个放不下了，在此分段
? ? ? ? ? ? ?cnt++;
? ? ? ? ? ? ?sum = a[i];//另起一个新段
? ? ? ?  }else sum += a[i];
? ?  }
? ? ?return cnt <= m; ?//满足题目要求，需要再减少试试 
?}
?int fun(){
? ? ?//l = a[i]最大元素
? ? ?//r = a[i]元素和;
? ? ?long long ans = 0;
? ? ?while(l <= r){
? ? ? ? ?long long mid = (r + l) / 2 ;
? ? ? ? ?if(check(mid)){
? ? ? ? ? ? ?ans = mid;
? ? ? ? ? ? ?r = mid - 1; 
? ? ? ?  }else l = mid + 1;
? ?  }
? ? ?return ans;
?}

其他

P6004 模幂运算

感觉这个题更重要的不是算法思想，而是数学上的推理。

主要用到了指数的拆分：底数平方而指数减半，此时最终结果不变

还用到了取模的一些特性，先指数运算再取模和先取模再指数运算再取模，最终结果是一样的

本题就借助了这两个特性，一边放大底数减小指数，一边对底数取模，将放大的底数再次缩小，达到简化计算的效果，直到指数减到0时返回1并跳出循环

然后就只剩一些细节处理了，具体来说就是b/2时有时候会丢失1（b是奇数时），所以要想办法把一个a乘回去。

?long long quick_pow(long long a, long long b, long long p) {
? ? ?long long ans = 1;
? ? ?a = a % p; ?// 如果a大于p，先取模
? ? ?while (b > 0) { //b=0时，说明上一轮就已经只剩a的一次，且已经在b是奇数的分支里乘到ans上了
? ? ? ? ?if (b & 1) ?// 如果b是奇数，先乘上a
? ? ? ? ? ? ?ans = (ans * a) % p;//只要是乘法运算，随时取模
? ? ? ? ?b >>= 1; ?// b除以2
? ? ? ? ?a = (a * a) % p; ?//用到取模和平方可以互换顺序的特性
? ?  }
? ? ?return ans;
?}