本文主要是介绍[BZOJ3295] [Cqoi2011]动态逆序对 CDQ分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CDQ跑的比分治快得多
首先 我们可以把每一个点看成一个三元组(x, y, z) x 表示它当前的值 y 表示的在序列中的编号 z 表示它的时间 即第z次操作后的这个点
所以 如果某个点P在平面上的左上方有点(值小于P并且位置在P之后) 后者右下方(恰好相反)的地方有点 就会形成一个逆序对
在一开始我们很容易求出每一个点形成的逆序对总数 每次删除的时候从ans中减去
然而 在CDQ分治的过程中 树状数组需要多次使用 每次清空需要耗费大量时间 这个时候我们加入一个时间轴 只有在当前时间的点才进行统计 这样就避免了清空的操作 节省了时间
还有一个问题 每次一个点x删除时 会减去他的逆序对(x, y) y删除的时候也同样会减去 这样就重复了 要怎样处理这样的问题呢？
我们将已经删除的元素看作一个删除序列 定义d[i]为删除该元素后删除序列中新增的逆序对的个数 这就是减重复了的个数 每次删除一个数过后ans要加上d[i]；
这样 每一个删除操作都成为了一个三元组(x, y, id) 我们可以用CDQ根据id排序 但是还剩下两位 处理的时候会有困难 所以我们把整个序列按y排序 这样就可以了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#define lowbit(x) ((x) & (-(x)))
#define SF scanf
#define PF printf
using namespace std;
typedef long long LL;
const int MAXN = 100000;
int cnt[MAXN+10], A[MAXN+10], idx[MAXN+10], c[MAXN+10], tim[MAXN+10]; // tim 节约每次删除树状数组的时间 cnt 计算某个数形成的逆序对数量
int d[MAXN+10];
int n, m, tot;
LL ans;
struct Node {int x, y, id; // y 原序列位置 x 现在的值bool operator < (const Node &t) const {return y < t.y;}
} q[MAXN+10], tmp[MAXN+10];
void add(int x, int f) { // f = -1 询问前方 f = 1 询问后方for(; x <= n && x; x += lowbit(x) * f) {if(tim[x] != tot) c[x] = 0, tim[x] = tot;c[x]++;}
}
int query(int x, int f) {int ret = 0;for( ; x && x <= n; x += lowbit(x) * f) if(tim[x] == tot)ret += c[x];return ret;
}
void CDQ(int L, int R) {if(L == R) {PF("%lld\n", ans);ans -= cnt[q[L].y];ans += d[L];return ;}int mid = (L+R) >> 1, l1, l2;l1 = L; l2 = mid+1;for(int i = L; i <= R; i++) if(q[i].id <= mid) tmp[l1++] = q[i];else tmp[l2++] = q[i];for(int i = L; i <= R; i++) q[i] = tmp[i];CDQ(L, mid);tot++;int j = L;for(int i = mid+1; i <= R; i++) {while(j <= mid && q[j].y < q[i].y) {add(q[j].x, -1); j++;}d[q[i].id] += query(q[i].x, 1);}tot++; j = mid;for(int i = R; i > mid; i--) {while(j >= L && q[j].y > q[i].y) {add(q[j].x, 1);j--;}d[q[i].id] += query(q[i].x, -1);}CDQ(mid+1, R);l1 = L; l2 = mid+1;for(int i = L; i <= R; i++) if(l1 <= mid && (l2 > R || q[l1] < q[l2])) tmp[i] = q[l1++];else tmp[i] = q[l2++];for(int i = L; i <= R; i++) q[i] = tmp[i];
}
int main() {SF("%d%d", &n, &m);for(int i = 1; i <= n; i++) {SF("%d", &A[i]); idx[A[i]] = i;}for(int i = 1; i <= n; i++) {cnt[i] = query(A[i], 1);add(A[i], -1);ans += cnt[i];}tot++; // 时间轴移动 防止重复统计for(int i = n; i; i--) {cnt[i] += query(A[i], -1);add(A[i], 1);}for(int i = 1; i <= m; i++) {SF("%d", &q[i].x); q[i].y = idx[q[i].x];q[i].id = i;}sort(q+1, q+1+m);CDQ(1, m);
}这篇关于[BZOJ3295] [Cqoi2011]动态逆序对 CDQ分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
