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 ;
}