[国家集训队]排队

· · 题解

题目描述

题目传送门

思路

更好的阅读体验

对于交换 i , j 的数字，我们考虑交换这两个数字（记这两个数字分别为 a,b）对答案的贡献。

显然，对于区间 [i+1,j-1] 中每一个大于 a 的数字会产生 +1 的贡献，每一个小于 a 的数字会产生 -1 的贡献，每一个小于 b 的数字会产生 +1 的贡献，每一个大于 b 的数字会产生 -1 的贡献。最后还有 a 与 b 是否为逆序对的贡献。

显然，我们需要求出区间中大（小）于一个数字的个数。这个问题可以使用树套树或暴力解决，但是在此处讲一种别致的分块。

对数列进行离散化，数的大小的值域为 1 \sim n。我们不妨在数列分块中在套上一个值域分块。记 Cnt1[x][y] 表示前 x 块的数列中值域在第 y 块出现的次数，记 Cnt2[x][y] 表示前 x 块的数列中数字 y，记 Bel[i] 表示数字 i 所对应的块，由于值域和块大小是同阶的，所以这个数组既可以表示数列对应的块，也可以表示数值对应的块。

一下的操作仅讨论查询小于一个数的个数，大于一个数字同理。

查询：设查询小于的数字为 k，块大小为 block_size。对于数列中的块外元素，暴力解决，时间复杂度 O(\sqrt n)。数列中的块内元素我们再此分为两类，第一类为完整值域中出现，即值域 Bel[0] \sim Bek[k]-1，这个利用 Cnt1 前缀相减可以在 O(\sqrt n) 的时间内算完；第二类为不在完整块内的，即数值 (Bel[k]-1)*block_size+1 \sim k，这个利用 Cnt2 前缀相减可以在 O(\sqrt n) 的时间内算完。总时间复杂度为 O(\sqrt n)。

交换：将 Cnt1[][Bel[a]],Cnt1[][Bel[b]],Cnt2[][a],Cnt2[][a] 四个数组总后往前差分即可得到每一块的数，修改对应的值并维护然后做前缀和就好了。这里有个细微的优化，差分（前缀）只需从 Bel[j] 到 Bel[i] 就可以了。由于块的数量不超过根号，所以时间复杂度为 O(\sqrt n)。

显然，Cnt1 可以 O(n) 预处理， Cnt2 可以 O(n\sqrt n) 预处理。至此，我们就已经在 O(n \sqrt n) 的时间复杂度内 AC。

这个思路来自于 [Ynoi2018] 未来日记 的启发。

代码

#include <bits/stdc++.h>
using namespace std;

