BZOJ 2141 排队 (三维偏序CDQ+树状数组)-白红宇

BZOJ 2141 排队 (三维偏序CDQ+树状数组)

阅读量：4616 次

发布时间：2019-06-09

本文共 2176 字，大约阅读时间需要 7 分钟。

题目大意：略

和这道题一样的思路

一开始的序列视为$n$次插入操作

把每次交换操作看成四次操作，删除$x$，删除$y$，加入$x$，加入$y$

把每次操作都看成一个三元组 $<x,w,t>$ 操作位置，权值，以及操作时间

变成了一道三维偏序裸题

外层按操作时间$t$升序，回溯时按操作位置$x$排序

处理左区间对右区间的影响时，正反两次树状数组求逆序对即可

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define N1 30100 6 #define ll long long 7 #define dd double 8 #define inf 0x3f3f3f3f3f3f3f3fll 9 using namespace std;10  11 int gint()12 {13     int ret=0,fh=1;char c=getchar();14     while(c<'0'||c>'9'){
   if(c=='-')fh=-1;c=getchar();}15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}16     return ret*fh;17 }18 int n,m,ma,nn,K;19  20 struct BIT{21 int s[N1];22 void update(int x,int w){
   for(int i=x;i<=ma;i+=(i&(-i))) s[i]+=w;}23 int query(int x){
   int ans=0; for(int i=x;i;i-=(i&(-i))) ans+=s[i]; return ans;}24 }b;25 struct node{
   int p,x,w,t,ans;}a[N1],tmp[N1];26 int c[N1],q[N1],que[N1],tl;27  28 void CDQ(int L,int R)29 {30     if(R-L<=1) return;31     int M=(L+R)>>1;32     CDQ(L,M); CDQ(M,R);33     int i=M-1,j=R-1,cnt=0,x;34     while(i>=L&&j>=M)35     {36         if(a[i].x>a[j].x){37             b.update(a[i].w,a[i].p);38             que[++tl]=i; i--;39         }else{40             a[j].ans+=b.query(a[j].w-1);41             j--;42         }43     }44     while(i>=L) {i--;}45     while(j>=M) {a[j].ans+=b.query(a[j].w-1); j--;}46     while(tl) {x=que[tl--]; b.update(a[x].w,-a[x].p);}47      48     i=L,j=M,cnt=0;49     while(i
         
          
           =1;i--) ans+=b.query(a[i].w-1),b.update(a[i].w,1);77 memset(b.s,0,sizeof(b.s));78 scanf("%d",&m); nn=n;79 for(i=n+1;i<=n+m;i++)80 {81 x=gint(); y=gint();82 a[++nn].p=-1,a[nn].t=nn,a[nn].x=x,a[nn].w=q[x];//,a[nn].id=i-n;83 a[++nn].p=-1,a[nn].t=nn,a[nn].x=y,a[nn].w=q[y];//a[nn].id=i-n;84 swap(q[x],q[y]);85 a[++nn].p=1,a[nn].t=nn,a[nn].x=x,a[nn].w=q[x];//a[nn].id=i-n;86 a[++nn].p=1,a[nn].t=nn,a[nn].x=y,a[nn].w=q[y];//a[nn].id=i-n;87 }88 CDQ(1,nn+1);89 sort(a+1,a+nn+1,cmp);90 printf("%lld\n",ans);91 for(i=n+1;i<=nn;i+=4)92 {93 ans+=-a[i].ans-a[i+1].ans+a[i+2].ans+a[i+3].ans;94 printf("%lld\n",ans);95 }96 return 0;97 }