結果
| 問題 |
No.3167 [Cherry 7th Tune C] Cut in Queue
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-11-19 22:51:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,060 bytes |
| コンパイル時間 | 401 ms |
| コンパイル使用メモリ | 82,704 KB |
| 実行使用メモリ | 251,156 KB |
| 最終ジャッジ日時 | 2025-05-30 21:02:51 |
| 合計ジャッジ時間 | 18,565 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 2 |
| other | RE * 43 |
ソースコード
class Doubly_Linked_List:
def __init__(self, N):
self.__N=N
self.__front=[-1]*N
self.__back=[-1]*N
def __len__(self):
return self.__N
def __str__(self):
res=[]
used=[0]*self.__N
for x in range(self.__N):
if used[x]:
continue
a=self.enumerate(x)
for y in a:
used[y]=1
res.append(a)
return str(res)
def __repr__(self):
return "[Doubly Linked List]: "+str(self)
def previous(self, x, default=-1):
return self.__front[x] if self.__front[x]!=-1 else default
def next(self, x, default=-1):
return self.__back[x] if self.__back[x]!=-1 else default
def disconnect_front(self, x):
""" x から前に伸びるリンクを削除する.
"""
front=self.__front; back=self.__back
y=front[x]
if y>=0:
front[x]=-1
back[y]=-1
def disconnect_back(self, x):
""" x から後ろに伸びるリンクを削除する.
"""
front=self.__front; back=self.__back
y=back[x]
if y>=0:
back[x]=-1
front[y]=-1
def extract(self, x):
""" x に接続するリンクを削除し, x の前後が存在するならば, それらをつなぐ.
"""
a=self.__front[x]
b=self.__back[x]
self.disconnect_front(x)
self.disconnect_back(x)
if a!=-1 and b!=-1:
self.connect(a,b)
def connect(self, x, y):
""" x から y へのリンクを生成する (すでにある x からのリンクと y へのリンクは削除される).
"""
self.disconnect_back(x)
self.disconnect_front(y)
self.__back[x]=y
self.__front[y]=x
def insert_front(self, x, y):
""" x の前に y を挿入する.
"""
z=self.__front[x]
self.connect(y,x)
if z!=-1:
self.connect(z,y)
def insert_back(self, x, y):
""" x の後に y を挿入する.
"""
z=self.__back[x]
self.connect(x,y)
if z!=-1:
self.connect(y,z)
def head(self, x):
""" x が属する弱連結成分の先頭を求める.
"""
while self.__front[x]!=-1:
x=self.__front[x]
return x
def tail(self, x):
""" x が属する弱連結成分の末尾を求める.
"""
while self.__back[x]!=-1:
x=self.__back[x]
return x
def enumerate(self, x):
""" x が属している弱連結成分を先頭から順に出力する.
"""
x=self.head(x)
res=[x]
while self.__back[x]>=0:
x=self.__back[x]
res.append(x)
return res
def depth(self, x):
dep=0
while self.__front[x]!=-1:
x=self.__front[x]
dep+=1
return dep
class Binary_Indexed_Tree():
def __init__(self, L, op, zero, neg):
""" op を演算とする N 項の Binary Indexed Tree を作成
op: 演算 (2変数関数, 可換群)
zero: 群 op の単位元 (x+e=e+x=x を満たす e)
neg : 群 op の逆元 (1変数関数, x+neg(x)=neg(x)+x=e をみたす neg(x))
"""
self.op=op
self.zero=zero
self.neg=neg
self.N=N=len(L)
self.log=N.bit_length()-1
X=[zero]*(N+1)
for i in range(N):
p=i+1
X[p]=op(X[p],L[i])
q=p+(p&(-p))
if q<=N:
X[q]=op(X[q], X[p])
self.data=X
def get(self, k):
""" 第 k 要素の値を出力する.
k : 数列の要素
index: 先頭の要素の番号
"""
return self.sum(k, k)
def add(self, k, x):
""" 第 k 要素に x を加え, 更新を行う.
k : 数列の要素
x : 加える値
"""
data=self.data; op=self.op
p=k+1
while p<=self.N:
data[p]=op(self.data[p], x)
p+=p&(-p)
def update(self, k, x):
""" 第 k 要素を x に変え, 更新を行う.
k: 数列の要素
x: 更新後の値
"""
a=self.get(k)
y=self.op(self.neg(a), x)
self.add(k,y)
def sum(self, l, r):
""" 第 l 要素から第 r 要素までの総和を求める.
※ l != 0 を使うならば, 群でなくてはならない.
l: 始まり
r: 終わり
"""
l=l+1 if 0<=l else 1
r=r+1 if r<self.N else self.N
if l>r:
return self.zero
elif l==1:
return self.__section(r)
else:
return self.op(self.neg(self.__section(l-1)), self.__section(r))
def __section(self, x):
""" B[0]+...+B[x] を求める. """
data=self.data; op=self.op
S=self.zero
while x>0:
S=op(data[x], S)
x-=x&(-x)
return S
def all_sum(self):
return self.sum(0, self.N-1)
def binary_search(self, cond):
""" cond(B[0]+...+B[k]) が True となるような最小の k を返す.
cond: 単調増加
※ cond(zero)=True の場合の返り値は -1 とする.
※ cond(B[0]+...+B[k]) なる k が (0<=k<N に) 存在しない場合の返り値は N とする.
"""
if cond(self.zero):
return -1
j=0
r=self.N
t=1<<self.log
data=self.data; op=self.op
alpha=self.zero
while t>0:
if j+t<=self.N:
beta=op(alpha, data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j
def __getitem__(self, index):
if isinstance(index, int):
return self.get(index)
else:
return [self.get(t) for t in index]
def __setitem__(self, index, val):
self.update(index, val)
def __iter__(self):
for k in range(self.N):
yield self.sum(k, k)
#==================================================
def solve():
from operator import add, neg
from collections import defaultdict
N = int(input())
A = [0] + list(map(int, input().split()))
length = N
Q = int(input())
Query = []
for _ in range(Q):
q, *value = map(int, input().split())
if q == 1:
length += 1
Query.append((q, *value))
L = Doubly_Linked_List(length + 2)
start = 0; goal = length + 1
for i in range(1, N + 1):
L.connect(i - 1, i)
L.connect(N, goal)
index = defaultdict(list)
for i,a in enumerate(A[1:], 1):
index[a].append(i)
j = N
for q, *value in Query:
if q == 1:
x, y = value
if x != -1:
i = index[x][-1]
else:
i = 0
j += 1
k = L.next(i)
L.connect(i, j)
L.connect(j, k)
index[y].append(j)
L_inv = [0] * (length + 2); ind = 0
for k in range(length + 2):
L_inv[ind] = k
ind = L.next(ind)
index_inv = {v: [L_inv[x] for x in index[v]][::-1] for v in index}
B = Binary_Indexed_Tree([0] * (length + 2), add, 0, neg)
for i, a in enumerate(A[1:], 1):
B.add(index_inv[a][-1], a)
ans = []
for q, *value in Query:
if q == 1:
x, y = value
B.add(index_inv[y][-1], y)
elif q == 2:
x, = value
B.add(index_inv[x][-1], -x)
index_inv[x].pop()
else:
x, y = value
s = index_inv[x][-1]; t = index_inv[y][-1]
l = min(s, t); r = max(s, t)
ans.append(B.sum(l, r))
return ans
#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
write("\n".join(map(str, solve())))