題目傳送門
題意簡述
看到題目顯而易見是求逆序對個數，
思路分析
看到資料范圍 \(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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541720.html
標籤：其他
上一篇：LeetCode刷題第八九十周