本文实际上是我于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;
}