• 应用
• 登录
• 注册

# 新人求助，动态逆序对那题，本机AC提交RE。。。

@ xzz_233 2017-10-12 22:55

RUN ID 3702141

# 哦，不会CDQ，树状数组套主席树 = =

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define Fname "inverse"
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 int sum(int pos){int ret=0;while(pos)ret+=TREE[pos],pos-=lowbit(pos);return ret;}
il ll solve(){
ll ret=0;
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){
++_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;
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(){
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
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;
}
@ xzz_233 2017-10-12 22:58 回复

// 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 int sum(int pos){int ret=0;while(pos)ret+=TREE[pos],pos-=lowbit(pos);return ret;}
il ll solve(){
ll ret=0;
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;
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;
}
@ xzz_233 2017-10-12 23:00 回复

@ xzz_233 2017-10-13 07:49 回复

120.44MB 卡过去了。。。醉了

@ xzz_233 2017-10-13 07:53 回复

const int & 大法好。。