#959001 (Python3) No.3494 一点挿入区間和取得

• 問題: No.3494 一点挿入区間和取得
• ユーザー: 👑 p-adic
• 提出日時: 2024-03-09 09:42:55
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: TLE
• 実行時間: -
• コード長: 3,834 bytes
• コンパイル時間: 316 ms
• コンパイル使用メモリ: 20,828 KB
• 実行使用メモリ: 33,616 KB
• 最終ジャッジ日時: 2026-04-03 20:52:34
• 合計ジャッジ時間: 11,905 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge5_0

ファイルパターン	結果
other	AC * 15 TLE * 1 -- * 7

ソースコード

class dliterator:
	def __init__(self,a,i):
		self.a,self.i=a,i
	def __eq__(self,i):
		return id(self.a)==id(i.a)and self.i==i.i
	def get(self):
		assert(self.i)
		return self.a.a[self.i][0]
	def set(self,x):
		assert(self.i)
		self.a.a[self.i][0]=x
	def copy(self):
		return dliterator(self.a,self.i)
	def next(self,c=1):
		for _ in R(c):
			self.i=self.a.a[self.i][2]
			assert(self.i>=0)
	def prev(self,c=1):
		for _ in R(c):
			self.i=self.a.a[self.i][1]
			assert(self.i>=0)
	def shift(c):
		if c<0:self.prev(-c)
		else:self.next(c)
	def __ladd__(self,c):
		self.shift(c)
	def __lsub__(self,c):
		self.shift(-c)
class dllist:
	def __init__(self,init=[]):
		n=len(init)
		self.a=[[n,n,0]]+[[x,i,i+2]for x,i in zip(init,R(n))]
		if n:self.a[0][2],self.a[-1][2]=1,0
		self.i=self.end()
	def size(self):
		return self.a[0][0]
	def end(self):
		return dliterator(self,0)
	def rend(self):
		return self.end()
	def begin(self):
		n=self.end()
		n.next()
		return n
	def rbegin(self):
		n=self.rend()
		n.prev()
		return n
	def front(self):
		return self.begin().get()
	def back(self):
		return self.rbegin().get()
	def insert_between(self,i,j,x,c):
		assert(id(i.a)==id(self)==id(j.a)and self.a[i.i][2]>=0 and self.a[j.i][2]>=0)
		k=j.copy()
		for _ in R(c):
			self.a[0][0]+=1
			n=self.i.i
			v=[x,i.i,k.i]
			if n:
				assert(self.a[n][2]==-1)
				self.i.prev()
				self.a[n]=v
			else:
				n=len(self.a)
				self.a+=[v]
			self.a[i.i][2]=self.a[k.i][1]=n
			k=dliterator(self,n)
	def insert_front(self,i,x,c=1):
		j=i.copy()
		j.prev()
		self.insert_between(j,i,x,c)
	def insert_back(self,i,x,c=1):
		j=i.copy()
		j.next()
		self.insert_between(i,j,x,c)
	def push_front(self,x,c=1):
		self.insert_front(self.begin(),x,c)
	def push_back(self,x,c=1):
		self.insert_back(self.rbegin(),x,c)
	def __ladd__(self,a):
		for x in a:self.push_back(x)
	def erase(self,i):
		assert(self.size()and id(i.a)==id(self)and i.i and self.a[i.i][2]>=0)
		self.a[0][0]-=1
		m=i.copy()
		m.prev()
		l=i.copy()
		l.next()
		self.a[m.i][2],self.a[l.i][1]=l.i,m.i
		self.i,self.a[i.i][1]=i,self.i.i
		self.a[i.i][2]=-1
	def pop_front(self):
		self.erase(self.begin())
	def pop_back(self):
		self.erase(self.rbegin())
	def clear(self):
		self.a,self.i=[[0,0,0]],self.end()
	def list(self):
		a=[]
		i=self.begin()
		e=self.end()
		while i!=e:
			a+=[i.get()]
			i.next()
		return a
	def copy(self):
		return dllist(self.list())
R=range
J=lambda:map(int,input().split())
N,Q=J()
B=int((N+Q)**0.5)+1
X=dllist([dllist()])
Y=dllist([0])
for a in J():
	if X.back().size()<B:
		X.back().push_back(a)
		Y.rbegin().set(Y.back()+a)
	else:
		X.push_back(dllist([a]))
		Y.push_back(a)
def Search(itr_X,itr_Y,j):
	while 1:
		j-=itr_X.get().size()
		if j<0:
			j+=itr_X.get().size()
			break
		else:itr_X.next(),itr_Y.next()
	return j
for q in R(Q):
	i,x,l,r=J()
	i-=1
	l-=1
	r-=1
	itr1_X=X.begin()
	itr1_Y=Y.begin()
	i=Search(itr1_X,itr1_Y,i)
	X_k1=itr1_X.get()
	Y_k1=itr1_Y.get()
	j=X_k1.begin()
	j.next(i)
	X_k1.insert_back(j,x)
	Y_k1+=x
	itr1_Y.set(Y_k1)
	if X_k1.size()>>1==B:
		X.insert_front(itr1_X,dllist())
		itr=itr1_X.copy()
		itr.prev()
		X_k1_minus=itr.get()
		Y_k1_minus=0
		for b in R(B):
			temp=X_k1.front()
			X_k1_minus.push_back(temp)
			Y_k1-=temp
			Y_k1_minus+=temp
			X_k1.pop_front()
		itr1_Y.set(Y_k1)
		Y.insert_front(itr1_Y,Y_k1_minus)
	r-=l
	answer=0
	itr2_X=X.begin()
	itr2_Y=Y.begin()
	l=Search(itr2_X,itr2_Y,l)
	X_k2=itr2_X.get()
	itr=X_k2.begin()
	end=X_k2.end()
	itr.next(l)
	while itr!=end:
		if r<0:break
		r-=1
		answer+=itr.get()
		itr.next()
	if r>=0:
		itr2_X.next()
		itr2_Y.next()
		itr3_X=itr2_X.copy()
		itr3_Y=itr2_Y.copy()
		r=Search(itr3_X,itr3_Y,r)
		while itr2_Y!=itr3_Y:
			answer+=itr2_Y.get()
			itr2_Y.next()
		X_k3=itr3_X.get()
		itr=X_k3.begin()
		while r>=0:
			r-=1
			answer+=itr.get()
			itr.next()
	print(answer)