记录编号	316691	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	3.288 s
提交时间	2016-10-07 06:38:30	内存使用	1.75 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

typedef long long LL;

const int maxn=100000+10;

bool vis[maxn];

LL Ans=0;

vector<int> :: iterator it;

int C[maxn],A[maxn];
int l[400],r[400];
int  num[maxn],haha[maxn];

vector<int> p[400];

int N,M,sum,sz,now;

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

void up(int x)
{
     for(;x;x-=lowbit(x))
     {
         C[x]++;               
     }
}
LL get(int x)
{
    LL res=0;
    if(!x)return 0;
    for(;x<=N;x+=lowbit(x))
    {
       res+=C[x]; 
                    
    }
    return res; 
}

void fenkuai()
{
     int sz=sqrt(N*1.0);
     if(N%sz==0)sz++;
     for(sum=1;sum*sz<N;sum++)
     {
      l[sum]=(sum-1)*sz+1,r[sum]=sum*sz;                                                     
      for(int j=l[sum];j<=r[sum];j++)
      {
        p[sum].push_back(A[j]);
        num[j]=sum;
      }
      sort(p[sum].begin(),p[sum].end());
     }
      l[sum]=(sum-1)*sz+1,r[sum]=N;                                                     
      for(int j=l[sum];j<=r[sum];j++)
      {
        p[sum].push_back(A[j]);
        num[j]=sum;
      }
      sort(p[sum].begin(),p[sum].end());
}

int getpos(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
       if(A[i]==now&&!vis[i])return i;
    }
}

void updata()
{
     
        int i=num[haha[now]];
        it=lower_bound(p[i].begin(),p[i].end(),now);     
            int pos=getpos(l[i],r[i]);
            for(int j=1;j<i;j++)
            Ans-=(p[j].end()-upper_bound(p[j].begin(),p[j].end(),now));        
            for(int j=l[i];j<pos;j++)
            {    if(A[j]>now&&!vis[j])
                 Ans--;
            }   
             for(int j=pos+1;j<=r[i];j++)
             {
               if(A[j]<now&&!vis[j])
                 Ans--;
             }           
              for(int j=i+1;j<=sum;j++)
              {
                Ans-=lower_bound(p[j].begin(),p[j].end(),now)-p[j].begin();
              }   
              vis[pos]=1;
              p[i].erase(it);
}
int main()
{
    freopen("inverse.in","r",stdin);
    freopen("inverse.out","w",stdout);
    scanf("%d%d",&N,&M);
    
    for(int i=1;i<=N;i++)scanf("%d",&A[i]),up(A[i]),Ans+=get(A[i]+1),haha[A[i]]=i;  
    fenkuai();
    for(int i=1;i<=M;i++)
    {
        scanf("%d",&now);
        printf("%lld\n",Ans);
        updata();    
    }
   fclose(stdin);fclose(stdout);
    return 0;
}