首先思路是很清晰的，该删的数从小到大开始删，这样在删到当前数的时候，比当前数小的数可以尽量少，能选的区间自然就更大了。
考虑如何实现，维护一个 set，从小到大遍历每个数，若当前数不需要被删除，就将其下标加入 set 中；若需要删除就在 set 中二分出恰好比当前数位置后的数，也就是区间的 \(r+1\)；把指针减一，就得到了区间的 \(l-1\)。直接计算答案即可，但由于已经被删的数是不计入区间的，所以我们还要再用一个树状数组维护 \(l\) 到 \(r\) 之间实际上还有几个没有被删的数，也就是删掉当前数的得分。
#include<bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
const int inf=1e9;
int n,k,c[MAXN],a[MAXN],p[MAXN],b[MAXN],t[MAXN],ans;
int lb(int x){return x&(-x);
}
void add(int x,int y){for(int i=x;i<=n;i+=lb(i))t[i]+=y;
}
int sum(int x){int tans=0;for(int i=x;i;i-=lb(i))tans+=t[i];return tans;
}
int read(){char c=getchar();int tmp=0;while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')tmp=tmp*10+(c-'0'),c=getchar();return tmp;
}
set<int>s;
set<int>::iterator it;
signed main(){n=read(),k=read();for(int i=1;i<=n;i++)a[i]=read(),p[a[i]]=i,add(i,1);for(int i=1;i<=k;i++)b[i]=read(),c[b[i]]++;s.insert(0),s.insert(n+1);for(int i=1;i<=n;i++){int pos=p[i];if(c[i]){s.insert(pos);}else{it=s.upper_bound(pos);int r=*it-1,l=*(--it);ans+=sum(r)-sum(l);add(pos,-1);}}printf("%lld\n",ans);return 0;
}AC 记录