【Luogu】每日一题——Day12. P3149 排序 (树状数组 + 逆序对)

链接：P3149 排序 - 洛谷

题目：

思路：

经典搭配了

首先我们来分析以下操作的作用，如果我们选了 a[k]，那么对逆序对有什么影响呢？

①.对于 x y，且 x > a[k]，y <= a[k]

由于 x > a[k]，那么 即使重新排序了 x 的位置也不变，且 y 也依旧是 <= a[i] 的，所以没有影响

②.对于 x y，且 x > a[k]，y > a[k]

由于二者均大于 a[k]，那么相对位置保持不变，依旧没影响

③.对于 x y，且 x <= a[k]，y <= a[k]，x > y

由于二者都小于 a[k]，那么其相对位置就会改变，即变为 y < x，此时不构成逆序对，因此有影响

综上：每次操作其实就是将所有 x <= a[k] 的奉献全删去

所以我们可以利用树状数组求出每个数的奉献，然后用一个前缀和加起来即可，每次查询就用总和减去 sum[a[k]] 即可

注意点：离散化，由于 a 的数据范围很大，所以得离散化一下，防止爆炸；对于 k 我们也有限制，如果之前某次查询存在过一个 k' 有 a[k'] >= a[k]，那么这次的 k 就不需要了，因为之前已经删过了，也就是说我们要存储一个最大的 a[k]

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
int n, m;
pair<int,int> a[300005];
int b[300005];
int tree[300005];
int sum[300005];
int lowbit(int x)
{return x & -x;
}void add(int x)
{for (; x <= n; x += lowbit(x)){tree[x]++;}
}int query(int x)
{int sum = 0;for (;x;x-=lowbit(x)){sum += tree[x];}return sum;
}void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i].first;a[i].second = i;}sort(a+1, a + n+1);int last = -1;int now = 0;for (int i = 1; i <= n; i++){if (a[i].first != last) now++;b[a[i].second] = now;}for (int i = n; i >= 1; i--){sum[b[i]] += query(b[i] - 1);add(b[i]);}for (int i = 1; i <= n; i++){sum[i] += sum[i - 1];}cout << sum[n] << endl;int mx = 0;while (m--){int k;cin >> k;if (b[k] > b[mx]){mx = k;}cout << sum[n] - sum[b[mx]] << endl;}
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}