結果

問題 No.259 セグメントフィッシング＋
ユーザー vain0vain0
提出日時 2015-08-01 02:11:24
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 3,542 bytes
コンパイル時間 762 ms
コンパイル使用メモリ 78,104 KB
実行使用メモリ 11,440 KB
最終ジャッジ日時 2024-07-18 00:20:46
合計ジャッジ時間 4,399 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <array>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
using ull = unsigned long long; using ll = long long;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define all(_X) begin(_X), end(_X)
#ifdef _LOCAL
# define ifdebug //
#else
# define ifdebug if (false)
#endif

//(T, +) semigroup
template<typename T>
struct AddSemigroup
{
	static T operate(T const& lhs, T const& rhs) { return lhs + rhs; }
	static T unit() { return 0; }
};

template<typename T>
T heightInt(T n)
{
	if ( n == 1 ) return 1;
	T h = 0;
	for ( ; n > static_cast<T>(1 << h); ++h );
	return h;
}

template<typename T, typename Semigroup>
class SegTree
{
	using uint = unsigned int;
	std::vector<T> v_;
	uint n_;
	uint h_;
public:
	void init(int n)
	{
		n_ = n;
		h_ = (heightInt<uint>(n));
		assert(n > 1);
		v_.resize((1 << h_) * 2 - 1, Semigroup::unit());
	}
private:
	int nodeIndexFromArrayIndex(int k) const
	{
		assert(0 <= k && static_cast<uint>(k) < n_);
		return ((1 << h_) - 1) + k;
	}
public:
	T const& at(int k) const { return v_[nodeIndexFromArrayIndex(k)]; }
	void update(int k, T const& x)
	{
		uint i = nodeIndexFromArrayIndex(k);
		if ( v_[i] == x ) return;
		v_[i] = x;

		while ( i != 0 ) {
			uint const parent = (i - 1) / 2;
			uint const child = parent * 2 + 1;
			v_[parent] = Semigroup::operate(v_[child], v_[child + 1]);
			i = parent;
		}
	}
public:
	T query(uint begin, uint end)
	{
		if ( begin >= end ) return Semigroup::unit();
		return queryRec(0, 0, 1 << h_, begin, end);
	}
private:
	T queryRec(uint i, uint nodeBeg, uint nodeEnd, uint queryBeg, uint queryEnd)
	{
		assert(nodeBeg <= queryBeg && queryBeg < queryEnd && queryEnd <= nodeEnd);
		uint const nodeMid = nodeBeg + (nodeEnd - nodeBeg + 1) / 2;
		if ( nodeBeg == queryBeg && nodeEnd == queryEnd ) {
			return v_[i];
		} else if ( queryEnd <= nodeMid ) {
			return queryRec(i * 2 + 1, nodeBeg, nodeMid, queryBeg, queryEnd);
		} else if ( nodeMid <= queryBeg ) {
			return queryRec(i * 2 + 2, nodeMid, nodeEnd, queryBeg, queryEnd);
		} else {
			assert(queryBeg < nodeMid && nodeMid < queryEnd);
			auto const& lhs = queryRec(i * 2 + 1, nodeBeg, nodeMid, queryBeg, nodeMid);
			auto const& rhs = queryRec(i * 2 + 2, nodeMid, nodeEnd, nodeMid, queryEnd);
			return Semigroup::operate(lhs, rhs);
		}
	}
};

using ST = SegTree<ll, AddSemigroup<ll>>;
ST st;
int t;
int n, q;

int il(int k) { return (t + 0 + k) % (2*n); }
int ir(int k) { return (t + n + (n - 1 - k)) % (2*n); }

ll query(int y, int z)
{
	if ( y < z ) {
		return st.query(y, z);
	} else {
		return st.query(y, 2*n) + st.query(0, z);
	}
}

int main()
{
	cin >> n >> q;
	st.init(n * 2);

	rep(i, q)
	{
		int u, y, z;
		char c;
		cin >> c >> u >> y >> z;
		t = u;
		switch ( c ) {
			case 'L':
				st.update(il(y), st.at(il(y)) + z);
				break;
			case 'R':
				st.update(ir(y), st.at(ir(y)) + z);
				break;
			case 'C': {
				int const yl = il(y),     zl = il(z);
				int const yr = ir(z - 1), zr = ir(y - 1);
				auto const sl = query(yl, zl);
				auto const sr = query(yr, zr);
				cout << (sl + sr) << endl;
				break;
			}
		}
		ifdebug {
			cout << "t = " << t << endl;
			cout << "[";
			rep(i, n)
			{
				cout << st.at(il(i)) << ", ";
			}
			cout << endl << " ";
			rep(i, n)
			{
				cout << st.at(ir(i)) << ", ";
			}
			cout << "]" << endl;
		}
	}

	return 0;
}
0