結果

問題 No.924 紲星
ユーザー kohei2019kohei2019
提出日時 2021-08-24 19:12:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 7,670 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 660,236 KB
最終ジャッジ日時 2024-11-15 07:08:31
合計ジャッジ時間 39,322 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 45 ms
62,972 KB
testcase_02 MLE -
testcase_03 AC 117 ms
84,384 KB
testcase_04 MLE -
testcase_05 AC 129 ms
85,348 KB
testcase_06 MLE -
testcase_07 AC 91 ms
77,388 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 AC 2,051 ms
282,568 KB
testcase_14 AC 1,584 ms
237,008 KB
testcase_15 AC 1,621 ms
247,840 KB
testcase_16 AC 3,771 ms
465,996 KB
testcase_17 AC 2,630 ms
317,480 KB
testcase_18 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

class SegTree:
    DEFAULT = {
        'min': 1 << 60,
        'max': -(1 << 60),
        'sum': 0,
        'prd': 1,
        'gcd': 0,
        'lmc': 1,
        '^': 0,
        '&': (1 << 60) - 1,
        '|': 0,
    }

    FUNC = {
        'min': min,
        'max': max,
        'sum': (lambda x, y: x + y),
        'prd': (lambda x, y: x * y),
        'gcd': math.gcd,
        'lmc': (lambda x, y: (x * y) // math.gcd(x, y)),
        '^': (lambda x, y: x ^ y),
        '&': (lambda x, y: x & y),
        '|': (lambda x, y: x | y),
    }

    def __init__(self, ls, mode='min', func=None, default=None):
        """
        要素ls, 関数mode (min,max,sum,prd(product),gcd,lmc,^,&,|)
        func,defaultを指定すれば任意の関数、単位元での計算が可能
        """
        N = len(ls)
        if default == None:
            self.default = self.DEFAULT[mode]
        else:
            self.default = default
        if func == None:
            self.func = self.FUNC[mode]
        else:
            self.func = func
        self.N = N
        self.K = (N - 1).bit_length()
        self.N2 = 1 << self.K
        self.dat = [self.default] * (2**(self.K + 1))
        for i in range(self.N):  # 葉の構築
            self.dat[self.N2 + i] = ls[i]
        self.build()

    def build(self):
        for j in range(self.N2 - 1, -1, -1):
            self.dat[j] = self.func(self.dat[j << 1], self.dat[j << 1 | 1])  # 親が持つ条件

    def leafvalue(self, x):  # リストのx番目の値
        return self.dat[x + self.N2]

    def update(self, x, y):  # index(x)をyに変更
        i = x + self.N2
        self.dat[i] = y
        while i > 0:  # 親の値を変更
            i >>= 1
            self.dat[i] = self.func(self.dat[i << 1], self.dat[i << 1 | 1])
        return

    def query(self, L, R):  # [L,R)の区間取得
        L += self.N2
        R += self.N2
        vL = self.default
        vR = self.default
        while L < R:
            if L & 1:
                vL = self.func(vL, self.dat[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.dat[R], vR)
            L >>= 1
            R >>= 1
        return self.func(vL, vR)
    
    def __iter__(self):
        for i in range(self.N):
            yield self[i]

    def __getitem__(self, x): return self.leafvalue(x) if (type(x) is int) else self.query(x[0],x[1])
    def __setitem__(self, x, val): return self.update(x, val)

class Node:
    def __init__(self,default):
        self.rch = None
        self.lch = None
        self.val = default
    
class PersistentSegTree:
    def __init__(self, ls):
        setnum = list(set(ls[:]))
        setnum.sort()
        self.dic_num_ID = dict()
        self.dic_ID_num = dict()
        for i,v in enumerate(setnum):
            self.dic_ID_num[i] = v
            self.dic_num_ID[v] = i
        ls = [self.dic_num_ID[i] for i in ls]
        self.N0 = len(ls)
        N = len(setnum)
        self.default = 0
        self.func =  (lambda x, y: x + y)
        self.N = N
        self.K = (N - 1).bit_length()
        self.N2 = 1 << self.K
        self.dat = [Node(0) for _ in range(2**(self.K + 1))]
        self.build()
        self.verdict = dict()
        self.verdict[-1] = 1
        for i in range(self.N0):
            self.update_x_val_told_tnew(ls[i],self.leafvalue_t(ls[i],i-1)+1,i-1,i)

    def build(self):
        for node in range(self.N2 - 1, 0, -1):
            self.dat[node].rch = self.dat[node<<1 | 1]
            self.dat[node].lch = self.dat[node<<1]
            self.dat[node].val = self.func(self.dat[node<<1 | 1].val,self.dat[node<<1].val)
            self.dat.pop()
            self.dat.pop()
    
    def leafvalue_t(self, x, t):  # ver.tにおけるリストのx番目の値
        '''
        version:tにおけるindex:xの値を出力
        '''
        x += self.N2
        v = self.dat[self.verdict[t]] # ver.tの根
        path = bin(x)[3:]
        for i in path:
            if i == '0':
                v = v.lch
            else:
                v = v.rch
        return v.val
    
    def update_x_val_told_tnew(self,x,val,told,tnew): # logN
        '''
        x: 変更するindex
        val: 変更後の値
        told: 変更前のversion
        tnew: 変更後のversion
        '''
        x += self.N2
        path = bin(x)[3:]
        self.verdict[tnew] = len(self.dat)
        new_nodes = [Node(self.default) for _ in range(len(path)+1)]
        v_old = self.dat[self.verdict[told]]
        v_new = new_nodes[0]
        now = 1
        for i in path: # ノードをつなげる
            if i == '0':
                v_new.rch = v_old.rch
                v_new.lch = new_nodes[now]
                v_new = new_nodes[now]
                v_old = v_old.lch 
            else:
                v_new.lch = v_old.lch
                v_new.rch = new_nodes[now]
                v_new = new_nodes[now]
                v_old = v_old.rch
            now += 1
        v_new.val = val
        for node in range(len(path)-1,-1,-1): # 付け加えたノードの値を子から親に更新
            new_nodes[node].val = self.func(new_nodes[node].lch.val,new_nodes[node].rch.val)
        self.dat.append(new_nodes[0])
    
    def get_all_t(self,t): # NlogN
        '''
        version:tにおける配列を出力
        return : list
        '''
        ret = []
        for i in range(self.N2,self.N2+self.N):
            path = bin(i)[3:]
            v = self.dat[self.verdict[t]]
            for p in path:
                if p == '0':
                    v = v.lch
                else:
                    v = v.rch
            ret.append(v.val)
        return ret

    def kth_query(self, L, R, k): # ver.tにおける[L,R)のクエリ
        '''
        区間kthクエリ[L,R)
        区間[L,R)でk番目に大きい数を出力 kは0オリジン
        '''
        k += 1
        if k > (R-L):
            return None
        vl = self.dat[self.verdict[L-1]]
        vr = self.dat[self.verdict[R-1]]
        path = 1
        cnt = 0
        while True:
            cntnow = cnt + vr.lch.val - vl.lch.val
            if cntnow < k:
                cnt += vr.lch.val-vl.lch.val
                path = (path << 1) | 1
                vl = vl.rch
                vr = vr.rch
            else:
                path = (path << 1)
                vl = vl.lch
                vr = vr.lch
            if vl.lch == None:
                break
        path -= self.N2
        return self.dic_ID_num[path]
    
import collections
N, Q = map(int,input().split())
lsA = list(map(int,input().split()))
dic_num_ls = collections.defaultdict(lambda:[])
for i in range(N):
    dic_num_ls[lsA[i]].append(i)

SG = PersistentSegTree(lsA)
lsLRmid = []
for i in range(Q): #(L,R,mid,i) [L,R)で持つ
    L,R = map(int,input().split())
    L -= 1
    mid = SG.kth_query(L,R,(R-L)//2)
    lsLRmid.append((L,R,mid,i))

lsLRmid.sort(key=lambda x:x[2])

lsLRnew = []
md = 0
keys = list(dic_num_ls.keys())
keys.sort()
SGsum = SegTree([0]*N,mode='sum')
SGcnt = SegTree([0]*N,mode='sum')
for key in keys:
    for j in dic_num_ls[key]:
        SGsum.update(j,key)
        SGcnt.update(j,1)
    while md <Q and lsLRmid[md][2] == key:
        L,R,mid,i = lsLRmid[md]
        sm = SGsum.query(L,R)
        cnt = SGcnt.query(L,R)
        sm -= mid*(cnt-((R-L)//2+1))
        lsLRnew.append((L,R,mid,sm,i))
        md += 1

ans = [0]*(Q)
for q in range(Q):
    L,R,mid,sm,i = lsLRnew[q]
    val = SGsum.query(L,R) - 2*sm
    if (R-L) % 2 == 0:
        val += 2*mid
    else:
        val += mid
    ans[i] = val

print(*ans,sep='\n')
0