网站建设支付,网站模板有后台,wordpress新建页面关于我们,广州软件定制公司洛谷P1774
题目#xff1a;登录 - Luogu Spilopelia
为什么最小的交换次数就是逆序对的个数#xff0c;请看相关证明
1、归并排序
// 归并排序解法
#includeiostream
#includecstring
#includealgorithm
using namespace std;
con…洛谷P1774
题目登录 - Luogu Spilopelia
为什么最小的交换次数就是逆序对的个数请看相关证明
1、归并排序
// 归并排序解法
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 5e5 10;
typedef long long ll;
int a[N],b[N];
int n;
ll ans 0;
void merge(int l,int r)
{if(lr) return;int mid l r 1;merge(l,mid),merge(mid 1,r);int k 0,i l,j mid 1;while(imidjr)if(a[i]a[j]) b[k] a[i];else {ans mid - i 1;b[k] a[j];}while(imid)b[k] a[i];while(jr) b[k] a[j];for(int i l,j 0;ir;i,j) a[i] b[j];
}
int main()
{scanf(%d,n);for(int i 0;in;i) scanf(%d,a[i]);merge(0,n-1);printf(%lld\n,ans);return 0;
}
2、树状数组
进行离散化之后赋予排名排名的数字越小则说明数字越小相同值的话先出现的排名数字越小。然后可以正着也可以反着进行求
// 树状数组的解法
#includeiostream
#includealgorithm
#includecstring
using namespace std;
typedef long long ll;
const int N 5e5 10;
int tr[N],ranks[N];
int n;
struct Node
{int num,id;
}a[N];
bool cmp(Node a,Node b)
{if(a.num!b.num)return a.num b.num;return a.id b.id;
}
int lowbit(int x){return x -x;
}
void add(int x,int v)
{for(int i x;in;ilowbit(i))tr[i] v;
}
ll query(int x)
{ll res 0;for(int i x;i;i-lowbit(i))res tr[i];return res;
}int main()
{scanf(%d,n);for(int i 1;in;i) {scanf(%d,a[i].num);a[i].id i;}sort(a 1,a 1 n,cmp);for(int i 1;in;i) ranks[a[i].id] i;ll ans 0;// 正向求解 for(int i 1;in;i){add(ranks[i],1);ans i - query(ranks[i]);}/*反向求解 for(int i n;i1;i--){add(ranks[i],1);ans query(ranks[i]-1);}*/printf(%lld,ans);return 0;
}
3、线段树
离散化之后对每一个排名
比如说当求到ranks[3] 的时候看看在它之前有没有 4 - ----n的数字出现询问以后把update(ranks[3],1)加到线段树里面去代表贡献了1.
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 1e6;
int ranks[N];
int sum[4*N];
struct Node
{int num,id;
}a[N];
typedef long long ll;
bool cmp(Node a,Node b)
{if(a.num!b.num) return a.num b.num;return a.id b.id;
}
void pushup(int x)
{sum[x] sum[x*2] sum[x*21];
}
void build(int l,int r,int x)
{if(l r) {sum[x] 0;return;}int mid l r 1;build(l,mid,x*2);build(mid 1,r,x*2 1);pushup(x);
}
void update(int pos,int l,int r,int x,int v)
{if(l r){sum[x] v;return;}int mid l r 1;if(posmid) update(pos,l,mid,x*2,v);else update(pos,mid 1,r,x*21,v);pushup(x);
}
long long query(int pl,int pr,int l,int r,int x)
{if(pllrpr) return sum[x];int mid l r1;long long ans 0;if(plmid) ans query(pl,pr,l,mid,x*2);if(prmid) ans query(pl,pr,mid 1,r,x*21);return ans;
}
int main()
{int n;scanf(%d,n);build(1,n,1);for(int i 1;in;i){scanf(%d,a[i].num);a[i].id i;}sort(a1,a1n,cmp);for(int i 1;in;i)ranks[a[i].id] i;ll ans 0;n;for(int i 1;in-1;i){ans query(ranks[i]1,n,1,n,1);update(ranks[i],1,n,1,1);}printf(%lld,ans);return 0;
}
