class SegmentTree(object): '''値が動的に変化する数値列の部分和を O(log(N)) で求める。 完全二分木を用いている。 計算量: リストからの初期化 O(N) 部分和の取得 O(log(N)) 値の更新 O(log(N)) ''' def __init__(self, seq): size = len(seq[:]) self.capacity = 1 << (len(bin(size - 1)) - 2) self.tree = [0] * self.capacity * 2 self.tree[self.capacity:self.capacity + size] = seq self._fill_tree() self.tree[0] = size def _fill_tree(self): for i in range(self.capacity - 1, 0, -1): self.tree[i] = self.tree[i << 1] + self.tree[(i << 1) + 1] def _update(self, validkey): pos = (self.capacity + validkey) >> 1 while pos: self.tree[pos] = self.tree[pos << 1] + self.tree[(pos << 1) + 1] pos >>= 1 def _validate_key(self, key): size = self.tree[0] if key >= size: raise KeyError('key must be smaller than len {}'.format(size)) if key < 0: if key < - size: raise KeyError('key must be larger than - len {}'.format(size)) else: return key + size return key def _validate_range(self, begin, end): pass def range_sum(self, begin, end): ''' returns sum(self.tree[capacity+begin:capacity+end]) in O(log(size)) ''' self._validate_range(begin, end) tree = self.tree res = 0 begin += self.capacity end += self.capacity while begin < end: if begin & 1: res += tree[begin] begin += 1 if end & 1: res += tree[end - 1] begin >>= 1 end >>= 1 return res def __len__(self): return self.tree[0] def __getitem__(self, key): validkey = self._validate_key(key) return self.tree[self.capacity + validkey] def __setitem__(self, key, value): validkey = self._validate_key(key) self.tree[self.capacity + validkey] = value self._update(validkey) def __repr__(self): seq = self.tree[self.capacity:self.capacity + len(self)] return 'SegmentTree({})'.format(seq) class MovingSegmentTree(object): def __init__(self, N): self.N = N self.st = SegmentTree([0] * (N*2)) def add_right(self, pos, val, t): original_pos = self.get_original_pos(pos, t) self.st[original_pos] += val def add_left(self, pos, val, t): original_pos = self.get_original_pos_left(pos, t) self.st[original_pos] += val def range_sum(self, begin, end, t): begin_right = self.get_original_pos(begin, t) end_right = self.get_original_pos(end, t) begin_left = self.get_original_pos_left(end-1, t) end_left = self.get_original_pos_left(begin-1, t) return self._sum(begin_right, end_right) + self._sum(begin_left, end_left) def _sum(self, begin, end): if begin < end: return self.st.range_sum(begin, end) else: return self.st.range_sum(0, end) + self.st.range_sum(begin, self.N * 2) def get_original_pos(self, pos, t): ''' x + t = pos (mod 2*N) x = (pos - t) % 2*N ''' return (pos - t) % (2 * self.N) def get_original_pos_left(self, pos, t): return self.get_original_pos(2 * self.N - 1 - pos, t) if __name__ == '__main__': N, Q = map(int, input().split()) mst = MovingSegmentTree(N) for t in range(1, Q + 1): x, y, z = input().split() y = int(y) z = int(z) if x == 'R': mst.add_right(y, z, t) elif x == 'L': mst.add_left(y, z, t) elif x == 'C': print(mst.range_sum(y, z, t)) else: raise RuntimeError('Unknown command!', x)