OI / Data Structure
14 minutes read (About 2026 words)

「BZOJ 4552」排序-平衡树 + fingerSearch/线段树分裂合并

给出一个 $n$ 的排列，进行 $m$ 次操作，每次操作是将一个区间升序或降序排序。
请你输出 $m$ 次操作后第 $p$ 个位置的值。

链接

BZOJ 4552

题解

线段树分裂合并

首先对于每个位置维护一颗权值线段树，其权值范围均为 $1 \sim n$。
然后对于每次排序操作就是对应区间的若干棵权值线段树的合并，但是我们要合并的线段树所在的区间可能包含在其他的权值线段树中，所以我们需要支持分裂操作。
然后我们用平衡树维护权值线段树对应的区间，这个用 set 维护就好了。
对于查询操作，就是在对应的权值线段树中求第 $k$ 大。

时间复杂度 $O(n \log n + m \log n)$。

平衡树???

权值线段树在这种情况下难道不能当平衡树用???
不就是空间 $O(n \log V)$，所以平衡树的做法和上面没区别，太久没写平衡树合并了就写了一下。
然后无旋 Treap 的启发式合并（其他可能能过吧）就 TLE 了。
抱着试试的心态写了 fingerSearch，然后比线段树合并还快!!!!!
翻了翻论文，Treap 的 fingerSearch 和红黑树差不多，合并两棵大小为 $n, m$ 的 Treap，复杂度为 $O(m \log(\frac n m))$，所以从同样大小级别的 Treap 开始合并，复杂度为 $O(n \log n)$。

以前只知道红黑树合并比线段树快，没想到无旋 Treap 也这么快…

以下是论文：

代码

无旋 Treap + fingerSearch

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
249
250
251
252
253
254
255
256
257
258
259
260
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「BZOJ 4552」排序 21-09-2017
 * 平衡树 + fingerSearch
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline bool read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return false;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
    return true;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

const int MAXN = 100000;

typedef unsigned int uint;
inline uint nextUint() {
    static uint seed = 495;
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

struct Node {
    Node *lc, *rc;
    int size, key;
    uint rank;

    inline void *operator new(size_t);

    inline void maintain() { size = lc->size + rc->size + 1; }

    Node();
    Node(int);
} pool[MAXN + 1], *null = pool, *cur = pool + 1;

inline void *Node::operator new(size_t) { return cur++; }

Node::Node() : lc(null), rc(null), size(0), rank(nextUint()), key(0) {}

Node::Node(int key) : lc(null), rc(null), size(1), rank(nextUint()), key(key) {}

inline Node *merge(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->rank < v->rank)
        return u->rc = merge(u->rc, v), u->maintain(), u;
    else
        return v->lc = merge(u, v->lc), v->maintain(), v;
}

typedef std::pair<Node *, Node *> Pair;

inline int query(Node *p, int k) {
    for (; p != null;) {
        if (p->lc->size + 1 == k)
            return p->key;
        else if (p->lc->size >= k)
            p = p->lc;
        else
            k -= p->lc->size + 1, p = p->rc;
    }
}

inline Pair split(Node *u, int v) {
    if (u == null) return Pair(null, null);
    Pair t;
    if (u->key < v) {
        t = split(u->rc, v);
        u->rc = t.first, t.first = u;
    } else {
        t = split(u->lc, v);
        u->lc = t.second, t.second = u;
    }
    u->maintain();
    return t;
}

inline Node *fingerSearch(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->rank > v->rank) std::swap(u, v);
    Pair t = split(v, u->key);
    u->lc = fingerSearch(u->lc, t.first);
    u->rc = fingerSearch(u->rc, t.second);
    u->maintain();
    return u;
}

bool type[MAXN + 1];
Node *root[MAXN + 1];
int end[MAXN + 1];
std::set<int> s;

inline void split(int x, int pos) {
    if (pos >= end[x] || pos < x) return;
    if (!type[x]) {
        Pair t = split(root[x], query(root[x], pos - x + 1) + 1);
        root[x] = t.first, root[pos + 1] = t.second;
    } else {
        root[pos + 1] = root[x];
        Pair t = split(root[pos + 1], query(root[pos + 1], end[x] - pos) + 1);
        root[pos + 1] = t.first, root[x] = t.second;
    }
    end[pos + 1] = end[x], end[x] = pos;
    s.insert(pos + 1), type[pos + 1] = type[x];
}

int n, q;

inline void merge(int a, int b) {
    if (a == b) return;
    s.erase(b);
    root[a] = fingerSearch(root[a], root[b]);
    end[a] = end[b];
}

inline int query(int x, int k) {
    k -= x - 1;
    if (!type[x])
        return query(root[x], k);
    else
        return query(root[x], end[x] - x + 2 - k);
}

int a[MAXN + 1];

std::vector<int> test(int a) {
    std::vector<int> t;
    for (register int i = 1; i <= root[a]->size; i++) {
        t.push_back(query(root[a], i));
    }
    return t;
}

