P2448 RE 前8个点,AC#9#10,求助
  • 板块学术版
  • 楼主cyfff
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/22 10:08
  • 上次更新2023/11/5 07:33:01
查看原帖
P2448 RE 前8个点,AC#9#10,求助
181437
cyfff楼主2020/11/22 10:08
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,tr[2000005],a[2000005],hs[2000005],cnt,b[2000005],ans;
LL rd(){
	register LL res=0,f=1;register char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<1)+(res<<3)+ch-48;
	return res*f;
}
LL fd(LL x){
    LL l=1,r=n*2,md;
    while(l<=r){
        md=(l+r)>>1;
        if(hs[md]==x)return md;
        else if(hs[md]<x)l=md+1; 
		else r=md-1;
    }
    return r;
}
void upd(LL x,LL y){for(;x<=cnt;x+=x&-x)tr[x]+=y;}
LL qr(LL x){LL an=0;for(;x;x-=x&-x)an+=tr[x];return an;}
LL x[2000005],y[2000005],i,p,vl,m;
int main(){
	n=rd();
	for(i=1;i<=n;++i)a[++m]=x[i]=rd(),a[++m]=y[i]=rd();
	sort(a+1,a+1+m);
	for(i=1;i<=m;++i)if(a[i]!=a[i-1])hs[++cnt]=a[i];
	for(i=1;i<=cnt;++i)b[i]=i;
	for(i=1;i<=n;++i){
		x[i]=fd(x[i]);y[i]=fd(y[i]);
		swap(b[x[i]],b[y[i]]);
	}
	for(upd(b[cnt],1),i=cnt-1;i;--i){
		vl=hs[i+1]-hs[i]-1;
		ans+=vl*qr(i);upd(i,vl);
		ans+=qr(b[i]-1);upd(b[i],1);
	}
	printf("%lld",ans);
	return 0;
}
2020/11/22 10:08
加载中...