AtCoder が提供しているABC（AtCoder Beginner Contest）343 のF問題をC++で解いてみました。ABC343は、2024年3月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Second Largest Query（Difficulty : 1370）
問題はリンク先をご覧ください。
ABC343 F問題 Second Largest Query
一番大きい値とその個数、二番目に大きい値とその個数をセグメント木で管理します。AtCoder Problems による Difficulty は 1370 でした。
解答案
セグメント木を使います。
C++ プログラム例（ABC343F）
型は、一番大きい値とその個数、二番目に大きい値をメンバに持つ構造体とします（7ー12行目）。演算する関数 op、単位元を返す関数 e を以下のように定義します。
- 関数 op：二つの構造体から、一番大きい値とその個数、二番目に大きい値を計算します。map コンテナを使って値を求めました（14ー32行目）。
- 関数 e：{-1, 0, -2, 0} を返します（34ー37行目）。
以下が、C＋＋プログラムとなります。セグメント木の操作に関するコードの背景色を変更しています。
#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
typedef struct {
int fv; // first value
int fc; // first count
int sv; // second value
int sc; // second count
} S;
S op(S a, S b)
{
S result;
map<int, int> m;
m[a.fv] += a.fc;
m[a.sv] += a.sc;
m[b.fv] += b.fc;
m[b.sv] += b.sc;
auto it = m.rbegin();
result.fv = (*it).first;
result.fc = (*it).second;
++it;
result.sv = (*it).first;
result.sc = (*it).second;
return result;
}
S e()
{
return (S){-1, 0, -2, 0};
}
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
segtree<S, op, e> seg(n);
for (int i = 0; i < n; ++i) {
seg.set(i, (S){a[i], 1, -1, 0});
}
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
int p, x;
cin >> p >> x;
--p;
seg.set(p, (S){x, 1, -1, 0});
} else if (type == 2) {
int L, R;
cin >> L >> R;
--L;
S result = seg.prod(L, R);
cout << result.sc << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python のセグメント木について
Python は、セグメント木を標準ライブラリとしては用意していません。このブログの Python プログラムは、なるべく言語標準のライブラリで実装したいと考えています。このような事情で、この記事では、Python に移植したプログラムの紹介を省略します。
最後に
型を工夫してセグメント木を使う問題でした。セグメント木を使う問題に慣れていければと思います。
引き続き ABC の問題を紹介していきます。
