これも愚直にやったら間に合わないが、区間更新・区間和の取得ができればよいので、
遅延評価セグメント木を使えば1回あたり $O(\log{N})$ で効率的に行える。
順列 $P$ を「$X$ 以上なら1、未満なら0」「$X$ より大きいなら1、以下なら0」とした2つの数列に変換すると、
2つはちょうど、$X$ の位置だけが異なった状態となり、その性質はソートしても変わらない。
from operator import add
from typing import TypeVar, Generic, Callable, List
T = TypeVar('T')
U = TypeVar('U')
class LazySegmentTreeInjectable(Generic[T, U]):
def __init__(self,
n: int,
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
self.n = n
self.depth = n.bit_length()
self.offset = 1 << self.depth
self.identity_data = identity_data
self.identity_lazy = identity_lazy
self.operation = operation
self.mapping = mapping
self.composition = composition
self.data = [identity_data() for _ in range(self.offset << 1)]
self.lazy = [identity_lazy() for _ in range(self.offset)]
@classmethod
def from_array(cls,
arr: List[T],
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
ins.data[ins.offset:ins.offset + ins.n] = arr
for i in range(ins.offset - 1, 0, -1):
ins.update(i)
return ins
def push(self, i: int) -> None:
if i < self.offset:
data = self.data
lazy = self.lazy
lz = lazy[i]
lch = i << 1
rch = lch + 1
data[lch] = self.mapping(data[lch], lz)
data[rch] = self.mapping(data[rch], lz)
if lch < self.offset:
lazy[lch] = self.composition(lazy[lch], lz)
lazy[rch] = self.composition(lazy[rch], lz)
lazy[i] = self.identity_lazy()
def update(self, i: int) -> None:
lch = i << 1
rch = lch + 1
self.data[i] = self.operation(self.data[lch], self.data[rch])
def all_apply(self, i: int, d: U) -> None:
self.data[i] = self.mapping(self.data[i], d)
if i < self.offset:
self.lazy[i] = self.composition(self.lazy[i], d)
def propagate(self, l: int, r: int) -> None:
for i in range(self.depth, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
def range_update(self, l: int, r: int, d: U) -> None:
l += self.offset
r += self.offset
self.propagate(l, r)
l2 = l
r2 = r
while l < r:
if (l & 1) == 1:
self.all_apply(l, d)
l += 1
if (r & 1) == 1:
r -= 1
self.all_apply(r, d)
l >>= 1
r >>= 1
l = l2
r = r2
for i in range(1, self.depth + 1):
if ((l >> i) << i) != l:
self.update(l >> i)
if ((r >> i) << i) != r:
self.update((r - 1) >> i)
def range_query(self, l: int, r: int) -> T:
l += self.offset
r += self.offset
self.propagate(l, r)
sml = self.identity_data()
smr = self.identity_data()
while l < r:
if (l & 1) == 1:
sml = self.operation(sml, self.data[l])
l += 1
if (r & 1) == 1:
r -= 1
smr = self.operation(self.data[r], smr)
l >>= 1
r >>= 1
return self.operation(sml, smr)
def point_set(self, p: int, d: T) -> None:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
self.data[p] = d
for i in range(1, self.depth + 1):
self.update(p >> i)
def point_get(self, p: int) -> T:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
return self.data[p]
def debug_print(self) -> None:
i = 1
while i <= self.offset:
print(*map('{: 4d}'.format, self.data[i:i * 2]))
i <<= 1
i = 1
while i <= self.offset:
print(*map('{: 4d}'.format, self.lazy[i:i * 2]))
i <<= 1
n, q, x = map(int, input().split())
ppp = list(map(int, input().split()))
ge_x = [(int(p >= x), 1) for p in ppp]
gt_x = [(int(p > x), 1) for p in ppp]
identity_data = lambda: (0, 1)
identity_lazy = lambda: -1
operation = lambda a, b: (a[0] + b[0], a[1] + b[1])
mapping = lambda a, b: a if b == -1 else (a[1] * b, a[1])
composition = lambda a, b: a if b == -1 else b
lst_ge = LazySegmentTreeInjectable.from_array(ge_x, identity_data, identity_lazy, operation, mapping, composition)
lst_gt = LazySegmentTreeInjectable.from_array(gt_x, identity_data, identity_lazy, operation, mapping, composition)
for _ in range(q):
c, l, r = map(int, input().split())
l -= 1
r -= 1
if c == 1:
s, _ = lst_ge.range_query(l, r + 1)
lst_ge.range_update(l, r - s + 1, 0)
lst_ge.range_update(r - s + 1, r + 1, 1)
s, _ = lst_gt.range_query(l, r + 1)
lst_gt.range_update(l, r - s + 1, 0)
lst_gt.range_update(r - s + 1, r + 1, 1)
else:
s, _ = lst_ge.range_query(l, r + 1)
lst_ge.range_update(l, l + s, 1)
lst_ge.range_update(l + s, r + 1, 0)
s, _ = lst_gt.range_query(l, r + 1)
lst_gt.range_update(l, l + s, 1)
lst_gt.range_update(l + s, r + 1, 0)
for i in range(n):
if lst_ge.point_get(i) != lst_gt.point_get(i):
print(i + 1)
break
else:
raise NotImplementedError