树状数组——BZOJ3192/Luogu3253 [JLOI2013]删除物品

干脆题面以后用HTML写传送门吧

BZOJ传送门

洛谷传送门

我们可以试一下把两个堆（其实这是个栈）拼起来（栈顶拼栈顶）比如样例拼成：5 4 1 2 7 3

然后把栈顶视为一个指针，每次出栈只要移动指针即可

然后区间弹栈信息我们用树状数组维护一下，移动次数就可以算出来了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll lowbit(ll x){return x&-x;}
ll n,m,a[],f[]={},p[];
inline ll erfen(ll x){
    ll l=,r=n+m;
    while(l<=r){
        ll mid=l+r>>;
        if(p[mid]==x)return mid;
        if(p[mid]>x)r=mid-;
        else l=mid+;
    }
}
inline void add(ll x){for(ll i=x;i<=n+m;i+=lowbit(i))f[i]++;}
inline ll sum(ll x){ll ans=;for(ll i=x;i>;i-=lowbit(i))ans+=f[i];return ans;}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=;i<=n;i++)scanf("%lld",&a[n-i+]);
    for(ll i=;i<=m;i++)scanf("%lld",&a[n+i]);
    for(ll i=;i<=n+m;i++)p[i]=a[i];
    sort(p+,p+n+m+);
    for(ll i=;i<=n+m;i++)a[i]=erfen(a[i]);
    memset(p,,sizeof p);
    for(ll i=;i<=n+m;i++)p[a[i]]=i;
    ll w=n,ans=;
    for(ll i=n+m;i;i--){
        if(p[i]==w||p[i]==w+){
            add(p[i]);continue;
        }
        if(p[i]<w)ans+=w-p[i]-sum(w)+sum(p[i]),w=p[i];
        else ans+=p[i]--w-sum(p[i])+sum(w),w=p[i]-;
        add(p[i]);
    }
    printf("%lld",ans);
}