競プロで使うc++の便利ライブラリ

こんにちは、ひぽたふです。

競プロで使う便利な標準ライブラリ達や、自作ライブラリをまとめておこうかなと思いました。
随時このページ更新して、見やすさ・探しやすさの改善や内容を増やしていく予定です。

ライブラリ

vector

vector<T>　初期化の仕方

vector<int> b(10, -1); // 中身を-1埋め
auto b = vector(2, vector(4, vector<int>(3, -1))); // 2x4x3次元

limits

numeric_limits<T>::max, min　最大値、最小値

numeric_limits<double>::max();

numeric

accumulate　総和

vector<long> a = {2, 1, 3};
accumulate(a.begin(), a.end(), 0l); // 最後初期値

partial_sum　累積和

vector<int> a = {2, 1, 3, 1};
vector<int> result(a.size() + 1);
partial_sum(a.begin(), a.end(), result.begin() + 1); // 0, 2, 3, 6, 7
// result[right] - result[left] ... sum [left, right)

bitset

bitset　ビット

bitset<5> a("10010"); // 10010
a[2] = 1; // 10110

algorithm

sort　ソート

vector<int> a = {2, 1, 3};
a.sort(a.begin(), a.end()); // 1, 2, 3
a.sort(a.begin(), a.end(), greater<int>()); // 3, 2, 1

lower_bound　二分探索

vector<int> a = {0, 0, 1, 1, 2, 7};
auto it = lower_bound(a.begin(), a.end(), 1); // {0, 0, @1, 1, 2, 7}
it = lower_bound(a.begin(), a.end(), 3); // {0, 0, 1, 1, 2, @7}
cout << *it << distance(a.begin(), it) << endl; // 7, 5

functional

greater, less

cmath

hypot　距離

hypot(x1 - x2, y1 - y2); // l2norm

iomanip

setprecision　出力時の小数精度

cout << setprecision(5) << M_PI << endl; // 3.1415

自作ライブラリ

データ構造

セグメントツリー　セグ木

template <class T>
class SegTree {
  public:
    int t = 1;
    vector<long long> table;

    T NEUTRAL;
    T(*OP)(T, T);

    SegTree(int n, T neutral, T(*op)(T, T)): NEUTRAL(neutral), OP(op) {
      while (t <= n) {
        t *= 2;
      }

      table = vector<long long>(t * 2 - 1, NEUTRAL);
    }

    long long top() {
      return find(0, t);
    }

    int up(int node) {
      return (node - 1) / 2;
    }

    int down(int node) {
      return (node * 2) + 1;
    }

    void update(int i, long long x) {
      i += t - 1;
      table[i] = x;

      while (i != 0) {
        i = up(i);
        int c = down(i);
        table[i] = OP(table[c], table[c + 1]);
      }
    }

    long long find(int l, int r, int node=0, int sl=0, int sr=-1) {
      if (sr < 0) sr = t;

      if (sr <= l || r <= sl) {
        return NEUTRAL;
      }

      if (l <= sl && sr <= r) {
        return table[node];
      }

      int sc = (sl + sr) / 2;
      int c = down(node);
      return OP(find(l, r, c, sl, sc), find(l, r, c + 1, sc, sr));
    }
};

// SegTree<long long> seg(10, 0, [](long long a, long long b){ return a + b; });
SegTree<long long> seg(10, numeric_limits<long long>::min(), [](long long a, long long b){ return max(a, b); });
seg.update(2, 3);
seg.update(1, 4);
cout << seg.find(1, 3) << endl;

アルゴリズム

総和

ll sum(ll right) {
  return right * (right + 1) / 2;
}

ll sum(ll left, ll right) {
  return sum(right) - sum(left - 1);
}

sum(3, 5) // 3 + 4 + 5