无尽怎么解释（P2448 无尽的生命）

题目传送门

题意简述

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

思路分析

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












，因此考虑离散化












。

离散化简单介绍

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

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

2 123456789 123456 987654321 123456

首先将所有出现过的数收集起来 


 


 


 


 


 


 

，存进 \(a\) 数组
 
 
 
 
 
 
，并进行排序  
   
   
   
   
   
   ，然后再去重保存进 \(pos\) 数组当中 


 


 


 


 


 


 

。

接下来就可以建立映射关系
 
 
 
 
 
 
。将数值大的数在 \(num\) 数组中用数值小的数代替 

 

 

 

 

 

 
，但各个数之间的大小关系不变

 

 

 

 

 

 

，接下来交换操作先用二分答案在 \(pos\) 数组中检索             ，然后通过映射在 \(num\) 数组中进行交换  
   
   
   
   
   
   。

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

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

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

 

 

 

 

 

 

。

设 \(x<y\),当 \(x\) 和 \(y\) 交换后             。

对于 \(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<iostream> #include<cstdio> #include<cmath> #include<algorithm> using 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<r){ int mid=(l+r)>>1; if(pos[mid]<x) l=mid+1; else 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<<ans<<endl; return 0; }