This blog does not introduce anything essentially new, though it may sound like it. At best, a much more different and maybe more? intuitive way to implement this. This was previously discovered (and improved, generalized, etc.) here

Hello Codeforces,

Around a year ago, the problem Boardgame Expo was set in CEOI 2025. I think the editorial mentions using a DSU adapted to have deque-like undoing. Upon trying to actually upsolve this problem earlier this year, I remembered only that "deque-like undoing" was necessary, so I tried coming up with it. I'd actually note that the problem itself doesn't require the full range of deque-like operations, as the data structures only need to pop. So, the standard queue-like implementation works here, though with maybe some additional considerations.

So, realizing I've been duped and wrote an unnecessary algorithm, I decided to maybe publish this absolutely brilliant discovery with the world. I acknowledge that it is likely it is wrong.

A bunch of useless words to pad the blog

One may wonder why queue-like doesn't work here. One may also be quick to realize that the push/pop operations that may occur on the same end of the deque are complements of each other, which, given queue-like works on amortized time complexity, means that one could repeatedly do the supposed amortized operations to result in quadratic time complexity.

In my view, though better implementations may not necessarily structure the code around this idea, the queue-like algorithm interweaves two stack-like structures with the following property:

• The stack is formed of multiple buckets
• Each bucket has a fixed capacity and it may never hold a partial amount of elements in it (i.e. they're either full or empty)
• The effective stack is represented as the read of the elements from the last bucket to the first

Queue-like then establishes a list of buckets as powers of two. It works because as you push elements on a stack elements' potential increases (up to $$$log$$$ per element, depending on index of bucket any element is from), and when, from the same stack, you start popping elements, the count of operations is limited by the total sum of potentials (you may not move an element further left than the number of buckets actually are left).

Illustration of the structure of the queue-like algorithm.

So, the actual soul of this trick is this power-of-two structured stack. I feel like once someone told me that Aho-Corasick can be adapted to admit insertions using this same stack. So, it's pretty cool.

Deque-like

So, again, the issue is that this power-of-two stack only works in an offline manner. I.e., one may first push, then pop. Whereas, in a deque, if we are to split it into two stacks and work from there, the stack needs to work in an online manner.

My idea was to just duplicate the buckets. I.e., instead of the buckets being of sizes $$$1, 2, 4, ...$$$, instead we'd have $$$1, 1, 2, 2, 4, 4,...$$$.

If in the standard power-of-two stack things are pretty clear (i.e., the occupied buckets are just the 1-bits in the writing in base-2 of the size of the stack), here things are more dynamic. Particularly, pushing works as follows:

• If both the first and second $$$1$$$-bucket is off, push the element in the second one
• If only the first $$$1$$$-bucket is off, push the element there
• Otherwise:
  • Form a $$$2$$$-group by concatenating the contents of the two $$$1$$$-buckets together
  • Now just push the element in the second $$$1$$$-bucket
  • Push the $$$2$$$-group using a similar strategy, only applied to the further buckets. Note that this may imply pushing a $$$4$$$-group, $$$8$$$-group, etc.

The second-then-first bucket thing is just that the list of elements is still coherent when read from right to left.

Popping is much easier by contrast.

• First, identify the smallest full bucket. Again, second-then-first applies in case of equality.
• Then, just remove the last element, and redistribute the elements in the second-buckets of the lesser sizes.

I don't actually have any formal proof for the amortization of all of this. I don't currently care enough to prove it. I think the first time I tried I came up with asserting that it amortizes to $$$O(1)$$$. Which is wrong because the $$$O(log)$$$ lower-bound is sort of proven for the queue-like case. The intuition is that, once you redistribute things through pop, the amount of work required to push the elements of a second-bucket to the next level is proportional to it. It is similar for a first-bucket. Mostly because, when each of these are instantiated, the sum of sizes of empty buckets below them sort of has to be equal to them (i.e. either all second or first buckets of lower order are empty upon instantiation).

Of course, the full deque-like idea is just interweaving the buckets of the left and right stacks in order of their sizes when pushed to the commutative DS (e.g. DSU).

Here is a fun AI-slop animation of some processes happening in a single stack. Note the order of the stacks is the same as the previous illustration.

I apologise for the abysmal FPS rate.

Aand here is the code of this. Note I wrote this at like 1am, and I hate when people play codingame and codegolf.

template<typename E, typename DS_T, typename DS_QT, typename DS_QA>
struct DequeLike {
   vector<pair<vector<E>, vector<E>>> L_;
   vector<pair<vector<E>, vector<E>>> R_;
   
   DS_T DS;
   
   template<class CB> void init(CB&& cb) { cb(DS); }
   
   void forcepush(const vector<E>& v) {
      for(auto& x : v) DS.push(x);
   }
   void repush(int where, int idx) {
      if(idx < 0) return;
      if(where == 0) { // L
         if(idx < sz(L_))
            forcepush(L_[idx].first),
            forcepush(L_[idx].second);
         repush(1, idx - 1);
         return;
      }
      if(idx < sz(R_))
         forcepush(R_[idx].first),
         forcepush(R_[idx].second);
      if(idx < sz(L_))
         forcepush(L_[idx].first),
         forcepush(L_[idx].second);
      repush(1, idx - 1);
   }
   
   
   void convert(vector<E>& a, vector<pair<vector<E>, vector<E>>>& A) {
      int p = 1;
      while(p <= sz(a)) {
         A.emplace_back(make_pair(vector<E>(), vector<E>()));
         if(p & sz(a)) {
            copy(sz(a) - p + all(a), back_inserter(A.back().first));
            a.resize(sz(a) - p);
         }
         p <<= 1;
      }
      return;
   }
   
   void rebalance(vector<E> v) {
      clear();
      vector<E> l, r;
      copy(all(v) - sz(v) / 2, back_inserter(l));
      copy(sz(v) - sz(v) / 2 + all(v), back_inserter(r));
      reverse(all(l));
      
      convert(l, L_);
      convert(r, R_);
      if(sz(L_) > sz(R_)) repush(0, sz(L_) - 1);
      else repush(1, sz(R_) - 1);
      return;
   }
   
   void push(E x, vector<pair<vector<E>, vector<E>>> &L, vector<pair<vector<E>, vector<E>>> &R) {
      int sizePop = 0;
      int overflow = 0;
      vector<E> flow;
      flow.emplace_back(x);
      while(overflow < sz(L) && !L[overflow].second.empty()) {
         sizePop += sz(L[overflow].first) + sz(L[overflow].second); 
         copy(all(L[overflow].second), back_inserter(L[overflow].first));
         swap(L[overflow].first, flow);
         L[overflow].second.clear();
         overflow++;
      }
      if(overflow == sz(L)) L.emplace_back(make_pair(flow, vector<E>()));
      else {
         if(L[overflow].first.empty()) L[overflow].first = move(flow);
         else L[overflow].second = move(flow), sizePop += sz(L[overflow].first); // can be optimized;
      }
      for(int i = 0; i < sz(R) && i < overflow + (&L == &R_); i++)
         sizePop += sz(R[i].first) + sz(R[i].second);
      
      DS.pop(sizePop);
      repush((&L == &R_), overflow);
      return;
   }
   
   void pop(vector<pair<vector<E>, vector<E>>> &L, vector<pair<vector<E>, vector<E>>> &R) {
      int sizePop = 0;
      int overflow = 0;
      vector<E> kill;
      
      while(overflow < sz(L) && L[overflow].first.empty()) overflow++;
      if(overflow == sz(L)) {
         for(int i = sz(R) - 1; i >= 0; i--) copy(all(R[i].first), back_inserter(kill)), copy(all(R[i].second), back_inserter(kill));
         clear();
         if(sz(kill) == 1) return;
         if(&L == &R_) reverse(all(kill));
         rebalance(kill);
         pop(L, R);
         return;
      }
      sizePop += sz(L[overflow].first) + sz(L[overflow].second);
      if(L[overflow].second.empty()) kill = move(L[overflow].first);
      else kill = move(L[overflow].second);
      
      
      for(int l = 0, i = overflow - 1; i >= 0; l += (1 << i), i--)
         copy(l + all(kill) - (1 << i), back_inserter(L[i].first));
      
      for(int i = 0; i < sz(R) && i < overflow + (&L == &R_); i++)
         sizePop += sz(R[i].first) + sz(R[i].second);
      
      DS.pop(sizePop);
      repush((&L == &R_), overflow);
   }
   void pushleft(E x) { push(x, L_, R_); }
   void pushright(E x) { push(x, R_, L_); }
   void popleft() { pop(L_, R_); }
   void popright() { pop(R_, L_); }
   void clear() {
      DS.clear();
      L_.clear();
      R_.clear();
   }
   
   vector<E> extract() {
      vector<E> l, r;
      for(auto v : L_ | views::reverse) {
         copy(all(v.first), back_inserter(l));
         copy(all(v.second), back_inserter(l));
      }
      for(auto v : R_ | views::reverse) {
         copy(all(v.first), back_inserter(r));
         copy(all(v.second), back_inserter(r));
      }
      reverse(all(l));
      copy(all(r), back_inserter(l));
      return l;
   }
   
   DS_QA query(DS_QT x) {
      return DS.query(x);
   }
};

Usage of this horrible template

I hope you liked this idea. Goodbye.