P3253

Aryper · 2021-08-14 12:10:34 · 个人记录

[JLOI2013]删除物品

一开始我们可以想象，每次删除的数是固定的，所以说可以通过模拟唯一确定解法。

我们可以先排序并用链表连接最大值，次大值，次次大值等等。

然后考虑将两个序列的堆顶相接，显然整个序列在堆顶发生变化时并不变化，因此只要变化堆顶即可，这是一个相当巧妙的转化思想。

那么我们就可以使用树状数组，完成每次的步数计算。

时间复杂度 O(n\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e5;

struct node{
    ll v,id;
}a[N+5];

ll n1,n2,top,ans,st;

ll c[N+5],nxt[N+5];

void add(ll x,ll y) {
    for(;x<=n1+n2;x+=x&-x) c[x]+=y;
}

ll ask(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

bool cmp(node x,node y) {
    return x.v>y.v;
}

bool cmp_(node x,node y) {
    return x.id<y.id;
}

int main() {

    n1=read();n2=read();

    for(ll i=n1;i>=1;i--) {
        a[i].v=read();add(i,1);
        a[i].id=i;
    }
    for(ll i=n1+1;i<=n1+n2;i++) {
        a[i].v=read();add(i,1);
        a[i].id=i;
    }

    sort(a+1,a+n1+n2+1,cmp);st=a[1].id;
    for(ll i=1;i<=n1+n2;i++) {
        nxt[a[i].id]=a[i+1].id;
    }
    sort(a+1,a+n1+n2+1,cmp_);
    top=n1;

    for(ll i=st;i;i=nxt[i]) {
        if(i<=top) {
            ans+=ask(top)-ask(i);
            top=i;add(i,-1);
        }
        else {
            ans+=ask(i-1)-ask(top);
            top=i-1;add(i,-1);
        }
    }

    write(ans);

    return 0;
}