[ABC343] F - Second Largest Query

[Q] Second Largest Query

全然わからなかった…。これ1600人解けるのすごいね。
俺はACL使っていないのでテンプレートを調整してます。

考察
・セグ木を魔改造すればよさそう
・どんな値を持てばいい？
-> {max, max_cnt, 2nd_max, 2nd_cnt}の4要素で管理すればいい
・2つを統合するときには、上位2つの値と個数を調べる。

実装

///////////// セグ木
class RangeMax
{
public:
  ll size_ = 1;
  vector<tll> dat; // max, max_cnt, 2nd_max, 2nd_max_cnt
  void init(ll sz)
  {
    while (size_ <= sz)
      size_ *= 2;
    dat.resize(size_ * 2, {-1, -1, -1, -1}); // -1は該当なし
  }

  /*
    {2, 1, -1, -1}, {3, 1, 2, 1}
    => 3の1個が最大値。2の2個が次点。
    ret = {3, 1, 2, 2} 
  */
  tll compare(tll a, tll b)
  {
    auto [v1, c1, v2, c2] = a;
    auto [v3, c3, v4, c4] = b;
    vector<pll> V = {{v1, c1}, {v2, c2}, {v3, c3}, {v4, c4}};
    sort(rall(V));
    for (auto it = V.begin() + 1; it != V.end();)
    {
      if (it->first == -1)
        it = V.erase(it);
      else if (it->first == prev(it)->first)
      {
        prev(it)->second += it->second;
        it = V.erase(it);
      }
      else
        ++it;
    }
    if (V.size() > 0)
    {
      v1 = V[0].first;
      c1 = V[0].second;
    }
    if (V.size() > 1)
    {
      v2 = V[1].first;
      c2 = V[1].second;
    }
    return {v1, c1, v2, c2};
  }

  void update(ll pos, tll x)
  {
    pos += size_;
    if (dat[pos] == x)
      return;
    dat[pos] = x;
    while (pos >= 2)
    {
      pos >>= 1;
      dat[pos] = compare(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }

  tll query_(ll l, ll r, ll k, ll a, ll b)
  {
    if (r <= a || b <= l)
      return {-1, -1, -1, -1};
    if (l <= a && b <= r)
      return dat[k];
    tll q1 = query_(l, r, k * 2, a, (a + b) >> 1);
    tll q2 = query_(l, r, k * 2 + 1, (a + b) >> 1, b);
    return compare(q1, q2);
  }

  tll query(ll l, ll r)
  {
    return query_(l, r, 1, 0, size_);
  }

  tll getval(ll id)
  {
    id += size_;
    return (dat[id]);
  }
};

int main()
{
  cincout();

  ll N, Q;
  cin >> N >> Q;

  RangeMax Z;
  Z.init(N);
  vector<ll> A(N);
  rep(i, N)
  {
    cin >> A[i];
    Z.update(i, {A[i], 1, -1, -1});
  }
  while (Q--)
  {
    ll q;
    cin >> q;
    if (q == 1)
    {
      ll p, x;
      cin >> p >> x;
      --p;
      auto [v1, c1, v2, c2] = Z.getval(p);

      // なんか長くなっちゃったけど、五月雨式に優先度処理してるだけ

      // 旧情報をキャンセルする
      if (v1 == A[p])
      {
        --c1;
        if (c1 == 0)
        {
          v1 = v2;
          c1 = c2;
          v2 = -1;
          c2 = -1;
        }
      }
      else if (v2 == A[p])
      {
        --c2;
        if (c2 == 0)
        {
          v2 = -1;
          c2 = -1;
        }
      }
      // 新しい値に置き換えることを考える
      A[p] = x;
      if (x > v1)
      {
        v2 = v1;
        c2 = c1;
        v1 = x;
        c1 = 1;
      }
      else if (x > v2)
      {
        v2 = x;
        c2 = 1;
      }
      Z.update(p, {v1, c1, v2, c2});
    }
    else
    {
      ll l, r;
      cin >> l >> r;
      --l;
      auto [v1, c1, v2, c2] = Z.query(l, r);
      if (v2 == -1)
      {
        cout << 0 << endl;
      }
      else
      {
        cout << c2 << endl;
      }
    }
  }
}

https://atcoder.jp/contests/abc343/submissions/50851692