怎么做网站排名网站关键词快速排名工具

「分治」是解决「逆序对」⾮常经典的解法，后续我们也会学到利⽤「树状数组」或「线段树」解决逆序对问题。
如果把整个序列[l, r]从中间mid 位置分成两部分，那么逆序对个数可以分成三部分：

• [l, mid]区间内逆序对的个数c1 ；
• [mid + 1, r]区间内逆序对的个数c2 ；
• 从[l, mid]以及[mid + 1, r]各选⼀个数，能组成的逆序对的个数c3
  那么逆序对的总数就是c1+c2+c3。其中求解c1,c2的时候跟原问题是⼀样的，可以交给「递归」去处理（经过前⾯题⽬的铺垫，我相信⼤家应该能够理解），那我们重点处理「⼀左⼀右」的情
  况。
  如果在处理⼀左⼀右的情况时，两个数组「⽆序」，我们的时间复杂度其实并没有优化到哪去，甚⾄还「不如暴⼒解法」。但是如果两个数组有序的话，我们就可以快速找出逆序对的个数。
  先不管怎么求逆序对，我们能让左右两个数组有序嘛？当然可以，这不就是「归并排序」么。因此，我们能做到在求完c1, c2 之后，然后让「左右两个区间有序」
  那么接下来问题就变成，已知两个「有序数组」，如何求出左边选⼀个数，右边选⼀个数的情况下的逆序对的个数。核⼼思想就是找到右边选⼀个数之后，左边区间内「有多少个⽐我⼤的」
  

定义两个「指针」扫描两个有序数组：此时会有下⾯三种情况：

1. a[cur1] ≤ a[cur2]：a[cur1]不会与[cur2, r]区间内任何⼀个元素构成逆序对，cur1++ ；
2. a[cur1] > a[cur2]：此时[cur1, mid]区间内所有元素都会与a[cur2]构成逆序对，逆序对个数增加 mid - cur1 + 1，此时cur2已经统计过逆序对了，cur2++；
   重复上⾯两步，我们就可以在O(N)的时间内处理完「⼀左⼀右」时，逆序对的个数。⽽且，我们会发现，这跟我们「归并排序的过程」是⾼度⼀致的。所以可以⼀边排序，⼀边计算逆序对的个数

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 5e5 + 10;
int n;
int a[N];
int tmp[N];LL merge(int left, int right)
{if (left >= right) return 0;LL ret = 0;int mid = (left + right) / 2;ret += merge(left, mid);ret += merge(mid + 1, right);//一左一右int cur1 = left, cur2 = mid + 1, i = left;while (cur1 <= mid && cur2 <= right){if (a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else{ret += mid - cur1 + 1;tmp[i++] = a[cur2++];}}while (cur1 <= mid) tmp[i++] = a[cur1++];while (cur2 <= right) tmp[i++] = a[cur2++];for (int j = left; j <= right; j++) a[j] = tmp[j];return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];cout << merge(1, n) << endl;return 0;
}

在快排中，当我们把数组「分成三块」之后： [l, left][left + 1, right - 1][right, r]，我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。
那么我们可以直接去「相应的区间」去寻找最终结果就好了

#include <bits/stdc++.h>
using namespace std;const int N = 5e6 + 10;int n, k;
int a[N];int get_random(int left, int right)
{return a[rand() % (right - left + 1) + left];
}int quick_select(int left, int right, int k)
{if (left >= right) return a[left];//1.选择基准元素int p = get_random(left, right);//2.分三块int l = left - 1, i = left, r = right + 1;while (i < r){if (a[i] < p) swap(a[++l], a[i++]);else if (a[i] == p) i++;else swap(a[--r], a[i]);}//3.选择存在最终结果的区间//[left, l][l+1, r-1][r, right]int a = l-left+1, b = r - 1 - l, c = right - r + 1;if (k <= a) return quick_select(left, l, k);else if (k <= a+b) return p;else return quick_select(r, right, k-a-b);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);srand(time(0));cin >> n >> k;k++;for (int i = 1; i <= n; i++) cin >> a[i];cout << quick_select(1, n, k);return 0;
}

如果把整个序列[l, r]从中间mid位置分成两部分，那么整个序列中「所有的⼦数组」就分成三部分：

