逆序对0pts求调(双倍经验已过)
查看原帖
逆序对0pts求调(双倍经验已过)
755759
zhujiangyuan楼主2024/4/14 15:41
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) x&-x
using namespace std;
const int N=4e5+10;
int n,tot;
LL x[N],y[N],id[N],ans,c[N];
struct lx{
	LL f,len;
}l[N];
map<int,int>mp;
void add(int x,int y){
	int xx=x;
	for(;x<=tot;x+=lowbit(x)) c[x]+=y*l[mp[xx]].len;
}
LL ask(int x){
	LL sum=0;
	for(;x;x-=lowbit(x)) sum+=c[x];
	return sum;
}
int main()
{
//	freopen("maxnum.in","r",stdin);
//	freopen("maxnum.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
		if(!mp[x[i]]) mp[x[i]]=x[i];
		if(!mp[y[i]]) mp[y[i]]=y[i];
		swap(mp[x[i]],mp[y[i]]);
	}
	for(int i=1;i<=n;i++) id[i]=mp[x[i]],id[n+i]=mp[y[i]];
	sort(id+1,id+n*2+1);
	int m=unique(id+1,id+n*2+1)-id-1;
	mp.clear();
	for(int i=1;i<=m;i++)
	{
		if(id[i]-id[i-1]==1) goto A;
		l[++tot].f=tot;l[tot].len=id[i]-id[i-1]-1;
		A:
		l[++tot].f=tot;l[tot].len=1;mp[id[i]]=tot;
	}
	for(int i=1;i<=n;i++) swap(l[mp[x[i]]],l[mp[y[i]]]);
	mp.clear();
	for(int i=1;i<=tot;i++) mp[l[i].f]=i;
	for(int i=tot;i>=1;i--)
	{
		ans+=ask(l[i].f)*l[i].len;
		add(l[i].f,1);
	}
	printf("%lld\n",ans);
	return 0;
}
//https://www.luogu.com.cn/problem/P2448
2024/4/14 15:41
加载中...