inline void solve() {
    io >> n >> q;
    for (int i = 1; i <= n; i++) {
        io >> a[i];
        root[i] = new Node(a[i]);
        s.insert(s.end(), i);
        end[i] = i;
    }

    static int tmp[MAXN], cnt = 0;
    for (register int cmd, l, r; q--;) {
        io >> cmd >> l >> r;
        split(*(--s.upper_bound(l)), l - 1);
        split(*(--s.upper_bound(r)), r);
        std::set<int>::iterator L = s.lower_bound(l), R = --s.upper_bound(r);
        register int pos = *L;
        if (L != R) {
            for (std::set<int>::iterator i = ++L;; i++) {
                tmp[++cnt] = *i;
                if (i == R) break;
            }
            for (register int i = 1; i <= cnt; i++) merge(pos, tmp[i]);
            cnt = 0;
        }
        type[pos] = cmd;
    }
    register int x;
    io >> x;
    io << query(*(--s.upper_bound(x)), x);
}
}

int main() {
    // freopen("sample/1.in", "r", stdin);
    solve();
    return 0;
}

线段树分裂合并

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
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「BZOJ 4552」排序 21-09-2017
 * 平衡树 + 线段树分裂合并
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline bool read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return false;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
    return true;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

const int MAXN = 100000;
const int MAX_LOG = 20;

struct Node {
    Node *lc, *rc;
    int size;

    inline void *operator new(size_t);

    inline void operator delete(void *);

    inline void maintain();

    Node();
} pool[MAXN * MAX_LOG + 1], *null = pool, *cur = pool + 1,
                            *bin[MAXN * MAX_LOG + 1];
int binTop;

inline void *Node::operator new(size_t) {
    return binTop ? bin[--binTop] : cur++;
}

inline void Node::operator delete(void *p) { bin[binTop++] = (Node *)p; }

Node::Node() : lc(null), rc(null), size(0) {}

inline void Node::maintain() { size = lc->size + rc->size + 1; }

inline Node *merge(Node *u, Node *v) {
    if (u == null) return v;
    if (v == null) return u;
    u->lc = merge(u->lc, v->lc);
    u->rc = merge(u->rc, v->rc);
    u->size += v->size, delete v;
    return u;
}

inline void split(Node *p, Node *&u, int k) {
    u = new Node();
    if (k > p->lc->size)
        split(p->rc, u->rc, k - p->lc->size);
    else
        std::swap(p->rc, u->rc);
    if (k < p->lc->size) split(p->lc, u->lc, k);
    u->size = p->size - k, p->size = k;
}

inline int query(Node *p, int l, int r, int k) {
    if (l == r) return l;
    register int mid = l + r >> 1;
    return p->lc->size < k ? query(p->rc, mid + 1, r, k - p->lc->size)
                           : query(p->lc, l, mid, k);
}

inline void insert(Node *&p, int l, int r, int v) {
    p = new Node();
    p->size = 1;
    if (l == r) return;
    register int mid = l + r >> 1;
    v <= mid ? insert(p->lc, l, mid, v) : insert(p->rc, mid + 1, r, v);
}

bool type[MAXN + 1];
Node *root[MAXN + 1];
int end[MAXN + 1];
std::set<int> s;

inline void split(int x, int pos) {
    if (pos >= end[x] || pos < x) return;
    if (!type[x]) {
        split(root[x], root[pos + 1], pos - x + 1);
    } else {
        root[pos + 1] = root[x];
        split(root[pos + 1], root[x], end[x] - pos);
    }
    end[pos + 1] = end[x], end[x] = pos;
    s.insert(pos + 1), type[pos + 1] = type[x];
}
int n, q;

inline void merge(int a, int b) {
    if (a == b) return;
    s.erase(b);
    root[a] = merge(root[a], root[b]);
    end[a] = end[b];
}

inline int query(int x, int k) {
    k -= x - 1;
    if (!type[x])
        return query(root[x], 1, n, k);
    else
        return query(root[x], 1, n, end[x] - x + 2 - k);
}

int a[MAXN + 1];

inline void solve() {
    io >> n >> q;
    for (int i = 1; i <= n; i++) {
        io >> a[i];
        insert(root[i], 1, n, a[i]);
        s.insert(s.end(), i);
        end[i] = i;
    }
    static int tmp[MAXN], cnt = 0;
    for (register int cmd, l, r; q--;) {
        io >> cmd >> l >> r;
        split(*(--s.upper_bound(l)), l - 1);
        split(*(--s.upper_bound(r)), r);
        std::set<int>::iterator L = s.lower_bound(l), R = --s.upper_bound(r);
        register int pos = *L;
        if (L != R) {
            for (std::set<int>::iterator i = ++L;; i++) {
                tmp[++cnt] = *i;
                if (i == R) break;
            }
            for (register int i = 1; i <= cnt; i++) merge(pos, tmp[i]);
            cnt = 0;
        }
        type[pos] = cmd;
    }
    register int x;
    io >> x;
    io << query(*(--s.upper_bound(x)), x);
}
}

int main() {
    // freopen("sample/1.in", "r", stdin);
    solve();
    return 0;
}
#
「HDU 3709」Balanced Number-数位 dp
「HDU 4773」Problem of Apollonius-圆的反演

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×