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
|
using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct {int l,r,sum;}T[maxn*20]; int a[maxn],p[maxn],c[maxn],uu,pre[maxn],suf[maxn]; int xx[100],yy[100]; int n,m,ooo,rot[maxn]; inline int lowbit(int x){return x&(-x);} void add(int x,int k){ for(int i=x;i<=n;i+=lowbit(i))c[i]+=k; } int getsum(int x){ int k=0; for(int i=x;i;i-=lowbit(i))k+=c[i];return k; } int query(int o,int l,int r,int x,int y){ if(!o)return 0; if(l>=x&&r<=y)return T[o].sum; else{ int mid=(l+r)/2; int ans=0; if(x<=mid)ans+=query(T[o].l,l,mid,x,y); if(mid<y)ans+=query(T[o].r,mid+1,r,x,y); return ans; } } int queryRange(int uu,int vv,int xx,int 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=++ooo; T[rt].sum++; if(l==r)return; int mid=(l+r)/2; if(x<=mid)update(T[rt].l,l,mid,x); if(mid<x)update(T[rt].r,mid+1,r,x); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); cin>>n>>m; ll ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; p[a[i]]=i; pre[i]=getsum(n)-getsum(a[i]); ans+=pre[i]; add(a[i],1); } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--){ suf[i]=getsum(a[i]-1); add(a[i],1); } while(m--){ cout<<ans<<endl; cin>>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; }
|
近期评论