记录编号	454279	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	4.318 s
提交时间	2017-09-28 18:48:03	内存使用	2.99 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=100000+10;
const int qrt=2500;
const int N=45;
typedef long long ll;
#define size(x) ((x!=NULL)?(x->siz):(0))
int n,m,bl;
ll ans;
int pre[M],nxt[M],sval[M],val[M],pos[M],c[M];
int block[M],beg[N],bend[N],fir[N],len[N];
struct treap{
    treap* ch[2];
    int val,key,siz;
    inline treap(int v) {siz=1;val=v;key=rand();ch[0]=ch[1]=NULL;}
    inline void update() {siz=1+size(ch[0])+size(ch[1]);}
}*rt[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int lb(int x) {return x&(-x);}
inline void add(int x) {while(x<=n) {++c[x];x+=lb(x);}}
inline int getans(int x){int tmp=0;while(x){tmp+=c[x];x-=lb(x);}return tmp;}
typedef pair<treap*,treap*> dou;
inline treap* merge(treap* a,treap* b){
    if(!a) return b; if(!b) return a;
    if(a->key<b->key){
        a->ch[1]=merge(a->ch[1],b);
        a->update();return a;
    }else{
        b->ch[0]=merge(a,b->ch[0]);
        b->update();return b;
    }
}
inline dou split(treap* o,int k){
    if(!o) return dou(NULL,NULL);
    dou x;
    if(size(o->ch[0])>=k){
        x=split(o->ch[0],k);
        o->ch[0]=x.second;o->update();x.second=o;
    }else{
        x=split(o->ch[1],k-size(o->ch[0])-1);
        o->ch[1]=x.first;o->update();x.first=o;
    }return x;
}
inline int getrank(treap* o,int v){
    if(!o) return 0;
    if(o->val>=v) return getrank(o->ch[0],v);
    else return getrank(o->ch[1],v)+size(o->ch[0])+1;
}
inline void _insert(treap* &o,int v){
    int k=getrank(o,v);
    dou x=split(o,k);
    treap* ans=new treap(v);
    o=merge(x.first,merge(ans,x.second));
}
inline ll work(int x){
    ll tmp=0;
    int p=pos[x];int b=block[p];
    if(p==fir[b]) fir[b]=nxt[p];
    else nxt[pre[p]]=nxt[p],pre[nxt[p]]=pre[p];
    int now=fir[b];
    while(now<p) {if(val[now]>x) ++tmp; now=nxt[now];}
    while(now<=bend[b]) {if(val[now]<x) ++tmp; now=nxt[now];}
    for(int i=1;i<b;++i){
        tmp+=len[i];
        tmp-=lower_bound(sval+beg[i],sval+bend[i]+1,x)-sval;
        tmp+=beg[i];
        tmp-=size(rt[i])-getrank(rt[i],x);
    }
    for(int i=b+1;i<=bl;++i){
        tmp+=lower_bound(sval+beg[i],sval+bend[i]+1,x)-sval;
        tmp-=beg[i];
        tmp-=getrank(rt[i],x);
    }_insert(rt[b],x);
    return tmp;
}
int main(){
    freopen("inverse.in","r",stdin);
    freopen("inverse.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;++i) {pre[i]=i-1;nxt[i]=i+1;}
    for(int i=1;i<=n;++i){
        sval[i]=val[i]=read();pos[val[i]]=i;
        block[i]=(i-1)/qrt+1;
        ans+=i-1-getans(val[i]);add(val[i]);
    }printf("%lld\n",ans);bl=block[n];
    for(int i=1;i<=bl;++i){
        fir[i]=beg[i]=bend[i-1]+1;
        bend[i]=min(n,i*qrt);len[i]=bend[i]-beg[i]+1;
        sort(sval+beg[i],sval+bend[i]+1);
    }--m;
    while(m--){
        ans-=work(read());
        printf("%lld\n",ans);
    }read();
    return 0;
}