以下の帰着を行います。

• \(B_i\) に \(i \times D\) を加算したと捉える。

すると、条件は以下のように変換されます。

• \(0 \le B_{i+1}-B_i \le 2D\)

この変換を使うと、削除が無い場合は以下のように解くことができます。

• stack \(s\) を用意する。
• \(s\) の一番上が \(t\) であるときに \(x\) が追加されるとする。
• \(t < x-2D\) なら、後ろに \(t+2D\) を追加する。
• そうでなく \(t \le x\) なら、後ろに \(x\) を追加する。
• そうでない時、つまり \(t > x\) なら、 \(s\) 中の \(x\) を超える要素を全て摘出し、それらを \(x\) に置き換えた上で後ろに \(x\) を追加する。

各要素を (値, 個数) の形で持つことで、 \(N\) 要素の追加を全体で \(O(N)\) で処理できます。

削除がある場合はどうすればよいでしょうか？
この場合、 永続データ構造 を使います。
永続データ構造とは、そのデータ構造の状態を過去のある時点の状態にロールバックできるようなデータ構造であり、非常によく研究されています。

• あなたの庭に永続データ構造を飾りませんか？
• 永続データ構造【新歓ブログリレー2019 6日目】
• ゼロから作る永続データ構造

注意として、永続 stack ではこの問題を解くことができません。というのも、最悪 \(O(N)\) 回の摘出を \(O(Q)\) 回行うことになるからです。

stack の代わりに、例えば 永続配列 を用いましょう。
というのも、問題は最悪 \(O(N)\) 回の摘出が発生することなので、ランダムアクセス可能な配列上でまとめて摘出できるよう適切に処理して最悪計算量を \(o(N)\) にすれば十分です。

• つくってなぐろ (永続配列/永続Union-Find木/永続セグメント木の作り方と意義、具体例)
• Persistent Array
• 永続配列(Persistent-Array)

今回は、以下の情報を持つ永続配列・ stack の末尾にあたる場所はどこかの情報をペアにしておくことでこの問題に正解できます。

• その要素の値
• その要素の個数
• その要素までの累積の個数
• その要素までの累積和

要素の摘出をまとめて行うために二分探索が必要になり、更に永続配列自体の時間計算量に \(\log\) が付くため、全体で \(\log\) が \(2\) つの解法になります。

本解法の時間計算量は \(O(N \log N + Q \log^2 N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

// https://sotanishy.github.io/cp-library-cpp/data-structure/persistent_array.hpp.html
template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};

using ll=long long;

typedef struct{
  ll val;
  ll cnt;
  ll totc;
  ll sum;
}dat;

using pa=PersistentArray<dat,8>;

ll sub(ll n){
  return (n*(n-1))/2;
}

int main(){
  ll Q,D;
  cin >> Q >> D;
  vector<pair<pa,int>> state;
  {
    vector<dat> ini(Q);
    pa ipa(ini);
    state.push_back({ipa,-1});
  }

  ll cnt=0;
  while(Q--){
    ll typ;
    cin >> typ;
    if(typ==1){
      ll X;
      cin >> X;
      X+=cnt*D;
      cnt++;

      if(state.back().second==-1){
        state.push_back({state.back().first.set(0,dat{X,1,1,X}),0});
        continue;
      }

      auto ca=state.back().first;
      int pos=state.back().second;
      dat cdat=ca.get(pos);
      ll tv=cdat.val;
      if(tv+2*D < X){
        X=tv+2*D;
      }
      if(tv <= X){
        state.push_back({ca.set(pos+1,dat{X,1,cnt,cdat.sum+X}),pos+1});
        continue;
      }
      int lo=0,hi=pos;
      while(lo<=hi){
        int te=(lo+hi)/2;
        if(ca.get(te).val>X){hi=te-1;}
        else{lo=te+1;}
      }

      if(hi==-1){
        state.push_back({ca.set(0,dat{X,cnt,cnt,X*cnt}),0});
      }
      else{
        cdat=ca.get(hi);
        ll lack=cnt-cdat.totc;
        state.push_back({ca.set(hi+1,dat{X,lack,cnt,cdat.sum+lack*X}),hi+1});
      }
    }
    else if(typ==2){
      state.pop_back();
      cnt--;
    }
    else{
      if(state.back().second==-1){
        cout << "0\n";
      }
      else{
        cout << state.back().first.get(state.back().second).sum-D*sub(cnt) << "\n";
      }
    }
  }
  return 0;
}