結果

問題 No.924 紲星
ユーザー gew1fw
提出日時 2025-06-12 13:49:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,425 bytes
コンパイル時間 387 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 232,360 KB
最終ジャッジ日時 2025-06-12 13:49:40
合計ジャッジ時間 6,906 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    queries_input = []
    for _ in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        queries_input.append((L, R))
        ptr += 2

    # Coordinate compression
    sorted_unique = sorted(list(set(A)))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    values = sorted_unique
    C = len(values)

    # Fenwick Tree
    class FenwickTree:
        def __init__(self, size):
            self.n = size
            self.count_tree = [0] * (self.n + 2)
            self.sum_tree = [0] * (self.n + 2)
        
        def update(self, idx, delta_c, delta_s):
            while idx <= self.n:
                self.count_tree[idx] += delta_c
                self.sum_tree[idx] += delta_s
                idx += idx & -idx
        
        def query_count(self, idx):
            res = 0
            while idx > 0:
                res += self.count_tree[idx]
                idx -= idx & -idx
            return res
        
        def query_sum(self, idx):
            res = 0
            while idx > 0:
                res += self.sum_tree[idx]
                idx -= idx & -idx
            return res

    ft = FenwickTree(C)

    # Mo's algorithm setup
    block_size = int(math.sqrt(N)) + 1

    queries = []
    for i in range(Q):
        L, R = queries_input[i]
        queries.append((i, L-1, R-1))  # Convert to 0-based indices

    # Sort queries using Mo's order
    queries.sort(key=lambda x: (x[1] // block_size, x[2] if (x[1] // block_size) % 2 == 0 else -x[2]))

    current_l = 0
    current_r = -1
    answers = [0] * Q

    def add_element(pos):
        val = A[pos]
        r = rank[val]
        ft.update(r, 1, val)

    def remove_element(pos):
        val = A[pos]
        r = rank[val]
        ft.update(r, -1, -val)

    for q in queries:
        idx, L, R = q
        # Expand current window to [L, R]
        while current_l > L:
            current_l -= 1
            add_element(current_l)
        while current_r < R:
            current_r += 1
            add_element(current_r)
        while current_l < L:
            remove_element(current_l)
            current_l += 1
        while current_r > R:
            remove_element(current_r)
            current_r -= 1

        # Calculate k for median
        length = R - L + 1
        k = (length + 1) // 2

        # Binary search to find the median's rank
        low, high = 1, C
        answer_rank = 0
        while low <= high:
            mid = (low + high) // 2
            cnt = ft.query_count(mid)
            if cnt >= k:
                answer_rank = mid
                high = mid - 1
            else:
                low = mid + 1

        if answer_rank == 0:
            median = 0
        else:
            median = values[answer_rank - 1]

        sum_less = ft.query_sum(answer_rank)
        count_less = ft.query_count(answer_rank)
        sum_total = ft.query_sum(C)
        sum_greater = sum_total - sum_less
        count_greater = length - count_less

        ans = (median * count_less - sum_less) + (sum_greater - median * count_greater)
        answers[idx] = ans

    # Output the answers in original order
    for ans in answers:
        print(ans)

if __name__ == '__main__':
    main()
0