#713019 (Ruby) No.1091 Range Xor Query

• 問題: No.1091 Range Xor Query
• ユーザー: 小野寺健
• 提出日時: 2021-11-05 13:27:50
• 言語: Ruby (3.3.0)
• 結果: AC
• 実行時間: 1,915 ms / 2,000 ms
• コード長: 700 bytes
• コンパイル時間: 206 ms
• コンパイル使用メモリ: 7,552 KB
• 実行使用メモリ: 35,972 KB
• 最終ジャッジ日時: 2024-04-23 20:58:35
• 合計ジャッジ時間: 32,352 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	74 ms; 12,416 KB
testcase_01	AC	74 ms; 12,288 KB
testcase_02	AC	74 ms; 12,288 KB
testcase_03	AC	255 ms; 24,192 KB
testcase_04	AC	1,095 ms; 22,616 KB
testcase_05	AC	1,219 ms; 31,560 KB
testcase_06	AC	104 ms; 14,592 KB
testcase_07	AC	1,245 ms; 24,424 KB
testcase_08	AC	1,757 ms; 29,684 KB
testcase_09	AC	885 ms; 20,324 KB
testcase_10	AC	1,237 ms; 28,288 KB
testcase_11	AC	1,596 ms; 29,680 KB
testcase_12	AC	903 ms; 31,440 KB
testcase_13	AC	1,851 ms; 29,400 KB
testcase_14	AC	1,359 ms; 28,140 KB
testcase_15	AC	1,420 ms; 30,924 KB
testcase_16	AC	1,379 ms; 25,924 KB
testcase_17	AC	1,915 ms; 32,840 KB
testcase_18	AC	342 ms; 15,488 KB
testcase_19	AC	361 ms; 24,192 KB
testcase_20	AC	1,804 ms; 29,796 KB
testcase_21	AC	862 ms; 19,156 KB
testcase_22	AC	1,693 ms; 31,852 KB
testcase_23	AC	1,206 ms; 35,972 KB
testcase_24	AC	1,222 ms; 34,904 KB
testcase_25	AC	1,236 ms; 35,836 KB
testcase_26	AC	1,228 ms; 35,028 KB
testcase_27	AC	1,238 ms; 35,028 KB

コンパイルメッセージ

Syntax OK

ソースコード

class SegmentTree
	def initialize(v)
		@n = 1
		while @n < v.length do
			@n *= 2
		end
		@node = Array.new(2*@n-1, 0)
		v.each_with_index{|x, i|
			@node[i+@n-1] = x
		}
		(@n-2).downto(0) {|i|
			@node[i] = @node[2*i+1] ^ @node[2*i+2]
		}
	end
	def query(a, b, k=0, l=0, r=@n)
		if r <= a or b <= l then
			return 0
		end
		if a <= l and r <= b then
			return @node[k]
		else
			vl = query(a, b, k * 2 + 1, l, (l + r) / 2)
			vr = query(a, b, k * 2 + 2, (l + r) / 2, r)
			return vl ^ vr
		end
	end
end

N, Q = gets.split(" ").map{|s| s.to_i}
a = gets.split(" ").map{|s| s.to_i}

q = []
Q.times {
	q << gets.split(" ").map(&:to_i)
}

st = SegmentTree.new(a)

q.each {|l, r|
	puts st.query(l-1, r)
}