1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 数据结构和算法

【Codeforces-420D】Cup Trick(无旋treap-平衡树)

• 数据结构和算法 • 阅读 135

题目传送门：https://codeforces.com/problemset/problem/420/D

题意：给出m次操作，每次操作输入两个值x，y，将y位置值为x的数移到最前面，让你求一个长度为n的初始序列满足所要进行操作的条件。

思路：由于初始序列未知，我们可以将序列都设为0，然后按操作进行，如果进行操作时，y位置为0，说明这个位置没有动过，可以为之前操作中没有操作过的值（比如说，如果你上一步操作把3位置的1移到了最前面，那么这一步操作你不能将这个位置的1移到最前面，因为这个位置的值不是1，如果这个位置在最前面的话，那么位置的值就不是0而是1了），那么我们可以将这个位置的值设为x，并移到最前面的位置，如果在操作的过程中遇到了重复操作的值，或者位置上的值与所操作的值不吻合的话说明这个初始序列是不存在的，那么就直接输出-1。

具体实现：我们可以用平衡树来维护这个序列，利用平衡树是有序的，来维护每次操作将值移到最前面的过程，我们可以将平衡树的val作为序列排序的对比值，大的val在最后面，小的val在最前面，每次操作可以是之前的val-1就可以了，emm，具体实现还是看代码吧。

  1 #pragma GCC optimize("O3")
  2 #pragma G++ optimize("O3")
  3
  4 #include
  5 #include
  6 #include
  7 #include
  8 #include<set>
  9 #include
 10 #include
 11 //#define int long long
 12 using namespace std;
 13 const int MAXN = 2000010;
 14 const int MOD = 2147483647;
 15
 16 int inf = 2000005;
 17
 18 //inline int read() {
 19 //    char a = getchar();
 20 //    int x = 0, f = 1;//f判断正负数
 21 //    while (a < '0' || a > '9') {
 22 //        if (a == '-') f = -1;
 23 //        a = getchar();
 24 //    }
 25 //    while (a >= '0' && a  26 //        x = x * 10 + (a - '0');
 27 //        a = getchar();
 28 //    }
 29 //    return x * f;
 30 //}
 31 //inline void write(int x) {
 32 //    if (x < 0) {
 33 //        putchar('-');
 34 //        x = -x;
 35 //    }
 36 //    if (x > 9) write(x / 10);
 37 //    putchar(x % 10 + '0');
 38 //}
 39
 40 queue<int>q;
 41
 42 struct Node
 43 {
 44     int left;      //左子树
 45     int right;     //右子树
 46     int size;      //大小
 47     int val;       //值
 48     int key;       //平衡种子
 49     int real;
 50
 51 }tree[MAXN];
 52
 53 int root, tot;
 54
 55 inline int add(int val, int real) {
 56     tot++;
 57     tree[tot].size = 1;
 58     tree[tot].val = val;
 59     tree[tot].key = rand() % MOD;
 60     tree[tot].left = 0;
 61     tree[tot].right = 0;
 62     tree[tot].real = real;
 63
 64     return tot;
 65 }
 66
 67 inline void update_root(int now) {
 68     int left, right;
 69
 70     left = tree[now].left;
 71     right = tree[now].right;
 72
 73     tree[now].size = tree[left].size + tree[right].size + 1;
 74 }
 75
 76 //拆分(now原treap,a左子树,b右子树,val值)
 77 inline void split_new(int now, int& a, int& b, int val) {
 78     if (now == 0) {
 79         a = 0;
 80         b = 0;
 81         return;
 82     }
 83
 84     if (tree[now].val //now左子树中的所有值都小于now，
 85         a = now;
 86         split_new(tree[now].right, tree[a].right, b, val);
 87     }
 88     else {
 89         b = now;
 90         split_new(tree[now].left, a, tree[b].left, val);
 91     }
 92
 93     update_root(now);
 94 }
 95
 96 inline void merge_new(int& now, int a, int b) {
 97     if (a == 0 || b == 0) {
 98         now = a + b;
 99         return;
100     }
101
102     //按照key值合并(堆性质)
103     if (tree[a].key < tree[b].key) {
104         /**
105          * a树key值小于b树，那么b树属于a树的后代，因为b树恒大于a树，那么b树一定属于a树的右后代，
106          * a的左子树不变，直接赋给now，递归合并a的右子树和b
107          */
108         now = a;
109         merge_new(tree[now].right, tree[a].right, b);
110     }
111     else {
112         now = b;
113         merge_new(tree[now].left, a, tree[b].left);
114     }
115
116     update_root(now);
117 }
118
119 int pos, value;
120 inline void find_new(int now, int rank) {//找第k大
121     while (tree[tree[now].left].size + 1 != rank) {
122         if (tree[tree[now].left].size >= rank) {
123             now = tree[now].left;
124         }
125         else {
126             rank -= tree[tree[now].left].size + 1;
127             now = tree[now].right;
128         }
129     }
130     pos = tree[now].val;
131     value = tree[now].real;
132     //cout << tree[now].val << " " << tree[now].real << "\n";
133 }
134
135 inline void insert_new(int val, int real) {
136     int x, y, z;
137
138     x = 0;
139     y = 0;
140     z = add(val, real);
141     split_new(root, x, y, val);
142     merge_new(x, x, z);
143     merge_new(root, x, y);
144 }
145
146 inline void del_new(int val) {
147     int x, y, z;
148
149     x = y = z = 0;
150     split_new(root, x, y, val);
151     split_new(x, x, z, val - 1);
152     merge_new(z, tree[z].left, tree[z].right);
153     merge_new(x, x, z);
154     merge_new(root, x, y);
155 }
156
157 inline void get_rank(int val) {
158     int x, y;
159
160     x = y = 0;
161     split_new(root, x, y, val - 1);
162     cout << tree[x].size + 1 << "\n";
163     merge_new(root, x, y);
164 }
165
166 inline void get_val(int rank) {
167     find_new(root, rank);
168 }
169
170 inline void get_pre(int val) {
171     int x, y;
172
173     x = y = 0;
174     split_new(root, x, y, val - 1);
175     find_new(x, tree[x].size);
176     merge_new(root, x, y);
177 }
178
179 inline void get_next(int val) {
180     int x, y;
181
182     x = y = 0;
183     split_new(root, x, y, val);
184     find_new(y, 1);
185     merge_new(root, x, y);
186 }
187
188 int mp[2000010];
189 int vis[1000005];
190 int sp[2000010];
191
192 int main() {
193
194     ios::sync_with_stdio(false);
195     cin.tie(0);
196     cout.tie(0);
197     int n, m;
198     //cin >> n >> m;
199     int rem = 0;
200     cin >> n >> m;
201
202
203     //memset(tree, 0, sizeof(tree));
204
205     add(MOD, 0);
206     root = 1;
207     tree[root].size = 0;
208
209     /*insert_new(2, 99);
210     insert_new(1, 87);
211     insert_new(3, 35);
212     get_val(2);
213     del_new(2);
214     get_val(2);*/
215
216     /*3 3
217     1 3
218     2 3
219     3 3*/
220
221     int flag = 1;
222     for (int i = 1; i ) {
223         //s.insert(i);
224         insert_new(inf - i, 0);    //利用val值来排序，val只需要不断递减，就可以保证每次操作都可以移动到最前面
225         //get_val(1);
226     }
227     int cnt = inf - n;
228     set<int>::iterator it;
229     /*if (n == 1000000 && m == 1000000) {
230         cout << -1 << "\n";
231         return 0;
232     }*/
233     int x, y;
234     for (; m; --m) {
235         cin >> x >> y;
236         /*x = read();
237         y = read();*/
238         //if (i >= 500000) continue;
239         //if (!flag) continue;
240         get_val(y);
241         if (value == x || value == 0) {
242             if (value == 0 && vis[x]) {
243                 flag = 0;
244                 //write(-1);
245                 cout << -1;
246                 return 0;
247             }
248             del_new(pos);
249             insert_new(--cnt, x);
250
251             //if (!vis[x]) {
252             //    /*it = s.find(x);
253             //    s.erase(it);*/
254             //    sp[x] = 1;
255             //}
256             if (mp[pos] == 0 && !vis[x]) {
257                 mp[pos] = x;
258                 vis[x] = 1;
259                 sp[x] = 1;
260             }
261
262         }
263         else {
264             flag = 0;
265             //write(-1);
266             cout << -1;
267             return 0;
268             //cout << -1 << "\n";
269         }
270     }
271     /*if (n == 1000000 && m == 1000000) {
272         cout << -1 << "\n";
273         return 0;
274     }*/
275     if (flag) {
276         /*it = s.begin();
277         while (it != s.end()) {
278             q.push(*it);
279             it++;
280         }*/
281         for (int i = 1; i ) {
282             if (!sp[i]) {
283                 q.push(i);
284             }
285         }
286         /*for (int i = 1; i 287             get_val(i);
288             if (value == 0) {
289                 int p = q.front();
290                 q.pop();
291                 cout << p << " ";
292             }
293             else cout << value << " ";
294         }*/
295         //int itt = inf;
296         for (int i = inf - n; i 1; i++) {
297             // pp;
298             //mp[i] != 0 ? write(mp[i]), putchar(' ') : pp = q.front(), q.pop(), printf("%d", pp), putchar(' ');
299             if (mp[i] != 0) {
300                 //cout << mp[i] << " ";
301                 cout << mp[i] << " ";
302                 //putchar(' ');
303             }
304             else {
305                 int pp = q.front();
306                 q.pop();
307                 cout << pp << " ";
308                 /*write(pp);
309                 putchar(' ');*/
310             }
311         }
312     }
313     else cout << -1;
314
315     return 0;
316 }

永远热爱，永远向着光。

Original: https://www.cnblogs.com/wabi/p/16514118.html
Author: Kyrizer_W
Title: 【Codeforces-420D】Cup Trick(无旋treap-平衡树)

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587890/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球