この問題には様々な解法が考えられますが、今回は Segment Tree を利用してこの問題を解くことを考えます。

まず、最初に全てのクエリを受け取ってオフラインでこの問題を解くことにします。そのうえで、全ての + クエリについて追加される値 \(x\) を並べて昇順ソートした配列 \(S\) を作成します。

以下の問題文中のサンプルでは、 \(S=(2,3,3,5,5,7,998244352)\) となります。

10 2
+ 7
- 7
+ 2
+ 3
- 2
+ 3
+ 5
- 3
+ 998244352
+ 5

基本的な方針としては、 \(S\) の各要素について、

• 追加されるタイミングで「起動」
• 削除されるタイミングで「休眠」

のような操作を加えて解くことを考えます。

このとき、 \(S\) を昇順に並べていることから、 \(S\) の (連続でなくともよい) 部分列をどのように取っても、それは昇順で sorted になっていることに留意してください。

Segment Tree には以下の形で情報を持ちます。

• {その区間のみに着目した \(f(X)\) の値, 区間の長さ}

( ACL の segtree における) 以下のように op, e を定義すれば、適切にこの情報を segtree に載せることができます。

二項演算 op:
\(\{a,b\}, \{c,d\}\) を結合することを考える。このとき、演算結果は \(\{a+c \times K^b,b+d\}\) である。

単位元 e: \(\{0, 0\}\)

追加と削除に対する処理は以下の通りです。

• 要素 \(x\) を追加する際は、 \(S\) 上の対応する位置を \(\{x,1\}\) とする。
• 要素 \(x\) を削除する際は、 \(S\) 上の対応する位置を \(\{0,0\}\) とする。

各処理の後、 segtree の全体に対してクエリを問い合わせると、現時点での \(f(T)\) の値を得ることができます。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

#define mod 998244353

using pl=pair<long long,long long>;

vector<long long> ce;
pl op(pl a, pl b) {
  return {(a.first+b.first*ce[a.second])%mod,a.second+b.second};
}
pl e() { return {0ll,0ll}; }

int main(int argc, char* argv[]){
  int q,k;
  cin >> q >> k;
  ce.resize(q+5);
  long long cv=1;
  for(int i=0;i<q+5;i++){
    ce[i]=cv;
    cv*=k;cv%=mod;
  }
  vector<string> typ(q);
  vector<long long> val(q);
  for(int i=0;i<q;i++){
    cin >> typ[i] >> val[i];
  }
  vector<long long> arr=val;
  sort(arr.begin(),arr.end());
  map<long long,long long> mp,cnt;
  for(int i=q;i>=0;i--){mp[arr[i]]=i;}

  segtree<pl, op, e> seg(q);
  for(int i=0;i<q;i++){
    if(typ[i]=="+"){
      seg.set(mp[val[i]]+cnt[val[i]],{val[i],1});
      cnt[val[i]]++;
    }
    else{
      cnt[val[i]]--;
      seg.set(mp[val[i]]+cnt[val[i]],{0,0});
    }
    cout << seg.all_prod().first << '\n';
  }
  return 0;
}