結果

問題 No.151 セグメントフィッシング
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-05 19:33:40
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 313 ms / 5,000 ms
コード長 3,947 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 11,080 KB
実行使用メモリ 11,256 KB
最終ジャッジ日時 2023-09-20 19:21:09
合計ジャッジ時間 5,503 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,444 KB
testcase_01 AC 18 ms
8,424 KB
testcase_02 AC 18 ms
8,464 KB
testcase_03 AC 17 ms
8,580 KB
testcase_04 AC 18 ms
8,560 KB
testcase_05 AC 19 ms
8,544 KB
testcase_06 AC 19 ms
8,560 KB
testcase_07 AC 19 ms
8,464 KB
testcase_08 AC 64 ms
8,968 KB
testcase_09 AC 65 ms
8,868 KB
testcase_10 AC 64 ms
8,868 KB
testcase_11 AC 64 ms
8,928 KB
testcase_12 AC 243 ms
10,928 KB
testcase_13 AC 240 ms
10,820 KB
testcase_14 AC 242 ms
10,844 KB
testcase_15 AC 245 ms
10,980 KB
testcase_16 AC 242 ms
10,816 KB
testcase_17 AC 165 ms
10,928 KB
testcase_18 AC 163 ms
10,072 KB
testcase_19 AC 306 ms
10,164 KB
testcase_20 AC 313 ms
10,068 KB
testcase_21 AC 194 ms
11,256 KB
testcase_22 AC 194 ms
11,228 KB
testcase_23 AC 147 ms
8,500 KB
権限があれば一括ダウンロードができます

ソースコード

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