#主席树、二分、树状数组#洛谷 3157 JZOJ 2287 动态逆序对

本文主要是介绍#主席树、二分、树状数组#洛谷 3157 JZOJ 2287 动态逆序对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

分析

首先如果不带修改操作那么就是一道主席树题目，但是既然有了修改，那么还必须用上树状数组维护，时间复杂度 $O(nlog^2n)$

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=100001;
int xa[N],xb[N],w[N*240],ls[N*240],rs[N*240],pos[N],n,m,cnt,rt[N]; long long ans;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(long long ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline void update(int &rt,int l,int r,int x,int y){if (!rt) rt=++cnt; w[rt]+=y; if (l==r) return; rr int mid=(l+r)>>1;if (x<=mid) update(ls[rt],l,mid,x,y);else update(rs[rt],mid+1,r,x,y);
}
inline signed query(int l,int r,int x,int type){rr int ca=0,cb=0,sum=0;for (rr int i=l-1;i;i-=-i&i) xa[++ca]=rt[i];for (rr int i=r;i;i-=-i&i) xb[++cb]=rt[i];for (rr int l=1,r=n;l<r;){rr int mid=(l+r)>>1;if (x>mid){if (type){for (rr int i=1;i<=ca;++i) sum-=w[ls[xa[i]]];for (rr int i=1;i<=cb;++i) sum+=w[ls[xb[i]]];}for (rr int i=1;i<=ca;++i) xa[i]=rs[xa[i]];for (rr int i=1;i<=cb;++i) xb[i]=rs[xb[i]];l=mid+1;}else{if (!type){for (rr int i=1;i<=ca;++i) sum-=w[rs[xa[i]]];for (rr int i=1;i<=cb;++i) sum+=w[rs[xb[i]]];}for (rr int i=1;i<=ca;++i) xa[i]=ls[xa[i]];for (rr int i=1;i<=cb;++i) xb[i]=ls[xb[i]];			r=mid;}}return sum;
}
signed main(){n=iut(); m=iut();for (rr int i=1,x;i<=n;++i){pos[x=iut()]=i,ans+=query(1,i-1,x,0);for (rr int j=i;j<=n;j+=-j&j) update(rt[j],1,n,x,1);}print(ans),putchar(10);for (rr int i=1;i<m;++i){rr int x=iut();ans-=query(1,pos[x]-1,x,0)+query(pos[x]+1,n,x,1);print(ans),putchar(10);for (rr int j=pos[x];j<=n;j+=-j&j) update(rt[j],1,n,x,-1);}return 0;
}