bzoj3295: [Cqoi2011]动态逆序对(cdq分治+树状数组)

时间：2022-04-22 06:18:11

3295: [Cqoi2011]动态逆序对

题目：传送门

题解：

　　 刚学完cdq分治，想起来之前有一道是树套树的题目可以用cdq分治来做...尝试一波

　　 还是太弱了...想到了要做两次cdq...然后伏地膜大佬

　　 其实需要维护的地方还是很容易想到的：

　　 第一维维护位置w，第二维维护数值s，第三维维护修改的时间t。

　　 那么对于t我们可以倒序插入，然后我们就可以把它看作t从小到大的插入结点（即使没有删除的点为了方便也要更新一下t）。

　　 再去观察就会发现，当我们插入一个节点t0时，我们需要求的就是在t0左边的比它大的数和在右边比它小的数：

　　 t<t0 w<w0 s>s0

　　 t<t0 w>w0 s<s0

　　 再转化一下符号：

　　 t<t0 w<w0 s<(n-s0+1)

　　 t<t0 w<(n-w0+1) s<s0

　　 这时候再看，不就是陌上花开吗！！！

　　 ps：大佬实在是太强了，记得开longlong（虽然不是很懂为什么，但是就是错了...）

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 struct node

 {

     int w,s,t;//位置，数值，操作时间

     LL ans;//当前时间的答案

 }a[],ba[];int n,m,b[];LL ans[];

 bool cmp(node n1,node n2){return n1.t<n2.t;}

 LL s[];

 int lowbit(int x){return x&-x;}

 void add(int x,int k){while(x<=n){s[x]+=k;x+=lowbit(x);}}

 int getsum(int x){LL ans=;while(x){ans+=s[x];x-=lowbit(x);}return ans;}

 void cdq(int l,int r)

 {

     if(l==r)return ;

     int mid=(l+r)>>;

     cdq(l,mid);cdq(mid+,r);

     int i=l,j=mid+,p=l;

     while(i<=mid && j<=r)

     {

         if(a[i].w<a[j].w)

         {

             add(a[i].s,);

             ba[p++]=a[i++];

         }

         else

         {

             a[j].ans+=getsum(a[j].s);

             ba[p++]=a[j++];

         }

     }

     while(i<=mid)add(a[i].s,),ba[p++]=a[i++];

     while(j<=r)a[j].ans+=getsum(a[j].s),ba[p++]=a[j++];

     for(int i=l;i<=mid;i++)add(a[i].s,-);

     for(int i=l;i<=r;i++)a[i]=ba[i];

 }

 int main()

 {

     scanf("%d%d",&n,&m);int x,cc=n;

     for(int i=;i<=n;i++)a[i].w=i,scanf("%d",&a[i].s);

     for(int i=;i<=m;i++)scanf("%d",&x),b[x]=i;int s=m;

     for(int i=;i<=n;i++)if(!b[i])b[i]=++s;

     for(int i=;i<=n;i++)a[i].t=n-b[a[i].s]+;

     sort(a+,a+n+,cmp);

     for(int i=;i<=n;i++)a[i].s=n-a[i].s+;

     cdq(,n);

     sort(a+,a+n+,cmp);

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

     {

         a[i].s=n-a[i].s+;

         a[i].w=n-a[i].w+;

     }

     cdq(,n);

     for(int i=;i<=n;i++)ans[a[i].t]=a[i].ans;

     for(int i=;i<=n;i++)ans[i]+=ans[i-];

     for(int i=n;i>=n-m+;i--)printf("%lld\n",ans[i]);

     return ;

 }

相关文章