結果

問題 No.151 セグメントフィッシング
コンテスト
ユーザー rpy3cpp
提出日時 2015-06-05 19:33:40
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 308 ms / 5,000 ms
コード長 3,947 bytes
コンパイル時間 102 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 13,864 KB
最終ジャッジ日時 2024-07-06 14:18:07
合計ジャッジ時間 4,905 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0