old/RangeAddQuery.test.cpp

• View this file on GitHub
• Last update: 2021-01-02 15:13:44+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_E

Depends on

• old/RangeAddQuery.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_E"
#include "./../old/RangeAddQuery.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	RangeAddQuery<int> seg(n);
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int l, r, x;
			cin >> l >> r >> x;
			seg.add(l - 1, r, x);
		} else {
			int i;
			cin >> i;
			cout << seg[i - 1] << '\n';
		}
	}
}

#line 1 "old/RangeAddQuery.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_E"
#line 2 "old/RangeAddQuery.cpp"
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

template <class T> class RangeAddQuery {
	int n;
	vector<T> a;
	static int ceil2(int n) {
		int m = 1;
		while (m < n) m *= 2;
		return m;
	}

public:
	RangeAddQuery(int _n) : n(ceil2(_n)), a(n * 2) {}
	RangeAddQuery(const vector<T>& v) : n(ceil2(v.size())), a(n * 2) {
		for (size_t i = 0; i < v.size(); ++i) {
			a[i + n] = v[i];
		}
	}
	void add(int l, int r, const T& x) {
		l = clamp(l, 0, n);
		r = clamp(r, 0, n);
		if (l >= r) return;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) a[l++] += x;
			if (r & 1) a[--r] += x;
		}
	}
	void add(int i, const T& x) {
		add(i, i + 1, x);
	}
	T operator[](int i) const {
		assert(0 <= i && i < n);
		T res = a[i += n];
		while (i >>= 1) {
			res += a[i];
		}
		return res;
	}
	vector<T> to_a() const {
		vector<T> res(n);
		for (int i = 0; i < n; ++i) {
			res[i] = operator[](i);
		}
		return res;
	}
};
#line 3 "old/RangeAddQuery.test.cpp"
#include <iostream>
#line 5 "old/RangeAddQuery.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	RangeAddQuery<int> seg(n);
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int l, r, x;
			cin >> l >> r >> x;
			seg.add(l - 1, r, x);
		} else {
			int i;
			cin >> i;
			cout << seg[i - 1] << '\n';
		}
	}
}

Back to top page