首页 > 代码库 > 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 动态逆序对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。