盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 4988 Little Pony and Boast Busters(动态逆序对 树状数组+treap)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4988

题意

给定上下两个排列 A[], B[],要求询问相同项之间两两连线的交叉数,并支持交换操作

思路

题解: http://www.shuizilong.com/house/archives/bestcoder-round-7-solution/
静态问题就是求排列 P[] 的逆序对
其中 P[i] = pA[B[i]](这里 pA[] 是 A[] 中某个元素的位置 类似的 pB[] 是 B[] 中某个元素的位置)
考察交换操作,无论是交换下排还是上排,都可以看成交换 P[] 中的两项
于是转化成动态逆序对问题,支持修改排列中的任意一项。
动态逆序对问题等价于区间 kth 大值(区间 Rank)问题。。可以用经典的树套树方法
复杂度 O(nlog2n)。

http://blog.csdn.net/u013654696/article/details/38964519
http://blog.csdn.net/cq_phqg/article/details/39070857

这里其实就是每一个树状数组的结点都是一颗SBT。

代码

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int N = 100005;
struct SBT{
//左子树指针,右子树指针,大小,键值
int left,right,size,key;
inline void Init(){
left=right=key=0;
size=1;
}
}T[N * 50];
int tot; //根的位置以及节点个数
//左旋转处理
inline void Left_rot(int &x){
int k=T[x].right;
T[x].right=T[k].left;
T[k].left=x;
T[k].size=T[x].size;
T[x].size=T[T[x].left].size+T[T[x].right].size+1;
x=k;
}
//右旋转处理
inline void Right_rot(int &x){
int k=T[x].left;
T[x].left=T[k].right;
T[k].right=x;
T[k].size=T[x].size;
T[x].size=T[T[x].left].size+T[T[x].right].size+1;
x=k;
}
//调整处理
void Maintain(int &r,bool flag){
if(flag){ //更新右子树
if(T[T[T[r].right].right].size>T[T[r].left].size)
Left_rot(r);
else if(T[T[T[r].right].left].size>T[T[r].left].size){
Right_rot(T[r].right);
Left_rot(r);
}
else
return;
}
else{ //更新在左子树
if(T[T[T[r].left].left].size>T[T[r].right].size)
Right_rot(r);
else if(T[T[T[r].left].right].size>T[T[r].right].size){
Left_rot(T[r].left);
Right_rot(r);
}
else
return;
}
//更新子树,然后再更新根,直到平衡为止
Maintain(T[r].left,false);
Maintain(T[r].right,true);
Maintain(r,false);
Maintain(r,true);
}
//插入新节点
void Insert(int &r,int k){
if(r==0){
r=++tot;
T[r].Init();
T[r].key=k;
}
else{
T[r].size++;
if(k<=T[r].key)
Insert(T[r].left,k);
else
Insert(T[r].right,k);
//插入后要调整,保证平衡
Maintain(r,k>=T[r].key);
}
}
//删除结点,利用的是前驱替换
int d_key;
void Remove(int &r,int k){
if(!r)
return ;
T[r].size--;
//前者说明就是要删的节点,后两者说明不存在此节点
if(T[r].key==k||(T[r].left==0&&k<T[r].key)||(T[r].right==0&&k>T[r].key)){
if(T[r].left&&T[r].right) {
Remove(T[r].left,k+1);
T[r].key = d_key;
}
else {
d_key = T[r].key;
r=T[r].left+T[r].right;
}
}
else Remove(k<=T[r].key?T[r].left:T[r].right,k);
}
//取得最大值,即一直遍历到最右的结点
int Get_Max(int r){
while(T[r].right)
r=T[r].right;
return r;
}
//取得最小值,即一直遍历到最左的结点
int Get_Min(int r){
while(T[r].left)
r=T[r].left;
return r;
}
//获得前驱
int Get_Pre(int &r,int y,int k){
if(r==0) return y;
if(k>T[r].key)
Get_Pre(T[r].right,r,k);
else
Get_Pre(T[r].left,y,k);
}
//获得后继
int Get_Next(int &r,int y,int k){
if(r==0) return y;
if(k<T[r].key)
Get_Next(T[r].left,r,k);
else
Get_Next(T[r].right,y,k);
}
//取得第K小的数,注:暂不能解决有重复数的
int Get_Kth(int &r,int k){
int t=T[T[r].left].size+1;
if(t==k) return T[r].key;
if(t<k) return Get_Kth(T[r].right,k-r);
else return Get_Kth(T[r].left,k);
}
//获得结点的名次
int Get_Rank(int r,int k){
int ans = 0;
while (r) {
if (T[r].key < k) {
ans += T[T[r].left].size + 1;
r = T[r].right;
}
else r = T[r].left;
}
return ans;
}
//排序
void Inorder(int &r){
if(r==0) return;
Inorder(T[r].left);
printf("%d\n",T[r].key);
Inorder(T[r].right);
}
int n, pa[N], pb[N], root[N], a[N], b[N], p[N];
LL ans;
inline int lowbit(int x) {
return x & (-x);
}
inline int Rank(int x, int v) {
int ret = 0;
for (int i = x; i; i -= lowbit(i))
ret += Get_Rank(root[i], v);
return ret;
}
inline void Add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i))
Insert(root[i], v);
}
inline void Del(int x, int v) {
for (int i = x; i <= n; i += lowbit(i))
Remove(root[i], v);
}
inline void init() {
tot = 0; ans = 0;
for (int i = 1; i <= n; i++) {
root[i] = 0;
pa[a[i]] = i;
pb[b[i]] = i;
}
for (int i = 1; i <= n; i++) {
int num = pa[b[i]];
ans += Rank(i, num);
Add(i, num); p[i] = num;
}
}
inline void update (int x , int v) {
// postion x , from p[x] to v
int pre = p[x];
Del (x , pre);
ans = ans - (Rank (x - 1 , pre) + (n - x - (Rank (n , pre + 1) - Rank (x , pre + 1))));
p[x] = v;
ans = ans + (Rank (x - 1 , v) + (n - x - (Rank (n , v + 1) - Rank (x , v + 1))));
Add (x , v);
}
inline void update (int k , int A , int B) {
if (k == 0) {
swap (a[A] , a[B]);
pa[a[A]] = A;pa[a[B]] = B;
update (pb[a[A]] , A);
update (pb[a[B]] , B);
}
else {
swap (b[A] , b[B]);
pb[b[A]] = A;pb[b[B]] = B;
update (A , pa[b[A]]);
update (B , pa[b[B]]);
}
}
int main () {
while(~scanf("%d", &n)) {
for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i]++;
for (int i = 1; i <= n; i++) scanf("%d", b + i), b[i]++;
init();
int q, k, A, B;
char op[10];
scanf("%d", &q);
LL ret = (LL)n * (n - 1) / 2;
while(q--) {
scanf("%s", op);
if (op[0] == 'Q') printf("%I64d\n", ret - ans);
else {
scanf("%d%d%d", &k, &A, &B);
A++, B++;
update(k, A, B);
}
}
}
return 0;
}