結果
| 問題 |
No.2292 Interval Union Find
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-07-04 22:01:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,080 bytes |
| コンパイル時間 | 422 ms |
| コンパイル使用メモリ | 82,512 KB |
| 実行使用メモリ | 266,960 KB |
| 最終ジャッジ日時 | 2025-07-04 22:04:21 |
| 合計ジャッジ時間 | 142,142 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 10 WA * 32 TLE * 2 |
ソースコード
## https://yukicoder.me/problems/no/2292
class LazySegmentTree:
"""
非再帰版遅延セグメント木。
更新は「加法」、取得は「最大値」のもの限定。
取得のところの都合で取得演算子は可換になっている必要がある。
"""
def __init__(self, init_array):
n = 1
while n < len(init_array):
n *= 2
self.size = n
self.array = [0] * (2 * self.size)
self.weights = [0] * (2 * self.size)
self.lazy_array = [0 for _ in range(2 * self.size)]
for i, a in enumerate(init_array):
self.array[self.size + i] = a
self.weights[self.size + i] = 1
end_index = self.size
start_index = end_index // 2
while start_index >= 1:
for i in range(start_index, end_index):
self.array[i] = self.array[2 * i] + self.array[2 * i + 1]
self.weights[i] = self.weights[2 * i] + self.weights[2 * i + 1]
end_index = start_index
start_index = end_index // 2
def _propagates(self, *ids):
for i in reversed(ids):
self._propagate(i)
def _propagate(self, i):
v = self.lazy_array[i]
if v == 0:
return
if i < self.size:
self._op(2 * i, v)
self._op(2 * i + 1, v)
self.lazy_array[i] = 0
def _op(self, index, v):
self.lazy_array[index] = v
if v == 1:
self.array[index] = 0
elif v == 2:
self.array[index] = self.weights[index]
def _get_target_index(self, l, r):
L = l + self.size; R = r + self.size
lm = (L // (L & -L)) >> 1
rm = (R // (R & -R)) >> 1
while 0 < L and L < R:
if R <= rm:
yield R
if L <= lm:
yield L
L >>= 1; R >>= 1
while L > 0:
yield L
L >>= 1
def add(self, l, r, x):
# 2. 区間[l, r)のdata, lazyの値を更新
L = self.size + l; R = self.size + r
*ids, = self._get_target_index(l, r)
self._propagates(*ids)
while L < R:
if R & 1:
R -= 1
self._op(R, x)
if L & 1:
self._op(L, x)
L += 1
L >>= 1; R >>= 1
# 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
for i in ids:
if i < self.size:
self.array[i] = self.array[2 * i] + self.array[2 * i + 1]
def get_sum(self, l, r):
# 1. トップダウンにlazyの値を伝搬
self._propagates(*self._get_target_index(l, r))
L = self.size + l; R = self.size + r
# 2. 区間[l, r)の最大値を求める
s = 0
while L < R:
if R & 1:
R -= 1
s += self.array[R]
if L & 1:
s += self.array[L]
L += 1
L >>= 1; R >>= 1
return s
def main():
N, Q = map(int, input().split())
queries = []
for _ in range(Q):
values = tuple(map(int, input().split()))
queries.append(values)
# 座標圧縮
v_set = set()
for values in queries:
if values[0] <= 2:
_, u, v = values
u -= 1
v -= 1
v_set.add(u)
v_set.add(u + 1)
v_set.add(v)
v_set.add(v + 1)
elif values[0] == 3:
_, u, v = values
u -= 1
v -= 1
v_set.add(u)
v_set.add(v)
else:
_, v = values
v -= 1
v_set.add(v)
v_list = list(v_set)
v_list.sort()
v_map = {}
for i, v in enumerate(v_list):
v_map[v] = i
v_max = len(v_list)
array = [1] * v_max
lazy_seg_tree = LazySegmentTree(array)
for values in queries:
if values[0] == 1:
_, l, r = values
l -= 1
r -= 1
l_ = v_map[l]
r_ = v_map[r]
if l_ < r_:
lazy_seg_tree.add(l_ + 1, r_ + 1, 1)
elif values[0] == 2:
_, l, r = values
l -= 1
r -= 1
l_ = v_map[l]
r_ = v_map[r]
lazy_seg_tree.add(l_ + 1, r_ + 1, 2)
elif values[0] == 3:
_, u, v = values
u -= 1
v -= 1
u_ = v_map[u]
v_ = v_map[v]
u_index = lazy_seg_tree.get_sum(0, u_ + 1)
v_index = lazy_seg_tree.get_sum(0, v_ + 1)
if u_index == v_index:
print(1)
else:
print(0)
elif values[0] == 4:
_, u = values
u -= 1
u_ = v_map[u]
u_low_index = lazy_seg_tree.get_sum(0, u_ + 1)
low = 0
high = u_
while high - low > 1:
mid = (high + low) // 2
if lazy_seg_tree.get_sum(0, mid + 1) >= u_low_index:
high = mid
else:
low = mid
if lazy_seg_tree.get_sum(0, low + 1) >= u_low_index:
v0 = low
else:
v0 = high
if u_low_index == lazy_seg_tree.get_sum(0, v_max):
print(N - v_list[v0])
else:
u_high_index = 1 + u_low_index
low = u_
high = v_max - 1
while high - low > 1:
mid = (high + low) // 2
if lazy_seg_tree.get_sum(0, mid + 1) >= u_high_index:
high = mid
else:
low = mid
if lazy_seg_tree.get_sum(0, low + 1) >= u_high_index:
v1 = low
else:
v1 = high
print(v_list[v1] - v_list[v0])
if __name__ == "__main__":
main()