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

回复帖子 返回题目

@ xzz_233 2017-10-12 22:55

RUN ID 3702141

上哈省OI下了数据我本机测是对的啊= =为什么RE了呢?

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

也许是我naive了= =

// 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 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){
          ++_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(){
    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 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;
}
@ xzz_233 2017-10-12 23:00 回复

有人吗。。dalao们都走了吗。。

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

120.44MB 卡过去了。。。醉了

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

const int & 大法好。。

没加:3551ms / 120.44MB

加了:2492ms / 97.88MB