题目描述

给定 $1$ ~ $n$ 的排列 $p_i$，接下来又有 $m$ 次操作，操作共有两种：

1. 交换操作：给定 $x$，将当前排列中的第 $x$ 个数与第 $x + 1$ 个数交换位置。
2. 询问操作：给定 $k$，请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。

对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下：

for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])

c++代码如下（我补充的，我只会c++）

for (int i = 1; i < n; i ++ )
    if (p[i] > p[i + 1])
        swap(p[i], p[i + 1])
//码风不好，勿喷

输入格式

第一行两个整数 $n,m$，表示排列长度与操作个数。

第二行 $n$ 个整数表示排列 $p_i$。

接下来 $m$ 行每行两个整数 $t_i,c_i$，描述一次操作：若 $t_i = 1$，则本次操作是交换操作，$x = c_i$；若 $t_i = 2$，则本次操作是询问操作，$k = c_i$。

输出格式

对于每次询问操作输出一行一个整数表示答案。

数据范围

对于测试点 $1$ ~ $2$：$n,m \leq 100$。

对于测试点 $3$ ~ $4$：$n,m \leq 2000$。

对于测试点 $5$ ~ $6$：交换操作个数不超过 $100$。

对于所有测试点：$2 \leq n,m \leq 2 \times 10^5$，$t_i \in \{1,2\}$，$1 \leq x < n$，$0 \leq k < 2^{31}$。

输入样例

3 6
1 2 3
2 0
1 1
1 2
2 0
2 1
2 2

输出样例

0
2
1
0

算法 找规律+树状数组优化

思路：

对于数列 $q[N]$，构造数列 $b[N]$，其中 $b[i]$ 表示所有满足 $j<i$ 且 $q[j] \> q[i]$ 的 $j$ 的数量。

每次冒泡之后，数列 $n$ 中所有大于 $1$ 的元素减一，并全部向左移一位。

//求b[N]的代码（暴力）O(n^2)
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j < i; j ++ )
        if (q[j] > q[i])
            b[i] ++ ;

举个例子：

若 $q[10] = \{7,4,8,3,1,6,2,5,10,9\}$
则 $b[10] = \{0,1,0,3,4,2,5,3,0,1\}$

第一次冒泡后：

$q[10] = \{4,7,3,1,6,2,5,8,9,10\}$
$b[10] = \{0,0,2,3,1,4,2,0,0,0\}$

第二次冒泡后：

$q[10] = \{4,3,1,6,2,5,7,8,9,10\}$
$b[10] = \{0,1,2,0,3,1,0,0,0,0\}$

第三次：

$q[10] = \{3,1,4,2,5,6,7,8,9,10\}$
$b[10] = \{0,1,0,2,0,0,0,0,0,0\}$

第四次：

$q[10] = \{1,3,2,4,5,6,7,8,9,10\}$
$b[10] = \{0,0,1,0,0,0,0,0,0,0\}$

第五次：

$q[10] = \{1,2,3,4,5,6,7,8,9,10\}$
$b[10] = \{0,0,0,0,0,0,0,0,0,0\}$

结束

如果还没懂的话，再举个例子：

若 $q[5] = \{5,4,3,2,1\}$
则 $b[5] = \{0,1,2,3,4\}$

第一次冒泡：

$q[5] = \{4,3,2,1,5\}$
$b[5] = \{0,1,2,3,0\}$

第二次冒泡：

$q[5] = \{3,2,1,4,5\}$
$b[5] = \{0,1,2,0,0\}$

第三次：

$q[5] = \{2,1,3,4,5\}$
$b[5] = \{0,1,0,0,0\}$

第四次：

$q[5] = \{1,2,3,4,5\}$
$b[5] = \{0,0,0,0,0\}$

结束

显然，第k次冒泡之后的总逆序对就是第 $k$ 次冒泡之后的 $b[k]$，但如果暴力求数列 $b$ 的话，时间复杂度仍是 $O(n^2)$然后像本蒟蒻一样40分，我们可以用树状数组进行维护，可将总时间复杂度降至$O(nlogn)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

const int N=200010;

int n,m;
int temp;
int data[N];
int b[N],d[N];
long long c[N],ans;

void update(int x, long long u)
{
    while(x <= n)
        c[x] += u,
        x += x & -x;
}
long long getsum(int x)
{
    long long res=0;
    while (x)
        res += c[x],
        x -= x & -x;
    return res;
}
int main()
{
    scanf("%d %d\n", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d",&data[i]);
        b[i] = i - 1 - getsum(data[i]);
        ans += b[i], d[b[i]] ++ ;
        update(data[i], 1);
    }
    std::memset(c, 0, sizeof c);
    update(1, ans);
    for (int i = 0; i < n; i ++ )
        temp += d[i],
        update(i + 2, temp - n);
    while (m -- )
    {
        short op;
        int x;
        scanf("\n%hd %d", &op, &x);
        x=std::min(x,n-1);
        if(op^1)printf("%lld\n", getsum(x + 1));
        else
            if (data[x] < data[x + 1])
            {
                std::swap(data[x], data[x + 1]);
                std::swap(b[x], b[x + 1]); 
                update(1, 1);
                update( ++ b[x + 1] + 1, -1);
            }
            else
            {
                std::swap(data[x], data[x + 1]);
                std::swap(b[x], b[x + 1]);
                update(1, -1);
                update(b[x] -- + 1, 1);
            }
    }
    return 0;
}
//好长啊

懒得注释了，勿喷