結果

問題 No.3792 XOR^2 Sum Query
コンテスト
ユーザー hiro1729
提出日時 2026-09-26 15:07:32
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 758 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 177 ms
コンパイル使用メモリ 64,472 KB
実行使用メモリ 711,308 KB
最終ジャッジ日時 2026-11-06 20:59:18
合計ジャッジ時間 8,507 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from atcoder.segtree import *

B = 31
C = (1 << B) - 1
mod = 998244353
inv4 = pow(4, -1, mod)

def f(a):
	return tuple(a if a & (1 << j) else C ^ a for j in range(B))

N, Q = map(int, input().split())
A = list(map(int, input().split()))
seg = SegTree(lambda a, b: tuple(i & j for i, j in zip(a, b)), tuple([C] * B), [f(a) for a in A])
for _ in range(Q):
	t, *q = map(int, input().split())
	if t == 1:
		p, x = q[0] - 1, q[1]
		seg.set(p, f(x))
	else:
		L, R = q[0] - 1, q[1]
		P = seg.prod(L, R)
		m = P[B - 1]
		s, z = 0, m
		for k in range(B):
			if (m & P[k]) == 0:
				s += P[k] * P[k] % mod
				s %= mod
				m |= P[k]
		t = ((C - z) * (C - z) - s) % mod
		print((s * 2 + t) * pow(2, R - L, mod) % mod * inv4 % mod)
0