結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
👑  loop0919
|
| 提出日時 | 2025-10-05 16:10:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 800 ms / 2,000 ms |
| コード長 | 6,108 bytes |
| コンパイル時間 | 192 ms |
| コンパイル使用メモリ | 82,620 KB |
| 実行使用メモリ | 146,564 KB |
| 最終ジャッジ日時 | 2025-10-05 16:10:41 |
| 合計ジャッジ時間 | 17,159 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
class fenwick_tree:
n = 1
data = [0 for i in range(n)]
def __init__(self, N):
self.n = N
self.data = [0 for i in range(N)]
def add(self, p, x):
assert 0 <= p < self.n, "0<=p<n,p={0},n={1}".format(p, self.n)
p += 1
while p <= self.n:
self.data[p - 1] += x
p += p & -p
def sum(self, l, r):
assert 0 <= l and l <= r and r <= self.n, "0<=l<=r<=n,l={0},r={1},n={2}".format(l, r, self.n)
return self.sum0(r) - self.sum0(l)
def sum0(self, r):
s = 0
while r > 0:
s += self.data[r - 1]
r -= r & -r
return s
class lazy_segtree:
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2 * k, self.lz[k])
self.all_apply(2 * k + 1, self.lz[k])
self.lz[k] = self.identity
def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
self.n = len(V)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
self.lz = [ID for i in range(self.size)]
self.e = E
self.op = OP
self.mapping = MAPPING
self.composition = COMPOSITION
self.identity = ID
for i in range(self.n):
self.d[self.size + i] = V[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.d[p]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return self.e
l += self.size
r += self.size
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 >> i)
sml, smr = self.e, self.e
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.d[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def apply_point(self, p, f):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log + 1):
self.update(p >> i)
def apply(self, l, r, f):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return
l += self.size
r += self.size
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, r2 = l, 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, r = l2, 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, g):
assert 0 <= l and l <= self.n
assert g(self.e)
if l == self.n:
return self.n
l += self.size
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 (g(self.op(sm, self.d[l]))):
while l < self.size:
self.push(l)
l = 2 * l
if g(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, g):
assert 0 <= r and r <= self.n
assert g(self.e)
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r - 1) >> i)
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (g(self.op(self.d[r], sm))):
while r < self.size:
self.push(r)
r = 2 * r + 1
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
INF = 10**18
N, Q = map(int, input().split())
A = list(map(int, input().split()))
queries = [[] for _ in range(N)]
for i in range(Q):
l, r = map(lambda x: int(x) - 1, input().split())
queries[l].append((i, l, r))
seg = lazy_segtree(A, max, -INF, max, max, -INF)
update = [[] for _ in range(N)]
for i in range(N):
idx = seg.min_left(i, lambda v: v <= A[i])
update[idx].append(i)
answers = [0] * Q
count = fenwick_tree(N)
for l in range(N):
for v in update[l]:
count.add(v, 1)
for i, _, r in queries[l]:
answers[i] = (r - l + 1) - count.sum(l, r + 1)
# print([count.sum(j, j + 1) for j in range(N)])
print(*answers, sep="\n")