Codeforces 540E Infinite Inversions 离散化+树状数组

题意：

有一个无限长序列。进行n次操作，每次把下标为i， j的两个值交换。

最后问你整个序列的逆序数的个数。

思路：

求逆序数分为两部分。一部分是交换过位置的，另一部分是没有交换过的。

第一部分：

用map处理n次操作后的情况。

离散化后，利用树状数组求出交换过的位置的逆序数的个数。

第二部分：

看一个样例：

2

1 6

9 5

得到的序列为6 2 3 4 9 1 7 8 5

首先对于数值6，其下标为1。在区间[1, 6]中，共有6个数。减去该区间中有3个是交换过位置的，则6-3 = 3是数值6对于当前序列所构成的逆序数个数。

对于数值9，下标为5，则在区间[5,9]，共有5个数。减去该区间有3个是换过位置的，则逆序数为2。

对于数值1，其下标为6，在区间[1,6]中，~~~~~也有3个逆序数。

……

问题变为求一个区间的中有几个是交换过位置的，其实只要知道其下标的排名。例如下标1的排名为1，下标5排名2，下标6排名3，下标9排名4。

区间[1,6]，则是3-1+1 = 3；

code：

#include <bits/stdc++.h>
using namespace std;
const int N = 2*1e5+5;
typedef long long LL;
int n;
map <int, int> mp, mp2;
int a[N], rk[N];
int bit[N];
inline int lowbit(int x) {
return x&(-x);
}
void update(int idx, int tn) {
while(idx <= tn) {
bit[idx]++;
idx += lowbit(idx);
}
}
int query(int idx) {
int ret = 0;
while(idx > 0) {
ret += bit[idx];
idx -= lowbit(idx);
}
return ret;
}
bool cmp(int i, int j) {
return a[i] < a[j];
}
void solve() {
int j = 0;
for(auto& i:mp) {
a[++j] = i.second;
mp2[i.second] = j;
}
for(int i = 1;i <= j; i++) rk[i] = i;
sort(rk+1, rk+j+1, cmp);
//count
int n = mp.size();
LL res = 0;
for(int i = 1;i <= n; i++) {
res += query(n) - query(rk[i]);
update(rk[i], n);
}
//cout<<res<<endl;
for(auto &i : mp) {
res += abs(i.second-i.first)-abs(mp2[i.second]-mp2[i.first]);
}
printf("%I64dn", res);
}
int main() {
scanf("%d", &n);
int t, p;
for(int i = 1;i <= n; i++) {
scanf("%d%d", &t, &p);
auto it = mp.find(t);
auto it2 = mp.find(p);
if(it == mp.end() && it2 == mp.end()) {
mp[t] = p;
mp[p] = t;
}
else if(it == mp.end()) {
mp[t] = it2->second;
it2->second = t;
}
else if(it2 == mp.end()) {
mp[p] = it->second;
it->second = p;
}
else
swap(it->second, it2->second);
}
solve();
return 0;
}

最后

以上就是顺心荷花为你收集整理的Codeforces 540E Infinite Inversions 离散化+树状数组的全部内容，希望文章能够帮你解决Codeforces 540E Infinite Inversions 离散化+树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。