zcmimi's blog
avatar
zc
2020-03-24 09:05:00
  • 本文总阅读量
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

#include<bits/stdc++.h>
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=100011,inf=2122219134;
int n,q,s[N],pos[N];
long long ans[50011];
void add(int x,int v){for(;x<=n;x+=x&-x)s[x]+=v;}
int ask(int x){int res=0;for(;x;x-=x&-x)res+=s[x];return res;}
struct node{
    int v,w,p,id;
    bool operator<(node t){return p<t.p;}
}b[N+50000],c[N+50000];
void cdq(int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1,j=l;
    cdq(l,m);cdq(m+1,r);
    for(int i=m+1;i<=r;++i){
        for(;j<=m&&b[j].p<=b[i].p;++j)add(b[j].v,b[j].w);
        ans[b[i].id]+=b[i].w*(ask(n)-ask(b[i].v));// 统计在i之前的与i组成的逆序对个数
    }
    for(int i=l;i<j;++i)add(b[i].v,-b[i].w);
    j=m;
    for(int i=r;i>m;--i){
        for(;j>=l&&b[j].p>=b[i].p;--j)add(b[j].v,b[j].w);
        ans[b[i].id]+=b[i].w*ask(b[i].v-1);// 统计在i之后的与i组成的逆序对个数
    }
    for(int i=m;i>j;--i)add(b[i].v,-b[i].w);
    std::merge(b+l,b+m+1,b+m+1,b+r+1,c+l);//使用merge合并比排序更快(归并排序)
    for(int i=l;i<=r;++i)b[i]=c[i];
}
int main(){
    in(n,q);
    int x;
    for(int i=1;i<=n;++i)in(x),b[i]=node{x,1,pos[x]=i,0};
    for(int i=1;i<q;++i)in(x),b[n+i]=node{x,-1,pos[x],i};
    cdq(1,n+q-1);
    for(int i=1;i<q;++i)ans[i]+=ans[i-1];
    for(int i=0;i<q;++i)out(ans[i],ln);
    flush();
}

在线解法: 树状数组+动态开点线段树

cdq分治是离线解法,万一遇到毒瘤出题人就不能用了

所以我们要学习更加高明的算法

树状数组套动态开点权值线段树, 实现有点类似待修改主席树

#include<bits/stdc++.h>
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=100011,inf=2122219134;
int n,q,pos[N],RT[N],sz=0,s[N*300],ls[N*300],rs[N*300];
void upd(int l,int r,int x,int y,int &rt){
    if(!rt)rt=++sz;
    s[rt]+=y;
    if(l==r)return;
    int m=(l+r)>>1;
    if(x<=m)upd(l,m,x,y,ls[rt]);
    else upd(m+1,r,x,y,rs[rt]);
}
int t[N],T[N];
int ask(int l,int r,int x,int typ){
    int cnt=0,CNT=0,sum=0;
    for(int i=l-1;i;i-=i&-i)t[++cnt]=RT[i];
    for(int i=r;i;i-=i&-i)T[++CNT]=RT[i];
    l=1,r=n;
    while(l<r){
        int m=(l+r)>>1;
        if(x>m){
            if(typ){
                for(int i=1;i<=cnt;++i)sum-=s[ls[t[i]]];
                for(int i=1;i<=CNT;++i)sum+=s[ls[T[i]]];
            }
            for(int i=1;i<=cnt;++i)t[i]=rs[t[i]];
            for(int i=1;i<=CNT;++i)T[i]=rs[T[i]];
            l=m+1;
        }
        else{
            if(!typ){
                for(int i=1;i<=cnt;++i)sum-=s[rs[t[i]]];
                for(int i=1;i<=CNT;++i)sum+=s[rs[T[i]]];
            }
            for(int i=1;i<=cnt;++i)t[i]=ls[t[i]];
            for(int i=1;i<=CNT;++i)T[i]=ls[T[i]];
            r=m;
        }
    }
    return sum;
}
int main(){
    in(n,q);
    int x;
    long long ans=0;
    for(int i=1;i<=n;++i){
        in(x);pos[x]=i;
        ans+=ask(1,i-1,x,0);
        for(int j=i;j<=n;j+=j&-j)upd(1,n,x,1,RT[j]);
    }
    out(ans,ln);
    while(--q){
        in(x);
        ans-=ask(1,pos[x]-1,x,0);
        ans-=ask(pos[x]+1,n,x,1);
        out(ans,ln);
        for(int j=pos[x];j<=n;j+=j&-j)upd(1,n,x,-1,RT[j]);
    }
    flush();
}
LG 3157 [CQOI2011]动态逆序对
comment评论
Search
search