BZOJ-9-3295: [Cqoi2011]动态逆序对[通俗易懂]

全栈程序员-站长 • 2022年4月21日下午12:20 • 未分类 • 阅读 35

大家好，又见面了，我是你们的朋友全栈君。

题意：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