結果

問題 No.1270 Range Arrange Query
ユーザー 👑 rin204rin204
提出日時 2023-12-29 16:50:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,552 ms / 7,000 ms
コード長 8,879 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 84,268 KB
最終ジャッジ日時 2023-12-29 16:51:10
合計ジャッジ時間 23,937 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
55,824 KB
testcase_01 AC 40 ms
55,824 KB
testcase_02 AC 41 ms
55,824 KB
testcase_03 AC 87 ms
76,060 KB
testcase_04 AC 41 ms
55,824 KB
testcase_05 AC 92 ms
75,924 KB
testcase_06 AC 494 ms
79,912 KB
testcase_07 AC 2,431 ms
81,116 KB
testcase_08 AC 621 ms
80,148 KB
testcase_09 AC 1,768 ms
81,328 KB
testcase_10 AC 1,874 ms
81,108 KB
testcase_11 AC 4,297 ms
83,236 KB
testcase_12 AC 4,552 ms
83,644 KB
testcase_13 AC 4,463 ms
84,268 KB
testcase_14 AC 273 ms
81,512 KB
testcase_15 AC 464 ms
82,812 KB
testcase_16 AC 439 ms
82,164 KB
testcase_17 AC 481 ms
82,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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")
0