记录编号	192867	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	4.569 s
提交时间	2015-10-13 10:42:30	内存使用	2.99 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=100010;
const int maxm=350;
const int mod=7777777;

ll Read()
{
    ll x=0;char y;int flag=1;
    do{y=getchar();if(y=='-') flag=-1;} while(y<'0'||y>'9');
    do{x=x*10+y-'0';y=getchar();} while(y>='0'&&y<='9');
    return x*flag;
}

int tree[3*maxn],block[maxn];
int a[maxn],p[maxn],b[maxn];
int l[maxm],r[maxm],nl[maxm];
int n,m,s;

int lowbit(int x) {return x&(-x);}

void modify(int x,ll val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=lowbit(x);
    }
}

ll getsum(int x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}

void build_block()
{
    int len=int(sqrt(double(n)));
    if(n%len) s=n/len+1;
    else s=n/len;
    for(int i=1;i<=s;i++)
    {
        l[i]=(i-1)*len+1;r[i]=min(i*len,n);
        sort(b+l[i],b+r[i]+1);nl[i]=l[i];
        for(int j=l[i];j<=r[i];j++) block[j]=i;
    }
}

int found_max(int pos,ll val)
{
    int tl=l[pos],tr=r[pos],m;
    while(tl<=tr)
    {
        m=(tl+tr)/2;
        if(val>b[m]) tl=m+1;
        else tr=m-1;
    }
    return r[pos]-tr;
}

int found_min(int pos,ll val)
{
    int tl=l[pos],tr=r[pos],m;
    while(tl<=tr)
    {
        m=(tl+tr)/2;
        if(val>b[m]) tl=m+1;
        else tr=m-1;
    }
    return tr-nl[pos]+1;
}

ll query(int val)
{
    ll tmp=0;int pos=block[p[val]];
    
    for(int i=1;i<pos;i++) tmp+=found_max(i,val);
    
    for(int i=nl[pos];i<=r[pos];i++)
    {
        if(p[b[i]]<p[val]&&b[i]>val) tmp++;
        if(p[b[i]]>p[val]&&b[i]<val) tmp++;
    }
    
    for(int i=pos+1;i<=s;i++) tmp+=found_min(i,val);
    
    return tmp;
}

void change(int pos)
{
    a[pos]=0;
    for(int i=l[block[pos]];i<=r[block[pos]];i++) b[i]=a[i];
    sort(b+l[block[pos]],b+r[block[pos]]+1);
    nl[block[pos]]++;
}

int main()
{
    freopen("inverse.in","r",stdin);
    freopen("inverse.out","w",stdout);
    //clock_t st=clock();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        a[i]=Read();
        b[i]=a[i];p[a[i]]=i;
    }
    ll ans=0,t;
    for(int i=1;i<=n;i++)
    {
        modify(a[i],1);
        ans+=i-getsum(a[i]);
    }
    build_block();
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans);
        t=Read();
        ans-=query(t);
        change(p[t]);
    }
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}