您的位置: 首页  >  IT文章  >  「Luogu P3157」「CQOI2011」「UVA 11990」动态逆序对 / ``Dynamic'' Inversion

「Luogu P3157」「CQOI2011」「UVA 11990」动态逆序对 / ``Dynamic'' Inversion

分类: IT文章 • 2023-03-24 08:37:32

Description

对于序列 (a)，它的逆序对数定义为集合

({(i,j)| i<j wedge a_i > a_j })

中的元素个数。

现在给出 (1sim n) 的一个排列，按照某种顺序依次删除 (m) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Hint

Luogu 数据：

  • (1le nle 10^5)
  • (1le mle 5 imes 10^4)

UVA 多组数据且数据规模为 Luogu 的两倍。

注：保证前 3 个 solution 可以在 UVA 上通过（Solution 1/2 亲测，Solution 3 代码可以参考：https://www.luogu.com.cn/blog/van/solution-uva11990 ），所有的 solution 实现的好都可以在 Luogu 上通过。

Solution 1

CDQ分治。

先计算出初始整个数列的逆序对数，然后逐个减去被删除数对逆序对数的影响。cdq 就是计算这个影响的过程。

当第 (i) 个数被删去之后，在它前面的，比它大的，且删除时间晚于自己的 数的个数，加上 在它后面的，比它小的，且删除时间晚于自己的 数的个数，就是这个数对总逆序对数的影响。

假如把这个东西拆成两部分来做，那每一个部分的计算实质上就是变形的 三维数点。合起来一起算也是可以的。

  • 第一维：位置，已经排好序。
  • 第二维：数值大小，cdq 的过程中内部归并排序。
  • 第三维：删除时间，使用树状数组等 DS 维护。

这个算法看起来海星，可惜不能在线。

  • 时间复杂度：(O(nlog^2 n))
  • 空间复杂度：(O(n))
  • 是否在线：否

Code for Solution 1

UVA 代码，Luogu同样可过。

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : Luogu P3157 CQOI2011 动态逆序对 / UVA 11990 ``Dynamic'' Inversion
 */
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 2e5 + 5;

int n, m;
struct bryidxt {
	int t[N];
	#define lbt(x) (x & (-x))
	inline void inc(int p, int v) {
		for (; p <= n + 1; p += lbt(p)) t[p] += v;
	}
	inline int get(int p) {
		int ret = 0;
		for (; p; p -= lbt(p)) ret += t[p];
		return ret;
	}
} bit;

struct query {
	int val, delt, ans;
} qry[N];
int loc[N];

inline bool cmp_delt(const query& x, const query& y) {
	return x.delt < y.delt;
}
inline bool cmp_val(const query& x, const query& y) {
	return x.val < y.val;
}

void cdqSolve(int l, int r) {
	if (l == r) return;
	
	int mid = (l + r) >> 1;
	cdqSolve(l, mid);
	cdqSolve(mid + 1, r);
	
	int i = l, j = mid + 1;
	for (; i <= mid; i++) {
		for (; j <= r && qry[i].val > qry[j].val; j++)
			bit.inc(qry[j].delt, 1);
		qry[i].ans += bit.get(m + 1) - bit.get(qry[i].delt);
	}
	for (i = mid + 1; i < j; i++)
		bit.inc(qry[i].delt, -1);
	
	i = r, j = mid;
	for (; i > mid; i--) {
		for (; j >= l && qry[i].val < qry[j].val; j--)
			bit.inc(qry[j].delt, 1);
		qry[i].ans += bit.get(m + 1) - bit.get(qry[i].delt);
	}
	for (i = mid; i > j; i--)
		bit.inc(qry[i].delt, -1);
	
	inplace_merge(qry + l, qry + mid + 1, qry + r + 1, cmp_val);
}

signed main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		fill(loc + 1, loc + 1 + n, 0);
		fill(qry + 1, qry + 1 + n, query());
		
		for (register int i = 1; i <= n; i++) {
			scanf("%d", &qry[i].val);
			qry[i].delt = m + 1;
			loc[qry[i].val] = i;
		}
		for (register int i = 1, p; i <= m; i++) {
			scanf("%d", &p);
			qry[loc[p]].delt = i;
		}
		
		long long cnt = 0ll;
		for (register int i = 1; i <= n; i++) {
			cnt += bit.get(n) - bit.get(qry[i].val);
			bit.inc(qry[i].val, 1);
		}
		for (register int i = 1; i <= n; i++)
			bit.inc(qry[i].val, -1);
		
		cdqSolve(1, n);
		
		sort(qry + 1, qry + 1 + n, cmp_delt);
		for (register int i = 1; i <= m; i++) {
			printf("%lld
", cnt);
			cnt -= qry[i].ans;
		}	
	}
	return 0;
}

Solution 2

树状数组套动态开点权值线段树（带修主席树）

这玩意就不这么复杂了啊。首先还是计算好原先的逆序对数。