• ⼦数组在区间[l, mid]内；
• ⼦数组在区间[mid + 1, r]内；
• ⼦数组的左端点在[l, mid]内，右端点在[mid + 1, r]内
  那么我们的「最终结果」也会在这三部分取到，要么在左边区间，要么在右边区间，要么在跨越中轴线的区间。因此，我们可以先求出左边区间的最⼤⼦段和，再求出右边区间的最⼤⼦段和，最后求出中间区间的最⼤⼦段和。其中求「左右区间」时，可以交给「递归」去解决。
  那我们重点处理如何求出「中间区间」的最⼤⼦段和。可以把中间区间分成两部分：
• 左边部分是从mid为起点，「向左延伸」的最⼤⼦段和；
• 右边部分是从mid + 1为起点，「向右延伸」的最⼤⼦段和。
  分别求出这两个值，然后相加即可。
  求法也很简单，直接「固定起点」，⼀直把「以它为起点的所有⼦数组」的和都计算出来，取最⼤值即可

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;typedef long long LL;int n;
LL a[N];int dfs(int left, int right)
{if (left == right) return a[left];int mid = (left + right) / 2;int ret = max(dfs(left, mid), dfs(mid+1, right));//求一左一右最大值int sum = a[mid], lmax = a[mid];for (int i = mid-1; i >= left; i--){sum += a[i];lmax = max(lmax, sum);}sum = a[mid+1]; int rmax = a[mid+1];for (int i = mid+2; i <= right; i++){sum += a[i];rmax = max(rmax, sum);}ret = max(ret, lmax + rmax);return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];cout << dfs(1, n);return 0;
}

⾮常经典的⼀道分治题⽬，也可以说是⼀道递归题⽬。
⼀维分治的时候，我们是从中间把整个区间切开，分成左右两部分（其实有时候我们可以三等分，就看具体问题是什么）。⼆维的时候，我们可以横着⼀⼑竖着⼀⼑，分成左上、右上、左下、右下四份。⽽这道题的矩阵⻓度正好是2^k ，能够被不断平分下去。像是在暗⽰我们，要⽤分治，要⽤分治，要⽤分治…
当我们把整个区间按照中⼼点⼀分为四后，四个区间⾥⾯必然有⼀个区间有缺⼝（就是公主的位置），那这四个区间不⼀样，那就没有相同⼦问题了。别担⼼，只要我们在中⼼位置放上⼀块地毯，四个区间就都有⼀个缺⼝了。如下图所⽰：

⽆论缺⼝在哪⾥，我们都可以在缺⼝对应的区间的⻆落，放上⼀个地毯。接下来四个区间都变成只有⼀个缺⼝的形式，就可以⽤递归处理⼦问题。
因此，我们拿到⼀个矩阵后的策略就是：

• 先四等分；
• 找出缺⼝对⾯的区间，放上⼀块地毯；
• 递归处理四个⼦问题

#include <bits/stdc++.h>
using namespace std;int k, x, y;void dfs(int a, int b, int len, int x, int y)
{if (len == 1) return;len /= 2;if (x < a + len && y < b + len) //公主在左上角{//放一号地毯cout << a + len << " " << b + len << " " << 1 << endl;dfs(a, b, len, x, y);dfs(a, b+len, len, a+len-1, b+len);dfs(a+len, b, len, a+len, b+len-1);dfs(a+len, b+len, len, a+len, b+len);}else if (x >= a+len && y >= b+len){cout << a + len-1 << " " << b + len-1 << " " << 4 << endl;dfs(a, b, len, a+len-1, b+len-1);dfs(a, b+len, len, a+len-1, b+len);dfs(a+len, b, len, a+len, b+len-1);dfs(a+len, b+len, len, x, y);}else if (x >= a+len){cout << a + len-1 << " " << b + len << " " << 3 << endl;dfs(a, b, len, a+len-1, b+len-1);dfs(a, b+len, len, a+len-1, b+len);dfs(a+len, b, len, x, y);dfs(a+len, b+len, len, a+len, b+len); }else{cout << a + len << " " << b + len-1 << " " << 2 << endl;dfs(a, b, len, a+len-1, b+len-1);dfs(a, b+len, len, x, y);dfs(a+len, b, len, a+len, b+len-1);dfs(a+len, b+len, len, a+len, b+len); }
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> k >> x >> y;k = (1 << k);dfs(1, 1, k, x, y);return 0;
}