fork download

copy

/// Implicit Treap - muoii
 
class trarr{
public:
 
    typedef struct item{
        int val,prior,cnt;
 
        item *l,*r;
 
        item(const int &v): val(v), l(nullptr), r(nullptr), cnt(1) { prior = (rand() << 16) | rand(); }
 
        void push() {
        }
 
        void recalc() {
			cnt = 1 + count(l) + count(r);
        }
 
        static int count(item* ptr) {
            return ptr?ptr->cnt:0;
        }
    } *pitem;
 
	pitem merge(pitem l, pitem r)
	{
		if(!l || !r) return l?l:r;
 
		if (l->prior < r->prior)
        {
			l->push();
			l->r = merge(l->r, r);
			l->recalc();
			return l;
		}
		else
        {
			r->push();
			r->l = merge(l, r->l);
			r->recalc();
			return r;
		}
	}
 
	void split(pitem node, int idx, pitem& l, pitem& r)
	{
		l = r = nullptr;
		if (!node) return;
 
		node->push();
 
		if (count(node->l) < idx)
        {
			l = node;
			split(l->r, idx - count(node->l) - 1, l->r, r);
			l->recalc();
		}
		else
        {
			r = node;
			split(r->l, idx, l, r->l);
			r->recalc();
		}
	}
 
public:
 
    static int count(pitem ptr) { return ptr?ptr->cnt:0;}
    pitem root=0;
    size_t siz=0;
 
	size_t size() const{
		return siz;
	}
 
	void insert(const int &idx,const int &val)
	{
		pitem l=0,r=0;
 
		split(root, idx, l, r);
 
		pitem cur = new item(val);
 
		root = merge(merge(l,cur),r);
 
		++siz;
	}
 
	void erase(const int &idx)
    {
		pitem l=0,m=0,r=0;
 
		split(root, idx, l, r);
		split(r, 1, m, r);
 
		root = merge(l, r);
 
		--siz;
	}
 
	void replace(const int &idx,const int &val)
	{
	    erase(idx);
	    insert(idx,val);
	}
 
    void push_front(const int &val) {
		return insert(0,val);
	}
	void push_back(const int &val) {
		return insert(siz,val);
	}
	void pop_front()
	{
	    erase(0);
	    --siz;
	}
	void pop_back()
	{
	    erase(--siz);
	}
 
	pitem operator [](const int &idx)
	{
		pitem l=0,m=0,r=0;
 
		split(root,idx,l,r);
		split(r,1,m,r);
 
		if (!m) throw runtime_error("IndexitemOutOfBound");
 
		root = merge(merge(l, m), r);
		return m;
	}
 
	/// query:
	/// sum,max/min
};

prog.cpp:70:5: error: ‘size_t’ does not name a type
     size_t siz=0;
     ^~~~~~
prog.cpp:72:2: error: ‘size_t’ does not name a type
  size_t size() const{
  ^~~~~~
prog.cpp: In constructor ‘trarr::item::item(const int&)’:
prog.cpp:11:84: error: ‘rand’ was not declared in this scope
         item(const int &v): val(v), l(nullptr), r(nullptr), cnt(1) { prior = (rand() << 16) | rand(); }
                                                                                    ^
prog.cpp: In member function ‘void trarr::insert(const int&, const int&)’:
prog.cpp:86:5: error: ‘siz’ was not declared in this scope
   ++siz;
     ^~~
prog.cpp: In member function ‘void trarr::erase(const int&)’:
prog.cpp:98:5: error: ‘siz’ was not declared in this scope
   --siz;
     ^~~
prog.cpp: In member function ‘void trarr::push_back(const int&)’:
prog.cpp:111:17: error: ‘siz’ was not declared in this scope
   return insert(siz,val);
                 ^~~
prog.cpp:111:24: error: return-statement with a value, in function returning 'void' [-fpermissive]
   return insert(siz,val);
                        ^
prog.cpp: In member function ‘void trarr::pop_front()’:
prog.cpp:116:8: error: ‘siz’ was not declared in this scope
      --siz;
        ^~~
prog.cpp: In member function ‘void trarr::pop_back()’:
prog.cpp:120:14: error: ‘siz’ was not declared in this scope
      erase(--siz);
              ^~~
prog.cpp: In member function ‘trarr::item* trarr::operator[](const int&)’:
prog.cpp:130:52: error: ‘runtime_error’ was not declared in this scope
   if (!m) throw runtime_error("IndexitemOutOfBound");
                                                    ^

Standard output is empty