最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球看点：P2448 无尽的生命

来源：博客园

题目传送门

题意简述

看到题目显而易见是求逆序对个数。


(资料图片仅供参考)

思路分析

看到数据范围 \(x_i,y_i \le 2^{31}-1\)，\(k \le 10^5\)。数据值域大但是个数少，且与数据之间的大小关系有关，因此考虑离散化。

离散化简单介绍

离散化实际就是一种映射，当数据值域过大而个数有限时，可以尝试离散化。

具体过程以此题为例。假设给出这么一组数据

2123456789 123456987654321 123456

首先将所有出现过的数收集起来，存进 \(a\) 数组，并进行排序，然后再去重保存进 \(pos\) 数组当中。

接下来就可以建立映射关系。将数值大的数在 \(num\) 数组中用数值小的数代替，但各个数之间的大小关系不变，接下来交换操作先用二分答案在 \(pos\) 数组中检索，然后通过映射在 \(num\) 数组中进行交换。

最终被交换过的数之间的逆序对在 \(num\) 数组中求即可。

被交换的数与未被交换的数之间的逆序对

考虑每个被交换的数对答案的贡献。

设 \(x

对于 \(x\) 来说, \(x \sim y\) 之间所有未被交换的数都比 \(x\) 大，形成逆序对。

对于 \(y\) 来说，\(x \sim y\) 之间所有未被交换的数都比 \(y\) 小，形成逆序对。

逆序对个数都为\(x \sim y\) 之间所有未被交换的数。

温馨提示：以下主要为代码实现讲解，本质思想同上。

对于交换过后的 \(num\) 数组，\(num_i\) 表示的是位置 \(pos_i\) 上当前所在的数在 \(num\) 数组中对应的数。记数 \(x\) 为位置 \(pos_i\) 上当前所在的数。

\(pos_{num_i}\) 表示数 \(x\) 现在所在的位置。

\(pos_i\) 表示数 \(x\) 原来在的位置。

\(\left\vert pos_i-pos_{num_i}-1\right\vert\) 表示两个位置间所有的数。

\(\left\vert num_i-i-1\right\vert\) 表示两个位置间所有被交换过的数。

因此所有未被交换的数就为 \(\left\vert pos_i-pos_{num_i}-1\right\vert - \left\vert num_i-i-1\right\vert\)。

code

#include#include#include#includeusing namespace std;struct A{int x,y;}a[100005];int k,pos[200005],num[200005],cnt,len;int t[100005];void add(int x){for(;x<=len;x+=(x&-x)) t[x]+=1;}long long sum(int x){long long ans=0;for(;x;x-=(x&-x)) ans+=t[x];return ans;}int find(int x){int l=1,r=len;while(l>1;if(pos[mid]x) r=mid-1;else return mid;}} int main(){scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d%d",&a[i].x,&a[i].y);num[++cnt]=a[i].x;num[++cnt]=a[i].y;}sort(num+1,num+cnt+1);for(int i=1;i<=cnt;i++){if(num[i]==num[i-1]) continue;pos[++len]=num[i];}for(int i=1;i<=len;i++) num[i]=i;for(int i=1;i<=k;i++){int pos1=find(a[i].x);int pos2=find(a[i].y);swap(num[pos1],num[pos2]);}long long ans=0;for(int i=len;i>=1;i--){add(num[i]);ans+=sum(num[i]-1);ans+=abs(pos[num[i]]-pos[i]-1)-abs(num[i]-i-1); } cout<

关键词： 简单介绍 温馨提示 显而易见