本文实际上是我于2022/7/29补写的
分治
逆序对(洛谷P1908)
我们直接打暴力,枚举每一个树a[i],在a[1~n]直接寻找比a[i]小的数即可。
但是这样很明显不能通过本题,他的时间复杂度是$$O(n^{2})$$
我们可以用线段树维护权值数组来加速,但是今天的重点是分治。
我们可以观察到,对于逆序对(x,y),只有3种情况:
- x,y在左边
- x,y在右边
- x左边y右边
所以我们能实现一个函数 calc(l, r):
- 调用 calc(l, mid) 获得左边块内的逆序对个数
- 调用 calc(mid, r) 获得右边块内的逆袭对个数
- 亲自去统计跨块的逆序对个数
即为在归并的过程中统计个数。
#include <bits/stdc++.h>
using namespace std;
int a[500005], n;
void input() {
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
}
long long ans;
// 统计 a[l, r) 区间内的逆序对的个数
void calc(int l, int r) {
if(l == r - 1)
return;
int mid = (l + r) / 2;
calc(l, mid); // 统计左边块内的逆序对个数
calc(mid, r); // 统计右边块内的逆序对个数
// 亲自统计跨块逆序对个数:x在左边,y在右边
for(int x=l; x<mid; x++) // 枚举左边块的 x
for(int y=mid; y<r; y++) // 枚举右边块的 y
if(a[x] > a[y]) ans++; // 发现一个跨块逆序对
}
void work() {
calc(0, n);
printf("%lld\n", ans);
}
int main() {
input();
work();
return 0;
}
但是我们用Master定理一算,嗯?还是$$O(n^{2})$$啊!
实现一个函数 calc(l, r):
- 调用 calc(l, mid)
- 调用 calc(mid, r)
- 将左边、右边的块排序
- O(n) 亲自统计跨块的逆序对个数
#include <bits/stdc++.h>
using namespace std;
int a[500005], n;
void input() {
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
}
long long ans;
int tmp[500005];
// 统计 a[l, r) 区间内的逆序对的个数
// 顺便给 a[l, r) 排序
void calc(int l, int r) {
if(l == r - 1)
return;
int mid = (l + r) / 2;
calc(l, mid); // 统计左边块内的逆序对个数
calc(mid, r); // 统计右边块内的逆序对个数
// 现在 a[l, mid) 和 a[mid, r) 都是有序的
// 亲自统计跨块逆序对个数:x在左边,y在右边
int y = mid;
for(int x=l; x<mid; x++) { // 枚举左边的 x
while(y < r && a[y] < a[x]) y++;
ans += y - mid; // a[mid, y) 全都小于 a[x],所以统计进答案
}
// 以下是合并左右两个有序数组,保证 a[l, r) 在调用结束后有序
// 归并排序
int p=l, q=mid, cur=l;
while(p < mid && q < r){
if(a[p] < a[q])
tmp[cur++] = a[p++];
else
tmp[cur++] = a[q++];
}
while(p < mid)
tmp[cur++] = a[p++];
while(q < r)
tmp[cur++] = a[q++];
for(int i=l; i<r; i++)
a[i] = tmp[i];
}
void work() {
calc(0, n);
printf("%lld\n", ans);
}
int main() {
input();
work();
return 0;
}
省了2个sort,就降下来了时间复杂度:
$$ T(n) = 2T(n/2) +O(n) = O(nlog n) $$
快速幂
因为取模可以在运算过程中取,所以我们可以不爆空间。
计算 xa mod p 时,分两种情况:
$$ 若 2 | a,则答案为 (x^{a/2})2 mod p\\ 若 2 ∤ a,则答案为 (x^{⌊a/2⌋})2 · x modp $$
ll quickPow(ll a, ll x, ll p) {
if(x == 0) return 1;
if(x == 1) return a % p;
ll tmp = quickPow(a, x/2, p);
if(x % 2 == 0)
return tmp * tmp % p;
else
return tmp * tmp % p * a % p;
}