1.树状数组每个节点的值为该区间内权值线段树的根结点。
2.每棵权值线段树储存其根节点对应树状数组中所表示的区间内的值离散化后在线段树对应各区间内的的个数。
3.先边输入初始序列边求出初始逆序和，每次询问先输出一次逆序和，再删该数。
修改 查询
如何求初始逆序和：
1.每次输入序列中一个数后，查询该数前面(包括该数)小于等于该数的数的个数，用当前数的位置(即当前输入的总数)，减去该数前面(包括该数)小于等于该数的数的个数，得到该数前面比该数大的数的个数，即逆序数。
2.每个位置的逆序数求和即为逆序和。
如何删：
1.求出该数前面比该数大的数的个数，直接查询即可。
2.求出该数后面比该数小的数的个数，直接查询即可。
3.将逆序和减去以上两部分即可得到删去后的逆序和。
4.将该数从包含该数的树状数组节点对应的线段树中删去。
//刚开始偷懒用vector存路径果然TLE。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,rt[100010],cnt=1,pos[100010],qi,hi; struct node { int l,r,v; }tree[100010*400]; int q[32],h[32]; int lowbit(int &x) {return x&(-x);} void add2(int l,int r,int &now,int k) { if(!now) now=cnt++; if(l==r) { tree[now].v++; return; } int mid=(l+r)>>1; if(k<=mid) add2(l,mid,tree[now].l,k); else add2(mid+1,r,tree[now].r,k); tree[now].v=tree[tree[now].l].v+tree[tree[now].r].v; } void add1(int p,int a) { while(p<=n) { add2(1,n,rt[p],a); p+=lowbit(p); } } void locate(int x,int y) { qi=hi=0; while(x>0) { q[qi++]=rt[x]; x-=lowbit(x); } while(y>0) { h[hi++]=rt[y]; y-=lowbit(y); } } int sum(int x) { int mid=0; if(x==1) { for(int i=0;i<hi;++i) mid+=tree[tree[h[i]].l].v; for(int i=0;i<qi;++i) mid-=tree[tree[q[i]].l].v; } else if(x==0) { for(int i=0;i<hi;++i) mid+=tree[h[i]].v; for(int i=0;i<qi;++i) mid-=tree[q[i]].v; } else { for(int i=0;i<hi;++i) mid+=tree[tree[h[i]].r].v; for(int i=0;i<qi;++i) mid-=tree[tree[q[i]].r].v; } return mid; } void down(int x) { if(x==1) { for(int i=0;i<qi;++i) q[i]=tree[q[i]].l; for(int i=0;i<hi;++i) h[i]=tree[h[i]].l; } else if(x==2) { for(int i=0;i<qi;++i) q[i]=tree[q[i]].r; for(int i=0;i<hi;++i) h[i]=tree[h[i]].r; } } int query1(int l,int r,int k) { if(k==r) { return sum(0); } int mid=(l+r)>>1; if(k<=mid) { down(1); return query1(l,mid,k); } else { int c=sum(1); down(2); return c+query1(mid+1,r,k); } } int query2(int l,int r,int k) { if(l==r) { if(l>k) return sum(0); else return 0; } int mid=(l+r)>>1; if(k==mid) { return sum(2); } else if(k<mid) { int c=sum(2); down(1); return c+query2(l,mid,k); } else { down(2); return query2(mid+1,r,k); } } void del1(int p) { qi=hi=0; while(p<=n) { h[hi++]=rt[p]; p+=lowbit(p); } } void del2(int l,int r,int k) { for(int i=0;i<hi;++i) tree[h[i]].v--; if(l==r) return; int mid=(l+r)>>1; if(k<=mid) { down(1); del2(l,mid,k); } else { down(2); del2(mid+1,r,k); } } int main() { long long ans=0; //freopen("testdata.in","r",stdin); cin>>n>>m; for(int i=1;i<=n;++i) { int a; scanf("%d",&a); pos[a]=i; add1(i,a); locate(0,i); ans+=i-query1(1,n,a); } while(m--) { int a; printf("%lld\n",ans); scanf("%d",&a); locate(0,pos[a]); ans-=query2(1,n,a); locate(pos[a],n); ans-=query1(1,n,a); del1(pos[a]); del2(1,n,a); } //cout<<ans<<endl; return 0; }
