[toph.co] Bucket

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Bucket
Source            : toph.co
Category          : Data Structure
Algorithm         : Implicit Treap
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define FI              freopen("in.txt", "r", stdin)
#define FO              freopen("out.txt", "w", stdout)
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define FOR(i, n)       for (int i = 1; i <= n; i++)
#define For(i, n)       for (int i = 0; i < n; i++)
#define ROF(i, n)       for (int i = n; i >= 1; i--)
#define Rof(i, n)       for (int i = n-1; i >= 0; i--)
#define FORI(i, n)      for (auto i : n)
 
#define ll              long long
#define ull             unsigned long long
#define vi              vector <int>
#define vl              vector <ll>
#define pii             pair <int, int>
#define pll             pair <ll, ll>
#define mk              make_pair
#define ff              first
#define ss              second
#define eb              emplace_back
#define em              emplace
#define pb              push_back
#define ppb             pop_back
#define All(a)          a.begin(), a.end()
#define memo(a, b)      memset(a, b, sizeof a)
#define Sort(a)         sort(All(a))
#define ED(a)           Sort(a), a.erase(unique(All(a)), a.end())
#define rev(a)          reverse(All(a))
//#define sz(a)           (int)a.size()
#define max3(a, b, c)   max(a, max(b, c))
#define min3(a, b, c)   min(a, min(b, c))
#define maxAll(a)       *max_element(All(a))
#define minAll(a)       *min_element(All(a))
#define allUpper(a)     transform(All(a), a.begin(), :: toupper)
#define allLower(a)     transform(All(a), a.begin(), :: tolower)
#define endl            '\n'
#define nl              puts("")
#define ub              upper_bound
#define lb              lower_bound
#define Exp             exp(1.0)
#define PIE             2*acos(0.0)
#define Sin(a)          sin(((a)*PIE)/180.0)
#define EPS             1e-9
  
// int dr[] = {1, -1, 0, 0}; // 4 Direction
// int dc[] = {0, 0, 1, -1};
// int dr[] = {0, 0, 1, -1, 1, 1, -1, -1}; // 8 Direction
// int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
// int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
// int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
 
inline int setbit(int mask, int pos)        { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)      { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)     { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)     { return (bool)(mask & (1 << pos)); }
 
#define popcount(mask)                       __builtin_popcount(mask) // count set bit
#define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
 
inline int read()                           { int a; scanf("%d", &a); return a; }
inline ll readLL()                          { ll a; scanf("%lld", &a); return a; }
inline double readDD()                      { double a; scanf("%lf", &a); return a; }
 
template <typename T> string toString(T num) { stringstream ss; ss << num; return ss.str(); }
int toInt(string s)                          { int num; istringstream iss(s); iss >> num; return num;  }
ll toLLong(string s)                         { ll num; istringstream iss(s); iss >> num; return num; }
 
#define inf             1e17
//#define mod             1000000007
 
static const int maxn = 1e5 + 5;
static const int logn = 18;
static const ll mod = 1e9 + 7;
 
 
struct node
{
      int val, pos;
      int priority, sze;
      node *lft, *rgt;
      node(int v = 0, int p = 0)
      {
            this->val = v;
            this->pos = p;
            this->priority = rand();
            this->sze = 1;
            this->lft = this->rgt = nullptr;
      }
};
 
typedef node*              pnode;
 
inline int sz(pnode t)
{
      if (t) return t->sze;
      return 0;
}
 
inline void updateSize(pnode t)
{
      if (t) t->sze = sz(t->lft) + 1 + sz(t->rgt);
}
 
inline void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
      // 'pos' goes to left subtree
      if (t == nullptr) return void(l = r = nullptr);
      int curr = sz(t->lft) + add;
      if (curr <= pos) Split(t->rgt, t->rgt, r, pos, curr+1), l = t;
      else Split(t->lft, l, t->lft, pos, add), r = t;
      updateSize(t);
}
 
inline void Merge(pnode &t, pnode l, pnode r)
{
      if (l == nullptr || r == nullptr) t = l ? l : r;
      else if (l->priority < r->priority) Merge(r->lft, l, r->lft), t = r;
      else Merge(l->rgt, l->rgt, r), t = l;
      updateSize(t);
}
 
inline int Search(pnode t, int val, int add = 0)
{
      if (t == nullptr) return -1;
      int curr = sz(t->lft) + add;
      if (t->val == val) return curr;
      else if (t->val < val) return Search(t->rgt, val, curr+1);
      else return Search(t->lft, val, add);
}
 
inline int searchPosition(pnode t, int val, int add = 0)
{
      if (t == nullptr) return add;
      int curr = sz(t->lft) + add;
      if (t->val < val) return searchPosition(t->rgt, val, curr+1);
      else return searchPosition(t->lft, val, add);
}
 
inline pnode Insert(pnode t, pnode newnode, int pos)
{
      pnode L, R;
      Split(t, L, R, pos-1);
      Merge(t, L, newnode);
      Merge(t, t, R);
      return t;
}
 
inline void Erase(pnode &t, int pos)
{
      pnode L, R, mid;
      Split(t, L, R, pos-1);
      Split(R, mid, t, 0);
      free(mid);
      Merge(t, L, t);
}
 
inline void EraseFront(pnode &t, int l)
{
      pnode L, R;
      Split(t, L, R, l-1);
      t = R;
}
 
inline void display(pnode t);
 
inline void EraseBack(pnode &t, int l)
{
      pnode L, R;
      Split(t, L, R, l);
      t = L;
}
 
inline void display(pnode t)
{
      if (t == nullptr) return;
      display(t->lft);
      trace1(t->val);
      display(t->rgt);
}
 
inline pnode kth(pnode t, int k)
{
      if (t == nullptr) return new node(-1, -1);
      int curr = sz(t->lft) + 1;
      if (curr == k) return t;
      if (curr < k) return kth(t->rgt, k - curr);
      else return kth(t->lft, k);
}
 
struct information
{
      int val, pos;
      information(int val = 0, int pos = 0) : val(val), pos(pos) {}
      inline bool operator < (const information &p) const
      {
            return pos < p.pos;
      }
};
 
int main()
{
      //FI;
      pnode treap = nullptr;
      int q = read();
      int p = 0;
      FOR(_q, q)
      {
            int type = read();
            int x = read();
            if (type == 1)
            {
                  int src = Search(treap, x);
                  if (src == -1)
                  {
                        int pos = searchPosition(treap, x);
                        treap = Insert(treap, new node(x, ++p), pos);
                  }
            }
            else if (type == 2)
            {
                  int src = Search(treap, x);
                  if (src != -1)
                  {
                        Erase(treap, src);
                  }
            }
            else if (type == 3)
            {
                  int src = Search(treap, x);
                  if (src != -1)
                  {
                        EraseFront(treap, src);
                  }
                  else
                  {
                        int pos = searchPosition(treap, x);
                        EraseFront(treap, pos);
                  }
            }
            else
            {
                  int src = Search(treap, x);
                  if (src != -1)
                  {
                        EraseBack(treap, src);
                  }
                  else
                  {
                        int pos = searchPosition(treap, x);
                        EraseBack(treap, pos-1);
                  }
            }
      }
      vector <information> ans;
      for (int i = 1; ; i++)
      {
            pnode k = kth(treap, i);
            if (k->pos == -1) break;
            ans.eb(k->val, k->pos);
      }
      Sort(ans);
      int len = ans.size();
      For(i, len)
      {
            printf("%d", ans[i].val);
            if (i+1 == len) puts("");
            else printf(" ");
      }
}