結果
| 問題 | No.1270 Range Arrange Query |
| コンテスト | |
| ユーザー |
 rin204
|
| 提出日時 | 2023-12-29 16:50:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 3,738 ms / 7,000 ms |
| コード長 | 8,879 bytes |
| コンパイル時間 | 246 ms |
| コンパイル使用メモリ | 82,224 KB |
| 実行使用メモリ | 84,328 KB |
| 最終ジャッジ日時 | 2024-09-27 16:16:33 |
| 合計ジャッジ時間 | 19,880 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
class BIT:
def __init__(self, n):
self.n = n
self.data = [0] * (n + 1)
if n == 0:
self.n0 = 0
else:
self.n0 = 1 << (n.bit_length() - 1)
def sum_(self, i):
s = 0
while i > 0:
s += self.data[i]
i -= i & -i
return s
def sum(self, l, r=-1):
if r == -1:
return self.sum_(l)
else:
return self.sum_(r) - self.sum_(l)
def get(self, i):
return self.sum(i, i + 1)
def add(self, i, x):
i += 1
while i <= self.n:
self.data[i] += x
i += i & -i
def lower_bound(self, x):
if x <= 0:
return 0
i = 0
k = self.n0
while k > 0:
if i + k <= self.n and self.data[i + k] < x:
x -= self.data[i + k]
i += k
k //= 2
return i + 1
class LazySegmentTreeBase_:
def ope(self, l, r):
raise NotImplementedError
def e(self):
raise NotImplementedError
def mapping(self, f, x):
raise NotImplementedError
def composition(self, f, g):
raise NotImplementedError
def id_(self):
raise NotImplementedError
def __init__(self, n, init=None):
self.n = n
self.log = (n - 1).bit_length()
self.n0 = 1 << self.log
self.data = [self.e()] * (2 * self.n0)
self.lazy = [self.id_()] * self.n0
if init is not None:
for i in range(n):
self.data[self.n0 + i] = init[i]
for i in range(self.n0 - 1, 0, -1):
self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])
def _all_apply(self, p, f):
self.data[p] = self.mapping(f, self.data[p])
if p < self.n0:
self.lazy[p] = self.composition(f, self.lazy[p])
def _push(self, p):
self._all_apply(2 * p, self.lazy[p])
self._all_apply(2 * p + 1, self.lazy[p])
self.lazy[p] = self.id_()
def _update(self, p):
self.data[p] = self.ope(self.data[2 * p], self.data[2 * p + 1])
def set(self, p, x):
p += self.n0
for i in range(self.log, 0, -1):
self._push(p >> i)
self.data[p] = x
for i in range(1, self.log + 1):
self._update(p >> i)
def __setitem__(self, p, x):
self.set(p, x)
def get(self, p):
p += self.n0
for i in range(self.log, 0, -1):
self._push(p >> i)
return self.data[p]
def __getitem__(self, p):
return self.get(p)
def prod(self, l, r):
assert 0 <= l <= r <= self.n0
l += self.n0
r += self.n0
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self._push(l >> i)
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
lles = self.e()
rres = self.e()
while l < r:
if l & 1:
lles = self.ope(lles, self.data[l])
l += 1
if r & 1:
r -= 1
rres = self.ope(self.data[r], rres)
l >>= 1
r >>= 1
return self.ope(lles, rres)
def all_prod(self):
return self.data[1]
def _apply(self, p, f):
p += self.n0
for i in range(self.log, 0, -1):
self._push(p >> i)
self.data[p] = self.mapping(f, self.data[p])
for i in range(1, self.log + 1):
self._update(p >> i)
def apply(self, l, r, f=None):
if f is None:
self._apply(l, r)
return
if l == r:
return
l += self.n0
r += self.n0
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self._push(l >> i)
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
l2 = l
r2 = r
while l < r:
if l & 1:
self._all_apply(l, f)
l += 1
if r & 1:
r -= 1
self._all_apply(r, f)
l >>= 1
r >>= 1
l = l2
r = r2
for i in range(1, self.log + 1):
if ((l >> i) << i) != l:
self._update(l >> i)
if ((r >> i) << i) != r:
self._update((r - 1) >> i)
def max_right(self, l, f):
if l == self.n:
return self.n
l += self.n0
for i in range(self.log, 0, -1):
self._push(l >> i)
sm = self.e()
while 1:
while l % 2 == 0:
l >>= 1
if not f(self.ope(sm, self.data[l])):
while l < self.n0:
self._push(l)
l <<= 1
if f(self.ope(sm, self.data[l])):
sm = self.ope(sm, self.data[l])
l += 1
return l - self.n0
sm = self.ope(sm, self.data[l])
l += 1
if l & -l == l:
break
return self.n
def min_left(self, r, f):
if r == 0:
return 0
r += self.n0
for i in range(self.log, 0, -1):
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
sm = self.e()
while 1:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not f(self.ope(self.data[r], sm)):
while r < self.n0:
self._push(r)
r = 2 * r + 1
if f(self.ope(self.data[r], sm)):
sm = self.ope(self.data[r], sm)
r -= 1
return r + 1 - self.n0
sm = self.ope(self.data[r], sm)
if r & -r == r:
break
return 0
class MoBase_:
def add_left(self, i):
raise NotImplementedError
def add_right(self, i):
raise NotImplementedError
def delete_left(self, i):
raise NotImplementedError
def delete_right(self, i):
raise NotImplementedError
def rem(self, i):
raise NotImplementedError
def __init__(self, n, Q):
self.n = n
self.Q = Q
self.width = int(max(1, n / max(1, Q * 2.0 / 3.0) ** 0.5))
self.L = []
self.R = []
def insert(self, l, r):
self.L.append(l)
self.R.append(r)
def run(self):
def cmp(i):
b = self.L[i] // self.width
res = b * self.n * 3
if b % 2 == 0:
res += self.R[i]
else:
res -= self.R[i]
return res
order = [(i, cmp(i)) for i in range(self.Q)]
order.sort(key=lambda x: x[1])
nl = 0
nr = 0
for i, _ in order:
l = self.L[i]
r = self.R[i]
while nl > l:
nl -= 1
self.add_left(nl)
while nr < r:
self.add_right(nr)
nr += 1
while nl < l:
self.delete_left(nl)
nl += 1
while nr > r:
nr -= 1
self.delete_right(nr)
self.rem(i)
class Lseg(LazySegmentTreeBase_):
def ope(self, l, r):
return min(l, r)
def e(self):
return 1 << 60
def mapping(self, f, x):
return f + x
def composition(self, f, g):
return f + g
def id_(self):
return 0
class Mo(MoBase_):
def add_left(self, i):
global l, inv
l -= 1
seg.apply(0, A[l], -1)
inv -= bitR.sum(A[l])
inv -= bitL.sum(A[l] + 1, n)
bitL.add(A[l], -1)
def add_right(self, i):
global r, inv
seg.apply(A[r] + 1, n, -1)
inv -= bitR.sum(A[r])
inv -= bitL.sum(A[r] + 1, n)
bitR.add(A[r], -1)
r += 1
def delete_left(self, i):
global l, inv
seg.apply(0, A[l], 1)
inv += bitR.sum(A[l])
inv += bitL.sum(A[l] + 1, n)
bitL.add(A[l], 1)
l += 1
def delete_right(self, i):
global r, inv
r -= 1
seg.apply(A[r] + 1, n, 1)
inv += bitR.sum(A[r])
inv += bitL.sum(A[r] + 1, n)
bitR.add(A[r], 1)
def rem(self, i):
ans[i] = seg.all_prod() * (r - l) + inv
n, Q = map(int, input().split())
A = list(map(int, input().split()))
for i in range(n):
A[i] -= 1
mo = Mo(n, Q)
for _ in range(Q):
l, r = map(int, input().split())
mo.insert(l - 1, r)
seg = Lseg(n, [0] * n)
for a in A:
seg.apply(a + 1, n, 1)
bitL = BIT(n)
bitR = BIT(n)
inv = 0
for a in A:
inv += bitR.sum(a + 1, n)
bitR.add(a, 1)
ans = [0] * Q
l = 0
r = 0
mo.run()
print(*ans, sep="\n")