BZOJ 2141 排队（CDQ分治）

我们把每一次交换看做两个插入两个删除。然后就是一个三维偏序。时间一维，下标一维，权值一维。
#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=100010;

struct query{

    int t,x,y,k,w;

}q[N],c[N];

int ans[N],n,a[N],m,tr[N],b[N],cnt;

bool cmp(query a,query b){

    return a.t<b.t;

}

int lowbit(int x){

    return x&-x;

}

void add(int x,int w){

    for(int i=x;i<=n;i+=lowbit(i)){

        tr[i]+=w;

    }

}

int getsum(int x){

    int tmp=0;

    for(int i=x;i;i-=lowbit(i)){

        tmp+=tr[i];

    }

    return tmp;

}

void cdq1(int l,int r){

    if(l==r)return;

    int mid=(l+r)>>1;

    cdq1(l,mid);cdq1(mid+1,r);

    int ll=l;int rl=mid+1;int now=0;

    while(ll<=mid&&rl<=r){

        if(q[ll].x<=q[rl].x){

            add(q[ll].y,q[ll].k);

            c[++now]=q[ll++];

        }

        else{

            ans[q[rl].w]+=q[rl].k*(getsum(n)-getsum(q[rl].y));

            c[++now]=q[rl++];

        }

    }

    while(ll<=mid){

        add(q[ll].y,q[ll].k);

        c[++now]=q[ll++];

    }

    while(rl<=r){

        ans[q[rl].w]+=q[rl].k*(getsum(n)-getsum(q[rl].y));

        c[++now]=q[rl++];

    }

    for(int i=l;i<=mid;i++){

        add(q[i].y,-q[i].k);

    }

    for(int i=l;i<=r;i++){

        q[i]=c[i-l+1];

    }

}

void cdq2(int l,int r){

    if(l==r)return;

    int mid=(l+r)>>1;

    cdq2(l,mid);cdq2(mid+1,r);

    int ll=l;int rl=mid+1;int now=0;

    while(ll<=mid&&rl<=r){

        if(q[ll].x>=q[rl].x){

            add(q[ll].y,q[ll].k);

            c[++now]=q[ll++];

        }

        else{

            ans[q[rl].w]+=q[rl].k*getsum(q[rl].y-1);

            c[++now]=q[rl++];

        }

    }

    while(ll<=mid){

        add(q[ll].y,q[ll].k);

        c[++now]=q[ll++];

    }

    while(rl<=r){

        ans[q[rl].w]+=q[rl].k*getsum(q[rl].y-1);

        c[++now]=q[rl++];

    }

    for(int i=l;i<=mid;i++){

        add(q[i].y,-q[i].k);

    }

    for(int i=l;i<=r;i++){

        q[i]=c[i-l+1];

    }

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        b[i]=a[i];

    }

    sort(b+1,b+1+n);

    int tot=unique(b+1,b+1+n)-b-1;

    for(int i=1;i<=n;i++){

        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;

        q[++cnt].t=cnt;q[cnt].x=i;q[cnt].y=a[i];q[cnt].k=1;q[cnt].w=0;

    }

    scanf("%d",&m);

    for(int i=1;i<=m;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        q[++cnt].t=cnt;q[cnt].x=x;q[cnt].y=a[x];q[cnt].k=-1;q[cnt].w=i;

        q[++cnt].t=cnt;q[cnt].x=y;q[cnt].y=a[y];q[cnt].k=-1;q[cnt].w=i;

        q[++cnt].t=cnt;q[cnt].x=x;q[cnt].y=a[y];q[cnt].k=1;q[cnt].w=i;

        q[++cnt].t=cnt;q[cnt].x=y;q[cnt].y=a[x];q[cnt].k=1;q[cnt].w=i;

        swap(a[x],a[y]);

    }

    cdq1(1,cnt);

    sort(q+1,q+1+cnt,cmp);

    cdq2(1,cnt);

    printf("%d\n",ans[0]);

    for(int i=1;i<=m;i++){

        ans[i]+=ans[i-1];

        printf("%d\n",ans[i]);

    }

    return 0;

}
巴特西

BZOJ 2141 排队（CDQ分治）

最新文章

热门文章
