結果

問題 No.3205 Range Pairwise Xor Query
コンテスト
ユーザー ルク
提出日時 2025-07-18 22:39:05
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 4,190 bytes
コンパイル時間 515 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 114,516 KB
最終ジャッジ日時 2025-07-18 22:39:19
合計ジャッジ時間 5,056 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree:
    n = 1
    size = 1
    log = 2
    d = [0]
    op = None
    e = 10**15

    def __init__(self, V, OP, E):
        self.n = len(V)
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        return self.d[p + self.size]

    def prod(self, l, r):
        assert 0 <= l and l <= r and r <= self.n
        sml = self.e
        smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                smr = self.op(self.d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def max_right(self, l, f):
        assert 0 <= l and l <= self.n
        assert f(self.e)
        if l == self.n:
            return self.n
        l += self.size
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not (f(self.op(sm, self.d[l]))):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                break
        return self.n

    def min_left(self, r, f):
        assert 0 <= r and r <= self.n
        assert f(self.e)
        if r == 0:
            return 0
        r += self.size
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not (f(self.op(self.d[r], sm))):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                break
        return 0

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __str__(self):
        return str([self.get(i) for i in range(self.n)])


def 入力():
    # 入力を受け取る関数.
    return input()


def 数字(文字列):
    # 数字に変換する関数.
    return int(文字列)


def 足し算だ(元の値, 追加する値):
    # 足し算をする関数.
    return 元の値 + 追加する値


def 出力(値):
    # 出力を行う関数.
    print(値)


ぜろ = 数字('0')
いち = 数字('1')
にじゅうろく = 数字('26')
エヌ, キュー = map(数字, 入力().split())
リスト = list(map(数字, 入力().split()))
ビットリスト = [[ぜろ]*エヌ for _ in range(にじゅうろく)]
for インデックス1 in range(エヌ):
    for インデックス2 in range(にじゅうろく):
        if リスト[インデックス1] & (いち << インデックス2):
            ビットリスト[インデックス2][インデックス1] = いち
釣り大好き = [segtree(ビットリスト[インデックス], 足し算だ, ぜろ) for インデックス in range(にじゅうろく)]
for _ in range(キュー):
    左, 右 = map(数字, 入力().split())
    左 -= いち
    答え = ぜろ
    for インデックス in range(にじゅうろく):
        # いちの個数を数える.
        いちの個数 = 釣り大好き[インデックス].prod(左, 右)
        ぜろの個数 = 右 - 左 - いちの個数
        答え += (いち << インデックス) * いちの個数 * ぜろの個数
    出力(答え)
0