bzoj 3295 动态逆序对 (三维偏序,CDQ+树状数组)

时间:2024-06-22 23:04:20

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3295

思路:

可以将这道题看成倒着插入,这样就可以转化成求逆序对数,用CDQ分治降维,正反用树状数组求两遍逆序对就好了。

这道题还可以用在线的树套树或者可持久化线段树来写。。

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 2e5+;
struct node{
int t,x,y;
int kind,id;
node() {}
node(int a,int b,int c,int d,int e = ):t(a),x(b),y(c),kind(d),id(e){}
bool operator < (const node &k) const {
if(x == k.x) return y<k.y;
return x < k.x;
}
};
int n,m,a[M],pos[M],x,c[M],tim,len;
node q[M],t[M];
ll ans[M];
void add(int x,int val){
while(x <= n){
c[x] += val;
x += (x&-x);
}
} int getsum(int x){
int sum = ;
while(x){
sum += c[x];
x -= (x&-x);
}
return sum;
} void cdq(int l,int r){
if(l == r) return ;
int mid = (l + r) >> ;
for(int i = l;i <= r;i ++){
if(q[i].t <= mid) add(q[i].y,q[i].kind);
else ans[q[i].id] += q[i].kind*(getsum(n) - getsum(q[i].y));
}
for(int i = l;i <= r;i ++)
if(q[i].t <= mid) add(q[i].y,-q[i].kind); for(int i = r;i >= l;i --){
if(q[i].t <= mid) add(q[i].y,q[i].kind);
else ans[q[i].id] += q[i].kind*getsum(q[i].y-);
}
for(int i = l;i <= r;i ++)
if(q[i].t <= mid) add(q[i].y,-q[i].kind); int L = l,R = mid+;
for(int i = l;i <= r;i ++){
if(q[i].t <= mid) t[L++] = q[i];
else t[R++] = q[i];
}
for(int i = l;i <= r;i ++) q[i] = t[i];
cdq(l,mid); cdq(mid+,r);
} int main()
{
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i ++){
scanf("%d",&a[i]);
pos[a[i]] = i; q[++len] = node(++tim,i,a[i],,);
}
for(int i = ;i <= m;i ++){
scanf("%d",&x);
q[++len] = node(++tim,pos[x],x,-,i);
}
sort(q+,q++len);
cdq(,len);
for(int i = ;i <= m;i ++){
ans[i] += ans[i-];
printf("%lld\n",ans[i-]);
}
return ;
}