題目:https://www.luogu.org/problemnew/show/3157

---

題解:

1.對于靜態的逆序對可以用樹狀數組做

2.我們為了方便可以把刪除當成增加,可以化動為靜

3.找到三維:時間,位置,大小

然后CDQ分治

#include<cstdio> #include<algorithm> #include<cstring> #define N 200010 typedef long long ll; using namespace std; ll n,m,ans[N],a[N],t[N]; struct point {ll t,pos,val;bool operator < (const point &x)const{return val>x.val;} }p[N],tmp[N]; bool cmp(const point &x,const point &y) {return x.t<y.t;} void add(int x,int k) {for (;x<N;x+=x&-x) t[x]+=k; } ll query(int x) {ll ret=0;for (;x;x-=x&-x) ret+=t[x];return ret; } void solve(int l,int r) {if (l==r) return ;int mid=l+r>>1,i=l,j=mid+1;solve(l,mid),solve(mid+1,r);for (int k=l;k<=r;k++)if (i<=mid && (p[i]<p[j] || j>r))tmp[k]=p[i++];else tmp[k]=p[j++];for (i=l;i<=r;i++) {p[i]=tmp[i];if (p[i].t<=mid) add(p[i].pos,1);else ans[p[i].t]+=query(p[i].pos);}for (i=l;i<=r;i++) if (p[i].t<=mid) add(p[i].pos,-1);for (i=r;i>=l;i--)if (p[i].t<=mid) add(p[i].pos,1);else ans[p[i].t]+=query(n)-query(p[i].pos);for (i=l;i<=r;i++)if (p[i].t<=mid) add(p[i].pos,-1);} int main() {scanf("%lld%lld",&n,&m);for (int i=1,x;i<=n;i++)scanf("%lld",&x),p[x].val=x,p[x].pos=i;for (int i=0,x;i<m;i++)scanf("%lld",&x),p[x].t=n-i;for (int i=1,cnt=0;i<=n;i++)if (!p[i].t) p[i].t=++cnt;sort(p+1,p+n+1,cmp);solve(1,n);for(int i=1;i<=n;i++)ans[i]+=ans[i-1];for(int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);return 0; }

　　

?

轉載于:https://www.cnblogs.com/mrsheep/p/8093738.html

總結

以上是生活随笔為你收集整理的洛谷 P3157 [CQOI2011]动态逆序对 | CDQ分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。