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;
}