70 pts RE #2,9,10 悬关求调
查看原帖
70 pts RE #2,9,10 悬关求调
877271
legolas7楼主2024/7/26 21:15
#include <cstdio>
#include <iostream>
#include <algorithm>
//#define int long long
using namespace std;
int n,query[200005][2],num[200005],arr[200005],nowp[200005],t[200005],nu=0,cnt=0;
int lowbit(int x){
	return x&(-x);
}
void add(int x,int k){
	while(x<=nu){
		t[x]+=k;
		x+=lowbit(x);
	}
}
int quadd(int x){
	int ans=0;
	while(x>0){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>query[i][0]>>query[i][1];
		num[++nu]=query[i][0],num[++nu]=query[i][1];
		nowp[query[i][0]]=query[i][0],nowp[query[i][1]]=query[i][1];
	}
	sort(num+1,num+nu+1);
	nu=unique(num+1,num+nu+1)-num-1;
	for(int i=1;i<=nu;i++){
		arr[i]=i;
	}
	for(int i=1;i<=n;i++){
		query[i][0]=lower_bound(num+1,num+nu+1,query[i][0])-num;
		query[i][1]=lower_bound(num+1,num+nu+1,query[i][1])-num;
		swap(arr[query[i][0]],arr[query[i][1]]);
	}
	for(int i=1;i<=nu;i++){
		if(arr[i]+1<=nu) cnt+=quadd(nu)-quadd(arr[i]);
		add(arr[i],1);
	}
	for(int i=1;i<=nu;i++){
		cnt+=abs(num[i]-num[arr[i]])-1-(abs(arr[i]-i)-1);
	}
	cout<<cnt;
	return 0;
}
2024/7/26 21:15
加载中...