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)


相关推荐

  • sql语法:inner join on, left join on, right join on具体用法

    sql语法:inner join on, left join on, right join on具体用法

    2021年11月28日
  • db2数据库sql中计算两个时间字段的差值用到timestampdiff函数

    db2数据库sql中计算两个时间字段的差值用到timestampdiff函数timestampdiff(2,char(timestamp(表.endTime)-timestamp(表.starteTime)))

  • java中voliate的讲解

    java中voliate的讲解Java并发编程:volatile关键字解析  volatile这个关键字可能很多朋友都听说过,或许也都用过。在Java5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果。在Java5之后,volatile关键字才得以重获生机。  volatile关键字虽然从字面上理解起来比较简单,但是要用好不是一件容易的事情。由于volatile关键字是与Java

  • Anaconda中将python 3.7版本退回python 3.6版本

    Anaconda中将python 3.7版本退回python 3.6版本最近在下载tensorflow的时候出现了如下图所示的情况:Couldnotfindaversionthatsatisfiestherequirementtensorflow经过一番查找资料,发现,原来在2019年,TensorFlow还不支持python3.7,所以,迫于无奈,我只能乖乖把python的版本退回到3.6版本,具体步骤也很简单。就是打开anacondap…

  • java CAS详解[通俗易懂]

    java CAS详解[通俗易懂]CAS解释:CAS(compareandswap),比较并交换。可以解决多线程并行情况下使用锁造成性能损耗的一种机制.CAS操作包含三个操作数—内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。一个线程从主内存中得到num值,并对num进行操作,写入值的时候,线程会把第一次取到的num值和主内存中num值进行比较,如果相等,就会将改变后的num写入主内存,如果不相等,则一直循环对比,知道成功为止。CAS

  • 查看oracle端口号「建议收藏」

    查看oracle端口号「建议收藏」我的oracle安装路径:D:/Study/Oracle打开其中的tnsnames.ora此文件中port=“端口号”端口号一般为1521

发表回复

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

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