哦,抱歉发上来才发现居然有缩进。。。本机我确实是运行通过答案对的啊。。。有问题烦请明示。。。
```cpp
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define lowbit(i) ((i)&-(i))
typedef long long ll;
il int gi(){
rg int x=0;rg bool flg=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return flg?-x:x;
}
const int maxn=1e5+1;
int n,m,st[maxn],__pos[maxn];
namespace init_inverse{
static int TREE[maxn];
il vd add(int pos){while(pos<=n)++TREE[pos],pos+=lowbit(pos);}
il vd _add(int pos){while(pos<=n)--TREE[pos],pos+=lowbit(pos);}
il int sum(int pos){int ret=0;while(pos)ret+=TREE[pos],pos-=lowbit(pos);return ret;}
il ll solve(){
ll ret=0;
drep(i,n,1)add(st[i]),ret+=sum(st[i]-1);
return ret;
}
il ll del(int x){ll ret=sum(x-1);_add(x);return ret;}
}
namespace DS{
int ls[maxn*100],rs[maxn*100],tot[maxn*100],rt[maxn],_cnt=0;
#define mid ((l+r)>>1)
il int build(int l,int r){
int ret=++_cnt;
if(l^r)ls[ret]=build(l,mid),rs[ret]=build(mid+1,r);
return ret;
}
il vd Updata(int&x,int l,int r,const int&pos,const int&num){
if(!x)return;
++_cnt,ls[_cnt]=ls[x],rs[_cnt]=rs[x],tot[_cnt]=tot[x]+num,x=_cnt;
if(l==r)return;
if(pos<=mid)Updata(ls[x],l,mid,pos,num);
else Updata(rs[x],mid+1,r,pos,num);
}
il int Query(const int&x,int l,int r,const int&_l,const int&_r){
if(_l>_r)return 0;
if(_l<=l&&r<=_r)return tot[x];
return (_l<=mid?Query(ls[x],l,mid,_l,_r):0)+(_r>mid?Query(rs[x],mid+1,r,_l,_r):0);
}
#undef mid
il vd init(){
rt[0]=build(1,n);
rep(i,1,n)rt[i]=rt[0];
rep(i,1,n)for(int j=i;j<=n;j+=lowbit(j))Updata(rt[j],1,n,st[i],1);
}
il ll del(int x){
ll ret=init_inverse::del(x);
for(int j=__pos[x]-1;j;j-=lowbit(j))ret+=Query(rt[j],1,n,x+1,n)-Query(rt[j],1,n,1,x-1);
for(int j=__pos[x];j<=n;j+=lowbit(j))Updata(rt[j],1,n,x,-1);
return ret;
}
}
int main(){
n=gi(),m=gi();
rep(i,1,n)st[i]=gi(),__pos[st[i]]=i;
ll ans=init_inverse::solve();
DS::init();
while(m--){
printf("%lld\n",ans);
ans-=DS::del(gi());
}
return 0;
}
```
by λᴉʍ @ 2017-10-12 22:58:56
大佬,大佬
by iodwad @ 2017-10-12 22:59:44
有人吗。。dalao们都走了吗。。
by λᴉʍ @ 2017-10-12 23:00:43
我naive了。。
by λᴉʍ @ 2017-10-13 07:36:49
@[XZZ\_\_233](/space/show?uid=23118) 大佬别熬夜了——来自一个蒟蒻的mo拜
by Focus_on @ 2017-10-13 07:45:46
假装是神帖。。。。
by 青衫白叙 @ 2017-10-13 07:46:57
120.44MB 卡过去了。。。醉了
by λᴉʍ @ 2017-10-13 07:49:27
const int & 大法好。。
没加:3551ms / 120.44MB
加了:2492ms / 97.88MB
by λᴉʍ @ 2017-10-13 07:53:35
假装是神贴(考古)![](https://cdn.luogu.com.cn/upload/pic/24142.png)
by XiaoX @ 2018-09-27 21:49:20