数直線上での個数分布
(library/sequence/dispersion.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/sequence/dispersion.hpp"

数直線上での個数分布

できること

• 配列要素が数直線上の各点に何個ずつあるか、を返す

  A: 1 2 3 3 5 9
  

  を変換すると

  arr:   1 1 2   1       1          ...
  idx: 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
  

  を得る

計算量

$O(N)$

使い方

vector<int> disp = dispersion(A);

Verified with

• 数直線上での個数分布のテスト (tests/sequence.dispersion.test.cpp)

Code

#pragma once
vector<int> dispersion(const vector<int> &A) {
    vector<int> res(2e6);
    for (auto &&v : A) ++res[v];
    return res;
}

#line 2 "library/sequence/dispersion.hpp"
vector<int> dispersion(const vector<int> &A) {
    vector<int> res(2e6);
    for (auto &&v : A) ++res[v];
    return res;
}

Back to top page