题目链接

题面：

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
#define y1 yy
using namespace std;
const int maxn=100100;
int pre[maxn],nt[maxn],sum[maxn],id[maxn],val[maxn];
int n,m;
ll ans;
void add(int x)
{
    for(;x<maxn;x+=(x&(-x)))
        sum[x]++;
}

int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&(-x)))
        ans+=sum[x];
    return ans;
}

struct node
{
    int lc,rc;
    int sum;
}t[maxn*400];
int root[maxn],cnt;

int newnode(void)
{
    cnt++;
    t[cnt].lc=t[cnt].rc=t[cnt].sum=0;
    return cnt;
}

int change(int p,int l,int r,int pos)
{
    if(!p) p=newnode();
    if(l==r)
    {
        t[p].sum=1;
        return p;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) t[p].lc=change(t[p].lc,l,mid,pos);
    else t[p].rc=change(t[p].rc,mid+1,r,pos);
    t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
    return p;
}

int ask(int p,int pl,int pr,int l,int r)
{
    if(pl>=l&&pr<=r) return t[p].sum;
    int mid=(pl+pr)>>1;
    int ans=0;
    if(l<=mid) ans+=ask(t[p].lc,pl,mid,l,r);
    if(r>mid) ans+=ask(t[p].rc,mid+1,pr,l,r);
    return ans;
}

//动态开点线段树维护了对应树状数组区间的值
ll ask(int pl,int pr,int l,int r)
{
    if(l>r) return 0;
    ll ans=0;
    for(;pr;pr-=(pr&(-pr)))
        ans=ans+ask(root[pr],1,n,l,r);
    for(;pl;pl-=(pl&(-pl)))
        ans=ans-ask(root[pl],1,n,l,r);
    return ans;
}

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        id[val[i]]=i;
        pre[i]=ask(n)-ask(val[i]);//这个数前面比他大的数
        ans=ans+pre[i];
        add(val[i]);
    }
    memset(sum,0,sizeof(sum));
    for(int i=n;i>=1;i--)
    {
        nt[i]=ask(val[i]-1);//这个数后面比他小的数
        add(val[i]);
    }

    int x;
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans);
        scanf("%d",&x);
        int now=id[x];
        //pre[now]-ask(0,now,x+1,n) 为真实的前面比当前大的值。
        //其中pre[now]为初始时前面比其大的值的数量，ask(0,now,x+1,n) 为已经删掉了的数量
        ans=ans-(pre[now]-ask(0,now,x+1,n))-(nt[now]-ask(now,n,1,x-1));
        for(;now<maxn;now+=(now&(-now)))
            root[now]=change(root[now],1,n,x);//对于now之后的数据来说，表示x已经被删除掉了
    }

    return 0;
}