差不多就是，当一个数 (a_i) 被删去时，逆序对数应减去，区间 ([1, i)) 中处在值域 ((a_i, n]) 的数的个数，以及区间 (（i, n]) 中处在值域 ([1, a_i)) 的数的个数。

分开来算的话，要写两个冗长的函数，但其实可以打一个记号，就像上面一样，这样就能写成一个了。常数比较大，于是跑不过cdq。

  • 时间复杂度：(O((n + m)log^2 n))
  • 空间复杂度：(O((n + m)log^2 n))
  • 是否在线：是

Code for Solution 2

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : Luogu P3157 CQOI2011 动态逆序对 / UVA 11990 ``Dynamic'' Inversion
 */
#include <cstdio>

using namespace std;
const int N = 2e5 + 5;
const int S = N << 7;
#define lbt(x) (x & (-x))
#define mid ((l + r) >> 1)

int n, m;
int val[N], loc[N];
long long cnt = 0ll;

int root[N];
int lc[S], rc[S];
int size[S];
int total = 0;

void modify(int& x, int l, int r, int p, int v) {
	if (!x) x = ++total;
	size[x] += v;
	if (l == r) return;
	if (p <= mid) modify(lc[x], l, mid, p, v);
	else modify(rc[x], mid + 1, r, p, v);
}

int node[2][N];
inline int get(int l, int r, int x, bool tag) {
	int cnt[2] = {0, 0}, ret = 0;
	for (register int p = r; p; p -= lbt(p)) node[0][++cnt[0]] = root[p];
	for (register int p = l - 1; p; p -= lbt(p)) node[1][++cnt[1]] = root[p];
	
	for (l = 1, r = n; l != r; )
		if (x > mid) {
			if (tag) {
				for (register int i = 1; i <= cnt[0]; i++) ret += size[lc[node[0][i]]];
				for (register int i = 1; i <= cnt[1]; i++) ret -= size[lc[node[1][i]]];
			}
			for (register int i = 1; i <= cnt[0]; i++) node[0][i] = rc[node[0][i]];
			for (register int i = 1; i <= cnt[1]; i++) node[1][i] = rc[node[1][i]];
			l = mid + 1;
		} else {
			if (!tag) {
				for (register int i = 1; i <= cnt[0]; i++) ret += size[rc[node[0][i]]];
				for (register int i = 1; i <= cnt[1]; i++) ret -= size[rc[node[1][i]]];
			}
			for (register int i = 1; i <= cnt[0]; i++) node[0][i] = lc[node[0][i]];
			for (register int i = 1; i <= cnt[1]; i++) node[1][i] = lc[node[1][i]];
			r = mid;
		}
	return ret;
}

void clear(int x) {
	if (!x) return;
	clear(lc[x]), clear(rc[x]);
	lc[x] = rc[x] = size[x] = 0;
}

signed main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		for (register int i = 1; i <= n; i++)
			clear(root[i]), root[i] = 0, loc[i] = val[i] = 0;
		total = cnt = 0;
		
		for (register int i = 1; i <= n; i++) {
			scanf("%d", val + i), loc[val[i]] = i;
			cnt += get(1, i - 1, val[i], 0);
			for (register int p = i; p <= n; p += lbt(p))
				modify(root[p], 1, n, val[i], 1);
		}
		
		for (register int x; m; --m) {
			scanf("%d", &x);
			printf("%lld
", cnt);
			cnt -= get(1, loc[x] - 1, x, 0);
			cnt -= get(loc[x] + 1, n, x, 1);
			for (register int p = loc[x]; p <= n; p += lbt(p))
				modify(root[p], 1, n, x, -1);
		}	
	}
	return 0;
}

Solution 3

线段树套平衡树。

另一种树套树方法，套路和 Solution 2 基本一样。

常数大一点，空间小一点。做法这里不做赘述。

  • 时间复杂度：(O((n + m)log^2 n))
  • 空间复杂度：(O(nlog n))
  • 是否在线：是

Code 不想写了 /kel 可以参考一下：https://www.luogu.com.cn/blog/van/solution-uva11990

Solution 4

K-D Tree。

既然可以转化成三维数点问题然后 cdq，那么K-D Tree自然也是可以的。

先把树建好，然后一个个删除。（当然你也可以离线然后倒着操作换成插入）

考虑到是惰性删除，所以可以定期重构来优化。一般来说因为常数因子的影响，其实跑得比大多数树套树快。

  • 时间复杂度：(O(nlog n + mn^{frac{2}{3}}))
  • 空间复杂度：(O(n))
  • 是否在线：是

Solution 5

数列分块套树状数组。 块乐

先分个块，每个块维护一个树状数组。删除数值 (x) 时，在每个块的树状数组中 (x) 的位置减去一，然后答案动态维护。

如果常数小可以过。

  • 时间复杂度：(O(msqrt{n}log n))（块长为 (sqrt{n}) 时，但取 (10^3) 差不多效率可以更高）
  • 空间复杂度：(O(nsqrt{n}))
  • 是否在线：是

相关推荐