题意:原本是一个从1到n的数组,给你一些对(x,y)让你交换,交换完后求逆序对的个数,这里x和y到1e9
思路,将区间合并为点,再离散化,之后归并,权值线段树,树状数组正常求逆序对即可
#include<cstdio> #include<algorithm> #include<map> #define int long long using namespace std; const int maxn = 100005; struct node{ int x,y; node(int _x,int _y):x(_x),y(_y){ } node(){ } }res[maxn*3]; struct tree{ int l,r,sum; }t[maxn*8]; void build(int l,int r,int k){ t[k].l=l; t[k].r=r; t[k].sum=0; if(l==r){ return ; } int mid=(l+r)/2; build(l,mid,k*2); build(mid+1,r,k*2+1); } void insert(int p,int summ,int k){ if(t[k].l==t[k].r){ t[k].sum+=summ; return; } int mid=(t[k].l+t[k].r)/2; if(p<=mid) insert(p,summ,k*2); else insert(p,summ,k*2+1); t[k].sum=t[k*2].sum+t[k*2+1].sum; } int ans=0; void search(int l,int r,int k){ //printf("%d %d %d %d %d %d\n",t[k].l,t[k].r,t[k].sum,l,r,k); if(l<=t[k].l&&t[k].r<=r){ ans+=t[k].sum; return; } int mid=(t[k].l+t[k].r)/2; if(mid>=l) search(l,r,k*2); if(mid<r) search(l,r,k*2+1); } map<int,int> mp; int x[maxn]; int y[maxn]; int all[maxn]; signed main(){ int k; scanf("%lld",&k); for(int i=0;i<k;i++){ scanf("%lld%lld",&x[i],&y[i]); all[2*i] = x[i]; all[2*i+1] = y[i]; } sort(all,all+2*k); int n = unique(all,all+2*k)-all; //for(int i=0;i<n;i++) printf("%d ",all[i]); int now=0,sum=0; for(int i=0;i<n;i++){ if(all[i]-now>1){ res[sum] = node(sum,all[i]-now-1); sum++; } //printf("%d",sum); res[sum] = node(sum,1); mp[all[i]]=sum; sum++; now = all[i]; } //printf("%d %d %d",mp[2],mp[1],mp[10]); for(int i=0;i<k;i++){ int xx=mp[x[i]]; int yy=mp[y[i]]; node a = res[xx]; res[xx] = res[yy]; res[yy] = a; } build(0,sum-1,1); int las=0; for(int i=sum-1;i>=0;i--){ //printf("a %lld %lld\n",res[i].x,res[i].y); ans=0; search(0,res[i].x,1); ans*=res[i].y; //printf("%d\n",ans); las+=ans; insert(res[i].x,res[i].y,1); } printf("%lld\n",las); return 0; } /* 2 1 15 7 27 */