結果

問題 No.2697 Range LIS Query
コンテスト
ユーザー seekworser
提出日時 2024-02-06 16:38:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 6,956 ms / 10,000 ms
コード長 3,532 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 276,908 KB
最終ジャッジ日時 2024-09-28 12:38:37
合計ジャッジ時間 66,736 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().strip()
class lazy_segtree:
    def __init__(self, v, op, e, mapping, composition, id_):
        n = len(v)
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_
        self._size = 1 << (n - 1).bit_length()
        self._d = [e] * (2 * self._size)
        self._lz = [id_] * 2 * self._size
        for i in range(n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])

    def _gindex(self, l, r):
        l += self._size
        r += self._size
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()
        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            l >>= 1
            r >>= 1
        while l:
            yield l
            l >>= 1

    def _propagates(self, *ids):
        for i in reversed(ids):
            f = self._lz[i]
            self._lz[i] = self._id
            self._lz[2 * i] = self._composition(f, self._lz[2 * i])
            self._lz[2 * i + 1] = self._composition(f, self._lz[2 * i + 1])
            self._d[2 * i] = self._mapping(f, self._d[2 * i])
            self._d[2 * i + 1] = self._mapping(f, self._d[2 * i + 1])

    def apply(self, l, r, f):
        (*ids,) = self._gindex(l, r)
        self._propagates(*ids)
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                self._lz[l] = self._composition(f, self._lz[l])
                self._d[l] = self._mapping(f, self._d[l])
                l += 1
            if r & 1:
                self._lz[r - 1] = self._composition(f, self._lz[r - 1])
                self._d[r - 1] = self._mapping(f, self._d[r - 1])
            l >>= 1
            r >>= 1
        for i in ids:
            self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])

    def prod(self, l, r):
        self._propagates(*self._gindex(l, r))
        resl = self._e
        resr = self._e
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                resl = self._op(resl, self._d[l])
                l += 1
            if r & 1:
                resr = self._op(self._d[r - 1], resr)
            l >>= 1
            r >>= 1
        return self._op(resl, resr)


K=4
def id(i,j):return i*K+j
def expand(z):
    for l in range(1,K):
        for i in range(K-l):
            z[id(i,i+l)]=max(z[id(i,i+l)],z[id(i+1,i+l)],z[id(i,i+l-1)])
    return z

def op(x,y):
    x=expand(x);y=expand(y)
    z=[0]*(K*K+1);z[K*K]=x[K*K]+y[K*K]
    for i in range(K):
        for j in range(i,K):
            for k in range(j,K):z[id(i,k)]=max(z[id(i,k)],x[id(i,j)]+y[id(j,k)])
    return z

def mapping(f:int,x):
    if f==-1:return x
    z=[0]*(K*K+1);z[K*K]=x[K*K]
    z[id(f,f)]=x[K*K]
    return z

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

N=int(input())
A=list(map(int,input().split()))
D=[]
for i in range(N):
    A[i]-=1
    z=[0]*(K*K+1);z[K*K]=1
    z[id(A[i],A[i])]=1
    D.append(z)
seg = lazy_segtree(D,op,[0]*(K*K+1),mapping,composition,-1)


Q=int(input())
ans=[]
while Q:
    Q-=1
    q=list(map(int,input().split()))
    if q[0]==1:
        l,r=q[1],q[2];l-=1
        res=seg.prod(l,r);res=expand(res)
        print(res[id(0,K-1)])
    if q[0]==2:
        l,r,x=q[1],q[2],q[3]
        l-=1;x-=1
        seg.apply(l,r,x)
0