Hdu 5193 Go to movies Ⅱ(带删除数插入数的逆序数对,块状链表)

acm_fighting · · 2164 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

传送门:Hdu 5193 Go to movies Ⅱ


题意:
有n个人站成一排,每个人的身高为Hi。每次有人加入或者有人离开,就要判断有多少人站反了(i < j&&Hi>Hj)
第一行n,m,接下来n个整数(n,m<=2e4)
接下来m行,
0 x y 表示有一个身高为y的人插在x后面,x=0表示插在最前面。(1≤y≤n)
1 x 表示第x个人(从左到右)离开。


思路:摘自题解http://bestcoder.hdu.edu.cn/solutions.php?page=12
添加或者删除一个元素时,维护逆序对时,需要知道在它之前有多少个数比它大,在它之后有多少个数比他小。有下标和权值两个维度,可以使用两个数据结构嵌套。题目中n=20000,范围不大,外层可以使用分块维护下标,这样添加和删除元素的时候,
也很方便,直接暴力。查找权值个数时,使用树状数组比较方便。内层通过树状数组维护权值。设每块的大小为S,那么删除或者添加元素时,维护逆序对数的复杂度是O(S+P∗logn),S是块内直接暴力更新逆序对的代价,
​P/S∗logn在前面块找比它大和在后面块中找比它小的代价,P表示当前元素的个数。为了使这两部分复杂度尽量均摊让S=P/S∗logn,S取根号Plogn
​。直接通过分块暴力添加和删除时,块的大小会退化,需要重构,。重构一次的复杂度是S*logn, 总的重构复杂度是,与添加和删除总的复杂度一至。因此整个问题的复杂度为O(m√nlogn).


#include<bits/stdc++.h>
using namespace std;
const int maxn=20010;
const int MAX_S=1050;
int ans,tot,n;

void add(int *c,int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=(x&-x);
    }
}

int sum(int *c,int x){
    int ret=0;
    while(x>0){
        ret+=c[x];
        x-=(x&-x);
    }
    return ret;
}

struct node_t{
    int num[MAX_S+10],sz,c[maxn],next,pre;

    void init(){
        memset(c,0,sizeof(c));
        sz=0;
        pre=0;
        next=0;
    }
}b[310];

int get_pos(int &x){
    int i=1;
    while(b[i].sz<x&&b[i].next)
        x-=b[i].sz,i=b[i].next;
    return i;
}

int cal(int x){
    int ret=0;
    int id=get_pos(x);
    for(int i=1;i<x;i++)    
        if(b[id].num[i]>b[id].num[x])
            ret++;
    for(int i=x+1;i<=b[id].sz;i++)
        if(b[id].num[i]<b[id].num[x])
            ret++;
    for(int i=1;i!=id;i=b[i].next)
        ret+=sum(b[i].c,n)-sum(b[i].c,b[id].num[x]);
    for(int i=b[id].next;i!=0;i=b[i].next)
        ret+=sum(b[i].c,b[id].num[x]-1);
    return ret;
}

int flag;

void ins(int x){
    int y=x;
    if(flag==0){    //是不是第一个元素  
        b[1].init();
        scanf("%d",&b[1].num[++b[1].sz]);
        add(b[1].c,b[1].num[1],1);
        flag=1;
        return ;
    }
    int id=get_pos(x);      //id表示在哪一块中
    if(b[id].sz==MAX_S){    //块重构
        b[++tot].init(),b[id].sz++;
        int cnt=0;
        for(int i=b[id].sz;i>x;i--)
            b[id].num[i]=b[id].num[i-1];
        scanf("%d",&b[id].num[x]);
        add(b[id].c,b[id].num[x],1);
        int len=b[id].sz/2;
        for(int i=len+1;i<=b[id].sz;i++){
            b[tot].num[++cnt]=b[id].num[i];
            add(b[tot].c,b[id].num[i],1);
            add(b[id].c,b[id].num[i],-1);
        }
        b[tot].sz=cnt,b[tot].next=b[id].next;
        b[id].next=tot,b[id].sz=len;
        b[tot].pre=id;
    }
    else{
        b[id].sz++;
        for(int i=b[id].sz;i>x;i--)
            b[id].num[i]=b[id].num[i-1];
        scanf("%d",&b[id].num[x]);
        add(b[id].c,b[id].num[x],1);
    }
    ans+=cal(y);
}

void del(int x){
    ans-=cal(x);
    int id=get_pos(x);
    add(b[id].c,b[id].num[x],-1);
    for(int i=x+1;i<=b[id].sz;i++)
        b[id].num[i-1]=b[id].num[i];
    b[id].sz--;
    if(b[id].sz==0){    //删除块  
        int pre=b[id].pre,net=b[id].next;
        b[net].pre=pre;
        b[pre].next=net;
    }
}

int main(){
    int m,op,x,y;
    while(~scanf("%d%d",&n,&m)){
        ans=0,tot=1,b[1].sz=0,flag=0;
        for(int i=1;i<=n;i++)
            ins(i);
        for(int i=1;i<=m;i++){
            scanf("%d",&op);
            if(op==0){
                scanf("%d",&x);
                ins(x+1);
            }
            else{
                scanf("%d",&x);
                del(x);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:acm_fighting

查看原文:Hdu 5193 Go to movies Ⅱ(带删除数插入数的逆序数对,块状链表)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

2164 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传