BZOJ3192: [JLOI2013]删除物品

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3192

Solution

注意只有两堆而且每次只会移动顶端，所以想到可以把两个顶端拼在一起，分割点就在这个数列里移来移去。
预处理排序一下，然后从大到小选，统计一下区间里未删除数的个数就可以了。
注意long long

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 100005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct data{
    ll v,id;
}a[N];
ll n1,n2,n,last,now,ans,c[N],pos[N];
void add(ll x,ll v){ for (;x<=n;x+=x&-x) c[x]+=v; }
ll get(ll x){
    ll num=0;
    for (;x;x-=x&-x) num+=c[x];
    return num;
}
bool cmp(data x,data y){ return x.v>y.v; }
int main(){
    n1=read(); n2=read(); n=n1+n2;
    for (ll i=1;i<=n1;i++)
        a[n1-i+1].v=read();
    for (ll i=n1+1;i<=n;i++)
        a[i].v=read();
    for (ll i=1;i<=n;i++)
        a[i].id=i,add(i,1);
    sort(a+1,a+1+n,cmp);
    last=n1;
    for (ll i=1;i<=n;i++){
        now=a[i].id;
        if (now>last){
            ans+=get(now-1)-get(last);
            last=now; add(now,-1);
        }else{
            ans+=get(last)-get(now);
            last=now; add(now,-1);
        }
    }
    printf("%lld",ans);
}