Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Solution By Chynti :)
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 3e5+10;
- typedef struct Treap* treap;
- struct Treap {
- int x, y, cnt;
- treap l, r;
- Treap(int _x) {
- cnt = 1, x = _x, y = rand();
- l = r = NULL;
- }
- };
- int cnt(treap t) {
- return t ? t->cnt : 0;
- }
- void upd_cnt(treap t) {
- if (t)
- t->cnt = cnt(t->l) + cnt(t->r) + 1;
- }
- void spl(treap t, treap &l, treap &r, int x, int add = 1) {
- if (!t)
- return void(l = r = NULL);
- int cur_x = add + cnt(t->l);
- if (cur_x < x)
- spl(t->r, t->r, r, x, cur_x + 1), l = t;
- else
- spl(t->l, l, t->l, x, add), r = t;
- upd_cnt(l);
- upd_cnt(r);
- upd_cnt(t);
- }
- void mer(treap &t, treap l, treap r) {
- if (!l || !r)
- t = l ? l : r;
- else if (l->y > r->y)
- mer(l->r, l->r, r), t = l;
- else
- mer(r->l, l, r->l), t = r;
- upd_cnt(t);
- }
- treap t;
- int n, m;
- int p[N], a[N];
- vector <int> res;
- int find_set(int a) {
- if (p[a] == a)
- return a;
- return p[a] = find_set(p[a]);
- }
- void prin(treap t) {
- if (!t) return;
- prin(t->l);
- res.push_back(t->x);
- if (t->x) n--;
- if (!n) {
- cout << res.size() << endl;
- for (int i = 0; i < res.size(); i++)
- cout << res[i] << " ";
- exit(0);
- }
- prin(t->r);
- }
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= 300000; i++) {
- p[i] = i;
- mer(t, t, new Treap(0));
- }
- for (int i = 1, x; i <= n; i++) {
- scanf("%d", &x);
- treap a, b, c, d;
- spl(t, a, b, x);
- spl(b, b, c, find_set(x)+1 - cnt(a));
- spl(b, b, d, find_set(x) - cnt(a));
- mer(b, b, c);
- mer(b, new Treap(i), b);
- mer(t, a, b);
- p[find_set(x)] = find_set(x) + 1;
- }
- prin(t);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement