先算出一个点前头比它大和后头比它小的数量。
每次删点就扔进一个主席树里头，防止造成重复删答案。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, a[100005], p[100005], c[100005], uu, pre[100005], suf[100005];
int lson[5000005], rson[5000005], sum[5000005], orz, rot[100005];
long long ans;
int lowbit(int x){
return x&-x;
}
int getSum(int x){
int tmp=0;
for(int i=x; i; i-=lowbit(i)) tmp += c[i];
return tmp;
}
int query(int o, int l, int r, int x, int y){
if(!o) return 0;
if(l>=x && r<=y) return sum[o];
else{
int mid=(l+r)>>1;
int ans=0;
if(x<=mid) ans += query(lson[o], l, mid, x, y);
if(mid<y) ans += query(rson[o], mid+1, r, x, y);
return ans;
}
}
int queryRange(int uu, int vv, int xx, int yy){//在uu到vv之间有多少数在xx和yy之间
int tmp=0;
for(int i=uu-1; i; i-=lowbit(i))
tmp -= query(rot[i], 1, n, xx, yy);
for(int i=vv; i; i-=lowbit(i))
tmp += query(rot[i], 1, n, xx, yy);
return tmp;
}
void update(int &rt, int l, int r, int x){
if(!rt) rt = ++orz;
sum[rt]++;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) update(lson[rt], l, mid, x);
if(mid<x) update(rson[rt], mid+1, r, x);
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
p[a[i]] = i;
pre[i] = getSum(n) - getSum(a[i]);
ans += pre[i];
for(int j=a[i]; j<=n; j+=lowbit(j)) c[j]++;
}
memset(c, 0, sizeof(c));
for(int i=n; i; i--){
suf[i] = getSum(a[i]-1);
for(int j=a[i]; j<=n; j+=lowbit(j)) c[j]++;
}
while(m--){
printf("%lld
", ans);
scanf("%d", &uu);
uu = p[uu];
ans -= pre[uu] + suf[uu];
ans += queryRange(1, uu-1, a[uu]+1, n);
ans += queryRange(uu+1, n, 1, a[uu]-1);
for(int i=uu; i<=n; i+=lowbit(i))
update(rot[i], 1, n, a[uu]);
}
return 0;
}