結果

問題 No.924 紲星
ユーザー terasaterasa
提出日時 2023-01-06 20:23:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,880 ms / 4,000 ms
コード長 6,086 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 86,520 KB
実行使用メモリ 260,380 KB
最終ジャッジ日時 2023-08-20 13:33:21
合計ジャッジ時間 22,506 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 144 ms
80,116 KB
testcase_01 AC 147 ms
80,264 KB
testcase_02 AC 147 ms
80,124 KB
testcase_03 AC 195 ms
83,588 KB
testcase_04 AC 177 ms
82,852 KB
testcase_05 AC 185 ms
83,420 KB
testcase_06 AC 187 ms
83,392 KB
testcase_07 AC 165 ms
82,492 KB
testcase_08 AC 1,880 ms
249,288 KB
testcase_09 AC 1,863 ms
260,380 KB
testcase_10 AC 1,847 ms
249,436 KB
testcase_11 AC 1,812 ms
249,328 KB
testcase_12 AC 1,801 ms
248,396 KB
testcase_13 AC 919 ms
154,416 KB
testcase_14 AC 833 ms
148,296 KB
testcase_15 AC 837 ms
145,180 KB
testcase_16 AC 1,163 ms
233,276 KB
testcase_17 AC 1,146 ms
175,888 KB
testcase_18 AC 144 ms
80,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Tuple, Callable, TypeVar, Optional
import sys
import itertools
import heapq
import bisect
import math
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key

input = sys.stdin.readline

if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)


def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input()[:-1]
def readlist1(): return list(map(lambda x: int(x) - 1, input().split()))


class BitVector:
    # reference: https://tiramister.net/blog/posts/bitvector/
    # (reference implemention is succinct, but this implemention is not succinct.)
    def __init__(self, N):
        self.N = N
        self.block_num = (N + 31) >> 5
        self.bit = [0] * self.block_num
        self.sum = [0] * self.block_num

        self.built = False

    def set(self, pos):
        self.bit[pos >> 5] |= 1 << (pos & 31)

    def build(self):
        assert not self.built
        for i in range(1, self.block_num):
            self.sum[i] = self.sum[i - 1] + self.popcount(self.bit[i - 1])
        self.built = True

    def access(self, pos):
        """return pos-th bit"""
        return self.bit[pos >> 5] >> (pos & 31) & 1

    def rank(self, pos):
        """count 1's in [0, pos) range"""
        assert self.built
        i = pos >> 5
        offset = pos & 31
        return self.sum[i] + self.popcount(self.bit[i] & ((1 << offset) - 1))

    def select(self, num):
        """return minimum i that satisfies rank(i) = num"""
        assert self.built
        if num == 0:
            return 0
        if self.rank(self.N) < num:
            return -1

        l = -1
        r = self.N
        while r - l > 1:
            c = (l + r) >> 1
            if self.rank(c) >= num:
                r = c
            else:
                l = c
        return r

    def popcount(self, n):
        c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
        c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
        c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
        c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
        c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
        return c


class WaveletMatrix:
    # reference: https://miti-7.hatenablog.com/entry/2018/04/28/152259
    def __init__(self, A):
        self.nums = sorted(set(A))
        self.idx = {a: i for i, a in enumerate(self.nums)}
        self.A = [self.idx[a] for a in A]

        self.digit = (len(self.nums) - 1).bit_length()
        self.B = [None] * self.digit
        self.offset = [None] * self.digit
        self.start_index = {}

        T = self.A
        for k in range(self.digit)[::-1]:
            self.B[k] = BitVector(len(T) + 1)
            zeros = []
            ones = []
            for i, a in enumerate(T):
                if a >> k & 1:
                    self.B[k].set(i)
                    ones.append(a)
                else:
                    zeros.append(a)
            self.B[k].build()
            self.offset[k] = len(zeros)
            T = zeros + ones
        for i, a in enumerate(T):
            self.start_index.setdefault(a, i)

    def access(self, i):
        """return i-th value"""
        ret = 0
        cur = i
        for k in range(self.digit)[::-1]:
            if self.B[k].access(cur):
                ret |= (1 << k)
                cur = self.B[k].rank(cur) + self.offset[k]
            else:
                cur -= self.B[k].rank(cur)
        return self.nums[ret]

    def rank(self, i, x):
        """return the number of x's in [0, i) range"""
        x = self.idx.get(x)
        if x is None:
            return 0
        for k in range(self.digit)[::-1]:
            if x >> k & 1:
                i = self.B[k].rank(i) + self.offset[k]
            else:
                i -= self.B[k].rank(i)
        return i - self.start_index[x]

    def range_freq(self, l, r, x):
        """return the number of x's in [l, r) range"""
        return self.rank(r, x) - self.rank(l, x)

    def quantile(self, l, r, n):
        """return n-th (0-indexed) smallest value in [l, r) range"""
        assert 0 <= n < r - l
        ret = 0
        for k in range(self.digit)[::-1]:
            rank_l = self.B[k].rank(l)
            rank_r = self.B[k].rank(r)
            ones = rank_r - rank_l
            zeros = r - l - ones
            if zeros <= n:
                ret |= 1 << k
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
                n -= zeros
            else:
                l -= rank_l
                r -= rank_r
        return self.nums[ret]


class BIT:
    def __init__(self, N):
        self.N = N
        self.A = [0] * (N + 1)

    def add(self, i, x):
        """add x to i-th element (0-indexed)"""
        assert 0 <= i < self.N
        i += 1
        while i <= self.N:
            self.A[i] += x
            i += i & -i

    def sum(self, i):
        """return sum(A[:i])"""
        assert 0 <= i <= self.N
        s = 0
        while i > 0:
            s += self.A[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        """return sum(A[l:r])"""
        return self.sum(r) - self.sum(l)


N, Q = readints()
A = readlist()
WM = WaveletMatrix(A)
query = [tuple(readints()) for _ in range(Q)]

ans = [0] * Q
task = defaultdict(list)
for i in range(Q):
    l, r = query[i]
    l -= 1
    median = WM.quantile(l, r, (r - l) // 2)
    task[median].append((i, l, r))

idx = defaultdict(list)
bit = BIT(N)
bit2 = BIT(N)
for i, a in enumerate(A):
    idx[a].append(i)
nums = sorted(idx)
for k in nums:
    for i, l, r in task[k]:
        ans[i] += k * bit2.range_sum(l, r) - bit.range_sum(l, r)
    for i in idx[k]:
        bit.add(i, k)
        bit2.add(i, 1)
bit = BIT(N)
bit2 = BIT(N)
for k in nums[::-1]:
    for i, l, r in task[k]:
        ans[i] += bit.range_sum(l, r) - k * bit2.range_sum(l, r)
    for i in idx[k]:
        bit.add(i, k)
        bit2.add(i, 1)
print(*ans, sep='\n')
0