ACLへ進む：型と演算を揃える
AtCoder Library は検証されたデータ構造の実装です。使い方だけでなく、与える演算の条件を理解して利用します。
言語：C++ / 計算量：例の処理による
前提：移植演習：累積和をC++で / Union-Findで連結を管理 / セグメント木は区間の集約器
考え方
- DSUなら leader / merge / same。
- segtree は型・結合演算・単位元を指定。
- 利用可否と対応言語は各コンテストの環境で確認します。
具体例
区間最小なら long long、op=min、eは十分大きい値。prod(l,r) は半開区間です。
実装
#include <iostream>
#include <algorithm>
#include <atcoder/segtree>
using namespace std;
long long op(long long a,long long b){return min(a,b);}
long long e(){return (1LL<<60);}
int main(){atcoder::segtree<long long,op,e>s(3);s.set(0,5);s.set(1,2);s.set(2,7);cout<<s.prod(0,2)<<"\n";}注意する条件
ローカルでACLが入っていないとコンパイルできません。通常の標準ライブラリではありません。
確認問題
配列[5,2,7]の prod(0,2) がminなら？
解答と理由
2
添字0と1を集約するので min(5,2)=2です。
実装課題
ACLのDSUを使い、4頂点で0-1、1-2を併合。0の成分サイズを出す。ACL利用環境で実行。
出力:
3参考実装
#include <iostream>
#include <atcoder/dsu>
using namespace std;
int main(){atcoder::dsu d(4);d.merge(0,1);d.merge(1,2);cout<<d.size(0)<<"\n";}