P2448 RE 前8个点,AC#9#10,求助

回复帖子

@chenyifan623  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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。