[BZOJ 2141] 排队

题目大意

给定长为 $n$ 的正整数序列 $\{a_i\}$ 以及 $m$ 次交换操作,求一开始以及每次操作后的逆序对数。

$1 \leqslant n \leqslant 20,000$

$1 \leqslant m \leqslant 2,000$

$1 \leqslant a_i \leqslant 1,000,000,000$

题目链接

BZOJ 2141

题解

CDQ 分治/三维偏序 + 离散化。

每次交换转化为两个删除和两个插入,求动态逆序对。

先让 $a_i = cnt - a_i + 1$ ( $cnt$ 为不同的数据数),求一次三维偏序(位置、操作时间、值),求出在某位置前面、之前的操作中、值比它大的个数。

再恢复 $a_i$ ,同时让 $pos_i = n - pos_i + 1$ ,再求一次三维偏序,求出在某位置后面、之前的操作中、值比它小的个数。

这样,我们求出来的其实是「某次操作新产生的逆序对数」,求一遍前缀和,依次输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 20005;
const int MAXM = 2005;
struct BinaryIndexedTree {
int c[MAXN], n;
BinaryIndexedTree(int n = 0) : n(n) {}
static int lowbit(int x) {
return x & -x;
}
void update(int pos, int d) {
#ifdef DBG
printf("update(%d), %d\n", pos, d);
#endif
for (int i = pos; i <= n; i += lowbit(i)) c[i] += d;
}
int query(int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i)) res += c[i];
#ifdef DBG
printf("query(%d) = %d\n", pos, res);
#endif
return res;
}
void clear(int pos) {
for (int i = pos; i <= n; i += lowbit(i)) {
if (c[i]) c[i] = 0;
else break;
}
}
};
struct Data {
int time, val, pos, *ans, sign;
Data() {}
Data(int time, int val, int pos, int *ans, int sign) : time(time), val(val), pos(pos), ans(ans), sign(sign) {}
bool operator<(const Data &another) const {
return pos < another.pos || (pos == another.pos && time < another.time)
|| (pos == another.pos && time == another.time && val < another.val);
}
#ifdef DBG
void print() const {
printf("Data: [time: %d, val: %d, pos: %d, sign: %d]\n", time, val, pos, sign);
}
#endif
} D[MAXN + (MAXM << 2)];
int h[MAXN];
int discretization(int n) {
static int set[MAXN];
std::copy(h, h + n, set);
std::sort(set, set + n);
int *end = std::unique(set, set + n);
for (int i = 0; i < n; i++) h[i] = std::lower_bound(set, end, h[i]) - set + 1;
return end - set;
}
int m;
void divide(Data *l, Data *r) {
#ifdef DBG
printf("divide in [%ld, %ld]\n", l - D + 1, r - D + 1);
#endif
if (l >= r) return;
static BinaryIndexedTree bit(m);
Data *mid = l + (r - l) / 2;
divide(l, mid), divide(mid + 1, r);
static Data temp[MAXN + (MAXM << 2)];
for (Data *p = temp, *pl = l, *pr = mid + 1; p <= temp + (r - l); p++) {
if (pr > r || (pl <= mid && pl->time <= pr->time)) {
*p = *pl++;
bit.update(p->val, p->sign);
} else {
*p = *pr++;
*p->ans += p->sign * bit.query(p->val - 1);
}
}
for (Data *p = temp, *q = l; q <= r; p++, q++) {
*q = *p;
bit.clear(p->val);
}
#ifdef DBG
printf("end divide in [%ld, %ld]\n", l - D + 1, r - D + 1);
#endif
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &h[i]);
m = discretization(n);
static int ans[MAXM];
int cnt = 0;
for (int i = 0; i < n; i++) D[cnt++] = Data(i + 1, h[i], i + 1, &ans[0], 1);
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int a, b;
scanf("%d %d", &a, &b);
D[cnt] = Data(cnt + 1, h[a - 1], a, &ans[i], -1);
cnt++;
D[cnt] = Data(cnt + 1, h[b - 1], b, &ans[i], -1);
cnt++;
D[cnt] = Data(cnt + 1, h[b - 1], a, &ans[i], 1);
cnt++;
D[cnt] = Data(cnt + 1, h[a - 1], b, &ans[i], 1);
cnt++;
std::swap(h[a - 1], h[b - 1]);
}
for (int i = 0; i < cnt; i++) D[i].val = m - D[i].val + 1;
std::sort(D, D + cnt);
#ifdef DBG
for (int i = 0; i < cnt; i++) D[i].print();
#endif
divide(D, D + cnt - 1);
for (int i = 0; i < cnt; i++) D[i].val = m - D[i].val + 1, D[i].pos = n - D[i].pos + 1;
std::sort(D, D + cnt);
#ifdef DBG
for (int i = 0; i < cnt; i++) D[i].print();
#endif
divide(D, D + cnt - 1);
for (int i = 1; i <= q; i++) ans[i] += ans[i - 1];
for (int i = 0; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}