結果

問題 No.2697 Range LIS Query
ユーザー PNJPNJ
提出日時 2024-03-22 21:54:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 9,201 ms / 10,000 ms
コード長 5,234 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 273,980 KB
最終ジャッジ日時 2024-09-30 11:26:48
合計ジャッジ時間 86,715 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
62,268 KB
testcase_01 AC 34 ms
54,896 KB
testcase_02 AC 73 ms
74,908 KB
testcase_03 AC 641 ms
94,788 KB
testcase_04 AC 620 ms
94,096 KB
testcase_05 AC 634 ms
93,856 KB
testcase_06 AC 7,680 ms
271,272 KB
testcase_07 AC 7,660 ms
270,768 KB
testcase_08 AC 8,096 ms
271,788 KB
testcase_09 AC 5,629 ms
195,540 KB
testcase_10 AC 5,096 ms
195,240 KB
testcase_11 AC 5,190 ms
194,608 KB
testcase_12 AC 5,602 ms
273,980 KB
testcase_13 AC 5,645 ms
272,112 KB
testcase_14 AC 6,851 ms
273,032 KB
testcase_15 AC 9,201 ms
273,068 KB
testcase_16 AC 8,189 ms
273,448 KB
testcase_17 AC 8,484 ms
272,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().strip()

class LazySegTree():
  # G:モノイド F:写像の集合
  # operate(x,y): x*y (G×G -> G)
  # mapping(f,x): f(x) (F×G -> G)
  # composition(f,g): f ○ g (F×F -> F)
  # element: Gの単位元
  # identity: Fの単位元(恒等写像)
  def __init__(self,V,operate,element,mapping,composition,identity):
    self.n = len(V)
    self.log = (self.n - 1).bit_length()
    self.size = 1 << self.log
    self.d = [element for i in range(2*self.size)]
    self.lz = [identity for i in range(self.size)]
    self.e = element
    self.op = operate
    self.mapping = mapping
    self.comp = composition
    self.id = identity
    for i in range(self.n):
      self.d[self.size + i] = V[i]
    for i in range(self.size - 1,0,-1):
      self.update(i)
  def all_apply(self,k,f):
    self.d[k] = self.mapping(f,self.d[k])
    if (k < self.size):
      self.lz[k] = self.comp(f,self.lz[k])
  def update(self,k):
    self.d[k] = self.op(self.d[2*k],self.d[2*k+1])
  def push(self,k):
    self.all_apply(2*k,self.lz[k])
    self.all_apply(2*k+1,self.lz[k])
    self.lz[k] = self.id

  def set(self,p,x): # V[p] -> x
    assert 0 <= p < self.n
    p += self.size
    for i in range(self.log,0,-1):
      self.push(p >> i)
    self.d[p] = x
    for i in range(1,self.log+1):
      self.update(p >> i)

  def get(self,p): # V[p]を取得
    assert 0 <= p < self.n
    p += self.size
    for i in range(self.log,0,-1):
      self.push(p>>i)
    return self.d[p]

  def prod(self,l,r): # [l,r)での値の取得
    assert 0 <= l <= r <= self.n
    if l==r:
      return self.e
    l += self.size
    r += self.size
    for i in range(self.log,0,-1):
      if (((l >> i) << i)!=l):
        self.push(l >> i)
      if (((r >> i) << i)!=r):
        self.push(r >> i)
    sml = smr = self.e
    while l < r:
      if l & 1:
        sml = self.op(sml,self.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.op(self.d[r],smr)
      l >>= 1
      r >>= 1
    return self.op(sml,smr)

  def all_prod(self):
    return self.d[1]

  def apply_point(self,p,f): # p -> f(p)
    assert 0<=p and p<self.n
    p+=self.size
    for i in range(self.log,0,-1):
      self.push(p>>i)
    self.d[p]=self.mapping(f,self.d[p])
    for i in range(1,self.log+1):
      self.update(p>>i)
  def apply(self,l,r,f): # [l,r)のxをf(x)
    assert 0 <= l <= r <= self.n
    if l == r:
      return
    l += self.size
    r += self.size
    for i in range(self.log,0,-1):
      if ((l >> i) << i)!= l:
        self.push(l >> i)
      if ((r >> i) << i) != r:
        self.push((r-1) >> i)
    l_,r_ = l,r
    while l < r:
      if (l&1):
        self.all_apply(l,f)
        l+=1
      if (r&1):
        r-=1
        self.all_apply(r,f)
      l >>= 1
      r >>= 1
    l,r = l_,r_
    for i in range(1,self.log+1):
      if ((l >> i) << i) != l:
        self.update(l>>i)
      if ((r >> i) << i) != r:
        self.update((r-1) >> i)

  def max_right(self,l,g): # x = prod(l,r), g(x) = true となる、最大のrを求める。
    assert 0 <= l <= self.n
    assert g(self.e)
    if l == self.n:
      return self.n
    l += self.size
    for i in range(self.log,0,-1):
      self.push(l >> i)
    sm=self.e
    while(1):
      while(l%2 == 0):
        l >>= 1
      if not(g(self.op(sm,self.d[l]))):
        while(l < self.size):
          self.push(l)
          l = 2*l
          if (g(self.op(sm,self.d[l]))):
            sm = self.op(sm,self.d[l])
            l += 1
        return l - self.size
      sm = self.op(sm,self.d[l])
      l += 1
      if (l & -l) == l:
        break
    return self.n
  
  def min_left(self,r,g): # x = prod(l,r), g(x) = true となる、最小のlを求める。
    assert (0 <= r <=self.n)
    assert g(self.e)
    if r == 0:
      return 0
    r += self.size
    for i in range(self.log,0,-1):
      self.push((r-1) >> i)
    sm=self.e
    while(1):
      r -= 1
      while(r > 1 and (r%2)):
        r >>= 1
      if not(g(self.op(self.d[r],sm))):
        while(r < self.size):
          self.push(r)
          r = 2*r + 1
          if g(self.op(self.d[r],sm)):
            sm = self.op(self.d[r],sm)
            r -= 1
        return r + 1 - self.size
      sm = self.op(self.d[r],sm)
      if (r & -r) == r:
        break
    return 0

def op(x,y):
  c = x[1] + y[1]
  z = [0 for j in range(16)]
  for i in range(4):
    for j in range(i,4):
      for k in range(j,4):
        for l in range(k,4):
          z[4*i+l] = max(z[4*i+l],x[0][4*i+j] + y[0][4*k+l])
  return (z,c)

def mapping(f,x):
  if f == -1:
    return x
  c = x[1]
  z = [0 for i in range(16)]
  z[5*f] = c
  return (z,c)

def composing(f,g):
  if f == -1:
    return g
  return f

N = int(input())
A = list(map(int,input().split()))
X = [([0 for j in range(16)],1) for j in range(N)]
seg = LazySegTree(X,op,([0 for j in range(16)],0),mapping,composing,-1)
for i in range(N):
  seg.apply_point(i,A[i]-1)

Q = int(input())
for _ in range(Q):
  q = list(map(int,input().split()))
  l,r = q[1],q[2]
  if q[0] == 1:
    z = seg.prod(l-1,r)[0]
    ans = 0
    for i in range(4):
      for j in range(4):
        ans = max(z[4*i+j],ans)
    print(ans)
  else:
    x = q[3] - 1
    seg.apply(l-1,r,x)
0