結果

問題 No.3581 分数対称差更新区間計数取得
コンテスト
ユーザー kidodesu
提出日時 2026-07-03 22:14:46
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,531 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 208 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 120,320 KB
最終ジャッジ日時 2026-07-03 22:16:48
合計ジャッジ時間 43,823 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.n0 = 2**(n-1).bit_length()
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def init(self, A):
        self.data[1:] = A
        for i in range(1, self.n):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    def lower_bound(self, x):
        w = i = 0
        k = self.n0
        while k:
            if i+k <= self.n and w + self.data[i+k] <= x:
                w += self.data[i+k]
                i += k
            k >>= 1
        # assert self.get(0, i) <= x < self.get(0, i+1)
        return i+1

def main():
    q = int(input())
    N = 10**6+1
    st = BIT(N)
    X = [0] * N
    for _ in range(q):
        i, l, r = list(map(int, input().split()))
        C = set()
        for j in range(1, i+1):
            if j * j > i: break
            C.add(j)
            C.add(i//j)
        for c in C:
            if X[c]:
                st.add(c, -1)
            else:
                st.add(c, 1)
            X[c] ^= 1
        print(st.get(l-1, r))

main()
0