char gc() {
    static char now[1 << 20], *S, *T;
    if (T == S) {
        T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
        if (T == S) return EOF;
    }
    return *S++;
}
template <typename T>
void read(T &x) {
    x = 0;
    char c = gc();
    while (c < '0' || c > '9') c = gc();
    x = c - '0';
    while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void read(T &x, Args &...args) {
    read(x);
    read(args...);
}

const int MAXN = 20010;

int Num[MAXN] , Temp[MAXN] , N , M , Num2[MAXN] , l , r , Block;

long long Sum;

int Cnt1[600][600];
int Cnt2[600][MAXN];

int Left[600] , Right[600] , Bel[MAXN];

void Merge(int l1 , int r1 , int l2 , int r2) {
    int ToT = 0;
    while(l1 <= r1 && l2 <= r2) {
        if(Num[l1] <= Num[l2]) {
            Temp[++ToT] = Num[l1++];
        }
        else {
            Temp[++ToT] = Num[l2++];
            Sum += r1 - l1 + 1;
        }
    }
    while(l1 <= r1) Temp[++ToT] = Num[l1++];
    while(l2 <= r2) Temp[++ToT] = Num[l2++];

    for(int i = ToT , j = r2; i >= 1; i--, j--) {
        Num[j] = Temp[i];
    }
}

void MergeSort(int l , int r) {
    if(l < r) {
        int Mid = l + r >> 1;
        MergeSort(l , Mid);
        MergeSort(Mid + 1 , r);
        Merge(l , Mid , Mid + 1 , r);
    }
}

int Query1(int l , int r , int k) { //查找 < k 的数的个数 
    int Bel_R = Bel[r] , Bel_L = Bel[l];

    if(Bel_L == Bel_R) {
        int res = 0;

        for(int i = l; i <= r; i++) {
            if(Num2[i] < k) res++;
        }

        return res;
    }
    else {
        int res = 0;

        for(int i = l; i <= Right[Bel_L]; i++) {
            if(Num2[i] < k) res++;
        }

        for(int i = 0; i < Bel[k]; i++) {
            res += Cnt1[Bel_R - 1][i] - Cnt1[Bel_L][i];
        }
        for(int i = (Bel[k] - 1) * Block + 1; i < k; i++) {
            res += Cnt2[Bel_R - 1][i] - Cnt2[Bel_L][i];
        }

        for(int i = Left[Bel_R]; i <= r; i++) {
            if(Num2[i] < k) res++;
        }

        return res;
    }
}

int Query2(int l , int r , int k) { //查找 > k 的数的个数 
    int Bel_R = Bel[r] , Bel_L = Bel[l];

    if(Bel_L == Bel_R) {
        int res = 0;

        for(int i = l; i <= r; i++) {
            if(Num2[i] > k) res++;
        }

        return res;
    }
    else {
        int res = 0;

        for(int i = l; i <= Right[Bel_L]; i++) {
            if(Num2[i] > k) res++;
        }

        for(int i = Bel[N]; i > Bel[k]; i--) {
            res += Cnt1[Bel_R - 1][i] - Cnt1[Bel_L][i];
        }
        for(int i = min(Bel[k] * Block , 20000); i > k; i--) {
            res += Cnt2[Bel_R - 1][i] - Cnt2[Bel_L][i];
        }

        for(int i = Left[Bel_R]; i <= r; i++) {
            if(Num2[i] > k) res++;
        }

        return res;
    }
}

void Swap(int l , int r) {
    int x = Num2[l] , y = Num2[r];

    int Bel_R = Bel[r] , Bel_L = Bel[l];

    for(int i = Bel[N]; i >= Bel_L; i--) {
        Cnt1[i][Bel[x]] -= Cnt1[i - 1][Bel[x]];
        Cnt1[i][Bel[y]] -= Cnt1[i - 1][Bel[y]];
        Cnt2[i][x] -= Cnt2[i - 1][x];
        Cnt2[i][y] -= Cnt2[i - 1][y];
    }

    Cnt1[Bel_L][Bel[y]]++;
    Cnt1[Bel_L][Bel[x]]--;
    Cnt2[Bel_L][y]++;
    Cnt2[Bel_L][x]--;

    Cnt1[Bel_R][Bel[y]]--;
    Cnt1[Bel_R][Bel[x]]++;
    Cnt2[Bel_R][y]--;
    Cnt2[Bel_R][x]++;

    for(int i = Bel_L; i <= Bel[N]; i++) {
        Cnt1[i][Bel[x]] += Cnt1[i - 1][Bel[x]];
        Cnt1[i][Bel[y]] += Cnt1[i - 1][Bel[y]];
        Cnt2[i][x] += Cnt2[i - 1][x];
        Cnt2[i][y] += Cnt2[i - 1][y];
    }

    swap(Num2[l] , Num2[r]);
}

int main() {
    scanf("%d" ,&N);

    Block = sqrt(N);

    for(int i = 1; i <= N; i++) {
        scanf("%d" ,&Num[i]);
        Num2[i] = Num[i];
    }

    for(int i = 1; i <= 20000; i++) {
        Bel[i] = (i - 1) / Block + 1;
    }
    MergeSort(1 , N);

    int Size = unique(Num + 1 , Num + 1 + N) - Num - 1;

    for(int i = 1; i <= N; i++) {
        Num2[i] = lower_bound(Num + 1 , Num + 1 + Size , Num2[i]) - Num;
    }

    for(int i = 1; i <= Bel[N]; i++) {
        Left[i] = Right[i - 1] + 1;
        Right[i] = i * Block;
    }

    Right[Bel[N]] = N;

    for(int i = 1; i <= Bel[N]; i++) {
        for(int j = 1; j <= Bel[N]; j++) {
            Cnt1[i][j] = Cnt1[i - 1][j];
        }

        for(int j = 1; j <= N; j++) {
            Cnt2[i][j] = Cnt2[i - 1][j];
        }

        for(int j = Left[i]; j <= Right[i]; j++) {
            Cnt1[i][Bel[Num2[j]]]++;
            Cnt2[i][Num2[j]]++;
        }
    }

    scanf("%d" ,&M);

    printf("%lld\n" ,Sum);

    while(M--) {
        scanf("%d%d" ,&l ,&r);

        if(l > r) swap(l , r);

        Sum = Sum - Query1(l + 1 , r - 1 , Num2[l]) + Query2(l + 1 , r - 1 , Num2[l]) + Query1(l + 1 , r - 1 , Num2[r]) - Query2(l + 1 , r - 1 , Num2[r]);
        if(Num2[r] > Num2[l]) Sum++;
        if(Num2[r] < Num2[l]) Sum--;

        Swap(l , r);

        printf("%lld\n" ,Sum);
    }
    return 0;
}