1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; typedef long long LL; inline const LL Get_Int() { LL num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=200005; LL n,m,pos[maxn],Ans[maxn]; struct BIT { LL c[maxn]; #define lowbit(x) x&(-x) void add(int x,int v) { for(int i=x; i<=n; i+=lowbit(i))c[i]+=v; } void clear(int x) { for(int i=x; i<=n; i+=lowbit(i))c[i]=0; } int sum(int x) { int sum=0; for(int i=x; i>=1; i-=lowbit(i))sum+=c[i]; return sum; } } bit; struct Pair { int x,y,t; bool operator < (const Pair& b) const { return x<b.x||(x==b.x&&y>b.y)||(x==b.x&&y==b.y&&t<b.t); } } a[maxn],tmp[maxn]; void CDQBinary(int Left,int Right) { if(Left==Right)return; int mid=(Left+Right)>>1; int lpos=Left,rpos=mid+1; for(int i=Left; i<=Right; i++) if(a[i].t<=mid)tmp[lpos++]=a[i]; else tmp[rpos++]=a[i]; for(int i=Left; i<=Right; i++)a[i]=tmp[i]; CDQBinary(Left,mid); int j=Left; for(int i=mid+1; i<=Right; i++) { while(j<=mid&&a[j]<a[i]) { bit.add(a[j].y,1); j++; } Ans[a[i].t]+=bit.sum(n)-bit.sum(a[i].y); } for(int i=Left; i<=mid; i++)bit.clear(a[i].y); j=mid; for(int i=Right; i>mid; i--) { while(j>=Left&&a[i]<a[j]) { bit.add(a[j].y,1); j--; } Ans[a[i].t]+=bit.sum(a[i].y-1); } for(int i=Left; i<=mid; i++)bit.clear(a[i].y); CDQBinary(mid+1,Right); merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp); int tot=0; for(int i=Left; i<=Right; i++)a[i]=tmp[tot++]; } int main() { n=Get_Int(); m=Get_Int(); for(int i=1; i<=n; i++) { a[i].x=i; a[i].y=Get_Int(); pos[a[i].y]=i; } int cnt=n; LL ans=0; for(int i=1; i<=m; i++) { int x=Get_Int(); a[pos[x]].t=cnt--; } for(int i=1; i<=n; i++) if(!a[i].t)a[i].t=cnt--; sort(a+1,a+n+1); CDQBinary(1,n); for(int i=1; i<=n; i++)ans+=Ans[i]; for(int i=n; i>n-m; i--) { printf("%lld\n",ans); ans-=Ans[i]; } return 0; }
|