#include<cstdio> #include<cstring> #include<set> #include<iostream> #define maxn 1000009 using namespace std; int n,m; int pos[maxn]; bool vis[maxn]; long long value[maxn]; set<int>st; set<int>::iterator it; void add(int x,int v) { while(x<=n) { value[x]+=v; x+=x&(-x); } } long long sum(int x) { long long ret=0; while(x>0) { ret+=value[x]; x-=x&(-x); } return ret; } int main() { int num; long long ans=0; scanf("%d%d",&n,&m); st.insert(0); st.insert(n+1); for(int i=1;i<=n;i++) { scanf("%d",&num); pos[num]=i; add(i,1); } for(int i=1;i<=m;i++) { scanf("%d",&num); vis[num]=1; } for(int i=1;i<=n;i++) { if(vis[i]==0)//need be moved { it=st.upper_bound(pos[i]); int r=*it-1; int l=*(--it); ans+=sum(r)-sum(l); add(pos[i],-1); } else { st.insert(pos[i]); } } cout<<ans; }
codeforces 387C George and Number
原文:http://www.cnblogs.com/yours1103/p/3566552.html