大家好，又见面了，我是你们的朋友全栈君。
题意：N个数的排列，M次操作，每次求当前的逆序对数量并删掉一个数
思路 :动态说的很到位。hiahia … 最初一直没想明白为什么 大佬的cdq 中统计了两次。
先定义 给出的删除的点的 t 值依次是N,N-1,N-2…（越先删除的视为越后插入的）
注意不在询问范围内的点的t值可以任意设置，为了方便按照x从左到右。给没有删除的点 t 值递增赋值 。
我们求的就是按顺序插入每一个数时，这个数左边比它大的、右边比它小的分别有多少个。
形式化地，对一个点 ( t0,x0,y0)，求出满足 t < t0,x < x0,y > y 0 的点的个数记为与 满足 t < t0, x > x0,y < y0的点的个数
这就是 cdq 里面进行的两个统计步骤，很容易想到的是 t < t0,x < x0,y > y 0 这符合逆序定义，
但是与二维 逆序数对不同的是 二维逆序数对，没有 t 值 我们只需要 记录一个总数，考虑每个数前面比它大的即可。
但是，这里不同这是有了 t 值 是动态的一个一个插入值， 不能只考虑 左边比它大的了，还需要考虑 加入了
这个值后 它右边比它小的值 。
#include<bits/stdc++.h>
using namespace std;
#define maxn 234567
#define ll long long
int n,m,cnt,pos[maxn];
int tree[maxn],x,b[maxn];
ll ans[maxn];
struct node
{
int x,y,t;
} a[maxn];
int lowbit(int x)
{
return x&(-x);
}
bool cp1(node a,node b)
{
return a.t<b.t;
}
bool cp(node a,node b)
{
return a.x<b.x;
}
void add(int p,int d)
{
while(p<=123456)
{
tree[p]+=d;
p+=lowbit(p);
}
}
int query(int p)
{
int ret=0;
while(p>0)
{
ret+=tree[p];
p-=lowbit(p);
}
return ret;
}
void cdq(int l,int r)
{
if(l>=r)return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(a+l,a+mid+1,cp);
sort(a+1+mid,a+1+r,cp);
int i=l,j=mid+1;
for(; j<=r; j++)
{
while(a[i].x<a[j].x&&i<=mid)
{
add(a[i].y,1);
i++;
}
ans[a[j].t]+=query(123456)-query(a[j].y);
}
for(j=l; j<i; j++)
add(a[j].y,-1);
i=mid,j=r;
for(; j>mid; j--)
{
while(a[i].x>a[j].x&&i>=l)
{
add(a[i].y,1);
i--;
}
ans[a[j].t]+=query(a[j].y-1);
}
for(j=mid; j>i; j--)
add(a[j].y,-1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
a[i].t=0;
scanf("%d",&a[i].y);
pos[a[i].y]=a[i].x=i;
}
cnt=n;
for(int i=1; i<=m; i++)
{
scanf("%d",&x);
a[pos[x]].t=cnt--;
b[i]=x;
}
cnt=1;
for(int i=1; i<=n; i++)
if(!a[i].t)a[i].t=cnt++;
sort(a+1,a+n+1,cp1);
cdq(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/SDUTNING/p/10267558.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107059.html原文链接：https://javaforall.net
