首页 > 代码库 > BZOJ 3295 动态逆序对

BZOJ 3295 动态逆序对

调了好久。。。。

转化成三维偏序,cdq处理。

好像比较快?

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 300500using namespace std;long long n,m,x,a[maxn],pos[maxn],f1[maxn],f2[maxn],t[maxn],ans=0;struct pnt{    long long a,b,c,ans;}p[maxn];bool cmp1(pnt x,pnt y) {return x.b<y.b;}bool cmp2(pnt x,pnt y) {return x.b>y.b;}bool cmp3(pnt x,pnt y) {return x.a<y.a;}long long lowbit(long long x) {return (x&(-x));}void add(long long x,long long val){    for (long long i=x;i<=n;i+=lowbit(i))        t[i]+=val;}long long ask(long long x){    long long ret=0;    for (long long i=x;i>=1;i-=lowbit(i))        ret+=t[i];    return ret;}void cdq1(long long left,long long right){    long long mid=left+right>>1;    sort(p+left,p+mid+1,cmp1);sort(p+mid+1,p+right+1,cmp1);    long long i=left,j=mid+1;    while (j<=right)    {        while ((i<=mid) && (p[i].b<p[j].b))        {            add(p[i].c,1);            i++;        }        p[j].ans+=ask(n)-ask(p[j].c);        j++;    }    for (long long j=left;j<i;j++) add(p[j].c,-1);}void cdq2(long long left,long long right){    long long mid=left+right>>1;    sort(p+left,p+mid+1,cmp2);sort(p+mid+1,p+right+1,cmp2);    long long i=left,j=mid+1;    while (j<=right)    {        while ((i<=mid) && (p[i].b>p[j].b))        {            add(p[i].c,1);            i++;        }        p[j].ans+=ask(p[j].c-1);        j++;    }    for (long long j=left;j<i;j++) add(p[j].c,-1);}void cdq(long long left,long long right){    if (left==right) return;    long long mid=left+right>>1;    cdq(left,mid);cdq(mid+1,right);    cdq1(left,right);    cdq2(left,right); }int main(){    scanf("%lld%lld",&n,&m);    for (long long i=1;i<=n;i++)    {        scanf("%lld",&a[i]);        pos[a[i]]=i;    }    for (long long i=1;i<=n;i++)    {        f1[pos[i]]=(pos[i]-1)-ask(pos[i]-1);        ans+=f1[pos[i]];        f2[pos[i]]=ask(n)-ask(pos[i]);        add(pos[i],1);    }    memset(t,0,sizeof(t));    for (long long i=1;i<=m;i++)    {        scanf("%lld",&x);        p[i].a=i;p[i].b=pos[x];p[i].c=x;    }    cdq(1,m);    sort(p+1,p+m+1,cmp3);     for (long long i=1;i<=m;i++)    {        printf("%lld\n",ans);        x=p[i].c;         ans-=(f1[pos[x]]+f2[pos[x]]);         ans+=(p[i].ans);    }    return 0;}

 

BZOJ 3295 动态逆序对