src/dp/imos.hpp

View this file on GitHub
Last update: 2022-12-29 23:27:10+09:00
Include: #include "src/dp/imos.hpp"

Verified with

test/aoj/dsl_5_a.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

template <typename T> struct ImosInterval {
  // [l, r), l and r is 0-indexed.
  int l, r;
  T v;
};

template <typename T> struct Imos {
private:
  int n;
  vector<T> s;

public:
  Imos(int n, const vector<ImosInterval<T>> &intervals) : n(n) {
    s.resize(n + 1, 0);
    for (auto interval : intervals) {
      s[interval.l] += interval.v;
      s[interval.r] -= interval.v;
    }
    for (int i = 0; i < n; ++i) {
      s[i + 1] += s[i];
    }
  }

  // i is 0-indexed.
  T get(int i) { return s[i]; }
};

#line 2 "src/dp/imos.hpp"

#include <bits/stdc++.h>
using namespace std;

template <typename T> struct ImosInterval {
  // [l, r), l and r is 0-indexed.
  int l, r;
  T v;
};

template <typename T> struct Imos {
private:
  int n;
  vector<T> s;

public:
  Imos(int n, const vector<ImosInterval<T>> &intervals) : n(n) {
    s.resize(n + 1, 0);
    for (auto interval : intervals) {
      s[interval.l] += interval.v;
      s[interval.r] -= interval.v;
    }
    for (int i = 0; i < n; ++i) {
      s[i + 1] += s[i];
    }
  }

  // i is 0-indexed.
  T get(int i) { return s[i]; }
};