题解 - [Luogu P5462]【X 龙珠】

发表于 更新于 分类于 ， 本文字数： 164 阅读时长 ≈ 1 分钟

题目

我太菜了，只会用线段树 + 双向链表做 QwQ

在读入时直接将序列转化成可能输出的数对

如样例 1 为 (3,1),(1,4),(4,2)

线段树维护全局最大数对 , 双向链表便于寻找前驱后继

每次直接输出最大数对并删除与它有交集的数对

另外有一点需要注意:

如果最大数对出现在中间时，在删除自身、前驱和后继后会产生一个新的数对

例如 (3,4),(4,2),(2,1) 删除之后会产生数对 (3,1)

Show code

Luogu_P5462view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#define _for(i, l, r) for (int i = (l); i <= (r); ++i)
#define _rep(i, l, r) for (int i = (l); i < (r); ++i)
template <typename A>
A Max(const A &x, const A &y) {
  return x < y ? y : x;
}
template <typename A>
A Min(const A &x, const A &y) {
  return x < y ? x : y;
}
template <typename A>
void Swap(A &x, A &y) {
  x ^= y ^= x ^= y;
}
template <typename A>
A Abs(const A &x) {
  return x > 0 ? x : -x;
}
template <typename A>
A Gcd(A x, A y) {
  return !y ? x : Gcd(y, x % y);
}
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = ' ';
int p, p3 = -1;
int getc() {
  return p1 == p2 &&
             (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
           EOF :
           *p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  int f = 0;
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getc();
  }
  if (f) x = -x;
  read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = hh;
  print(oth...);
}
}  // namespace FastIO
#define read FastIO::read
#define print FastIO::print
const int N = 1e5 + 5;
namespace Seg {
#define _now tree[p]
#define _lch tree[p].l
#define _rch tree[p].r
struct node {
  int first, second, pos;
} pair[N];
struct segtree {
  node val;
  int l, r;
  bool operator<(const segtree &a) const {
    return (val.first == a.val.first) ? val.second < a.val.second :
                                        val.first < a.val.first;
  }
  void pt() { print(val.first, val.second); }
} tree[N << 2];
int cnt;
node _max(const segtree &a, const segtree &b) { return a < b ? b.val : a.val; }
void push_up(int p) { _now.val = _max(tree[_lch], tree[_rch]); }
void build(int &p, int l, int r) {
  p = ++cnt;
  if (l == r) {
    _now = {pair[l], 0, 0};
    return;
  }
  int mid = l + ((r - l) >> 1);
  build(_lch, l, mid);
  build(_rch, mid + 1, r);
  push_up(p);
}
void del(int p, int l, int r, int target) {
  if (_now.val.first == -1) return;
  if (l == r) {
    _now = {pair[target] = {-1, -1, target}, 0, 0};
    return;
  }
  int mid = l + ((r - l) >> 1);
  if (target <= mid) del(_lch, l, mid, target);
  else del(_rch, mid + 1, r, target);
  push_up(p);
}
void modify(int p, int l, int r, int target, const node &a) {
  if (l == r) {
    _now = {pair[target] = a, 0, 0};
    return;
  }
  int mid = l + ((r - l) >> 1);
  if (target <= mid) modify(_lch, l, mid, target, a);
  else modify(_rch, mid + 1, r, target, a);
  push_up(p);
}
}  // namespace Seg
struct list {
  int pre, suc;
} id[N];
int head, rear;
int a[N], n;
void del_rear(const int &p, const int &pre) {
  Seg::del(1, 1, n, p);
  Seg::del(1, 1, n, pre);
  rear = id[pre].pre;
  id[pre].pre = id[rear].suc = 0;
}
void del_head(const int &p, const int &suc) {
  Seg::del(1, 1, n, p);
  Seg::del(1, 1, n, suc);
  head = id[suc].suc;
  id[suc].suc = id[head].pre = 0;
}
void del(const int &p, const int &pre, const int &suc) {
  Seg::modify(1, 1, n, p, {Seg::pair[pre].first, Seg::pair[suc].second, p});
  Seg::del(1, 1, n, pre);
  if (!id[pre].pre) head = p;
  else id[id[pre].pre].suc = p;
  id[p].pre = id[pre].pre;
  Seg::del(1, 1, n, suc);
  if (!id[suc].suc) rear = p;
  else id[id[suc].suc].pre = p;
  id[p].suc = id[suc].suc;
}
int main() {
  read(n);
  _for(i, 1, n) read(a[i]);
  --n;
  _for(i, 1, n) {
    Seg::pair[i] = {a[i], a[i + 1], i};
    id[i] = {i - 1, i + 1};
  }
  int tmp1;
  head = 1;
  rear = n;
  id[n].suc = 0;
  Seg::build(tmp1, 1, n);
  _rep(i, 1, (n + 1) >> 1) {
    Seg::tree[1].pt();
    int tmp = Seg::tree[1].val.pos;
    int suc = id[tmp].suc, pre = id[tmp].pre;
    if (tmp == rear) del_rear(tmp, pre);
    else if (tmp == head) del_head(tmp, suc);
    else del(tmp, pre, suc);
  }
  Seg::tree[1].pt();
  --FastIO::p3;
  FastIO::flush();
  return 0;
}