本文主要是介绍Codeforces Round #301 (Div. 2) E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
E Infinite Inversions
一个无穷的数列1,2,3......进行n（n<=100000）次swap操作，问操作后的数列有多少逆序对。
考虑到交换的数可能比较大，但是交换的次数相对少，可以用离散化解决。离散化以后，模拟一下操作。然后逆序对可以分为两部分考虑，一部分是被交换了的数之间的逆序对，另一部分是被交换的数与没交换的数之间的逆序对。在这个数列中，每个数是唯一的，用离散化后的值借助树状数组可以得出被交换了的数之间的逆序对（就是经典的逆序对求法）。除了用map存每个被交换的数的“名次”外，我们再开一个数组，根据“名次”可以找到相应的数，这样就可以利用名次计算出被交换的数与没交换的数之间的逆序对。具体见代码。
感觉自己实力有所增强了，div2的场基本上都能出D，E也能赛后不借助外力A掉。
#include <bits/stdc++.h>
using namespace std; #define ll long long
const int maxn=100010;int a[maxn];
int b[maxn];
int c[maxn*2];
int _mp[maxn*2];int cnt;
int cc[maxn*2];
int lowbit(int x){return x&(-x);
}void update(int pos){while(pos<=cnt){cc[pos]++;pos+=lowbit(pos);}
}int query(int pos){int re=0;while(pos){re+=cc[pos];pos-=lowbit(pos);}return re;
}int main(){int n;cin>>n;map<int,int> mp;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);mp[a[i]]=1;mp[b[i]]=1;}cnt=0;for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){it->second=++cnt;_mp[cnt]=it->first;}ll ans=0;for(int i=1;i<=cnt;i++){c[i]=i;}for(int i=1;i<=n;i++){swap(c[ mp[a[i]] ],c[ mp[b[i]] ]);}for(int i=1;i<=cnt;i++){ans+=c[i]-1-query(c[i]-1);//当前数 int num=_mp[ c[i] ];//交换前数 int ori=_mp[ i ]; //前面未被交换的数中有tmp1个大于当前数 int tmp1=ori-num-(mp[ori]-mp[num]);//后面未被交换的数中有tmp2个小于当前数 int tmp2=num-ori-(mp[num]-mp[ori]);if( tmp1>0 ){ans+=tmp1;}if( tmp2>0 ){ans+=tmp2;}update(c[i]);}cout<<ans<<endl;return 0;
}这篇关于Codeforces Round #301 (Div. 2) E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
