結果
| 問題 |
No.924 紲星
|
| コンテスト | |
| ユーザー |
 kohei2019
|
| 提出日時 | 2021-08-24 19:19:56 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,746 bytes |
| コンパイル時間 | 279 ms |
| コンパイル使用メモリ | 82,524 KB |
| 実行使用メモリ | 605,864 KB |
| 最終ジャッジ日時 | 2024-11-15 07:24:33 |
| 合計ジャッジ時間 | 43,874 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 MLE * 1 |
| other | AC * 6 TLE * 5 MLE * 5 |
ソースコード
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
import gc
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))
del SG
gc.collect()
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
del SGcnt
del keys
del lsLRmid
gc.collect()
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')