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

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

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

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107059.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 能用python开发手机软件吗_python numpy

    能用python开发手机软件吗_python numpy有许多人对如何在手机上进行python开发感到很困惑,今天我就给大家推荐几个比较好的python开发软件。一.QPythonOHQPython真的是一款好的软件,它可以支持Python库的安装。内置sl4aserver,简直是一款神器!二.Pydroid3Pydroid3是我目前见过的最好的一款python编辑器,他可以使用pip,甚至可以在手机上掉。…

  • 如何查看 Python 全部内置变量和内置函数?

    如何查看 Python 全部内置变量和内置函数?

    2021年10月21日
  • Python字符串

    从编码和常用字符串函数两方面进行总结1.编码计算机里面,编码方法有很多种,英文的一般用ascii,而中文有unicode,utf-8,gbk,utf-16等等。unicode是utf-8,g

    2021年12月18日
  • Java面试之EJB & Spring[通俗易懂]

    Java面试之EJB & Spring[通俗易懂]Java面试之EJB & Spring

  • java javah_Javah 常见错误记录

    java javah_Javah 常见错误记录测试文件:hello-jni/src/com/example/hellojni/HelloJni.java/***该文件来自AndroidNDKSample-HelloJni,为了便于说明问题,我作了一些修改。*/packagecom.example.hellojni;publicclassHelloJni{publicnativeStringstringFromJNI…

  • String数组初始化

    String数组初始化在java中,声明一个数组时,不能直接限定数组长度,只有在创建实例化对象时,才能对给定数组长度.。如下,1,2,3可以通过编译,4,5不行。而String是Object的子类,所以上述BCF均可定义一个存放50个String类型对象的数组。1.Stringa[]=newString[50];2.Stringb[];3.charc[];4.Stringd[50];5.char…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号