結果

問題 No.2697 Range LIS Query
コンテスト
ユーザー isee
提出日時 2024-02-06 21:48:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,249 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 133,180 KB
最終ジャッジ日時 2024-09-28 12:37:02
合計ジャッジ時間 13,151 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from math import isqrt

K = 4

def main():
    # 入力
    N = int(input())
    A = [a-1 for a in list(map(int, input().split()))]
    # 計算・出力
    L = isqrt(K*N)
    
    def genB(X):
        # B[i][j] := i 以上 j 以下の数での LIS
        # を構成
        res = []
        for i in range(K):
            row = [0]*K
            for x in X:
                if x < i: continue
                row[x] = max(row[:x+1])+1
            for j in range(1, K):
                row[j] = max(row[j-1], row[j])
            res.append(row)
        return res
    
    def merB(B1, B2):
        # B をマージする (B1+B2)[i][j] = max(B1[i][k] + B2[k][j] | i <= k <= j)
        res = [[0]*K for _ in range(K)]
        for i in range(K):
            resi = res[i]
            B1i = B1[i]
            for k in range(i, K):
                B1ik = B1i[k]
                B2k = B2[k]
                for j in range(k, K):
                    resi[j] = max(resi[j], B1ik+B2k[j])
        return res
    
    B = []
    for l in range(0, N+1, L):
        B.append(genB(A[l:l+L]))

    C = [-1]*(len(B)+1)  # C[i] = x if i 番目の区間が全て x になっている else -1

    BO = []  # 区間内が全て同じ数のときの B
    for x in range(K):
        BO.append([[L if i <= x <= j else 0 for j in range(K)] for i in range(K)])
    
    Q = int(input())
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            # 計算クエリ
            _, l, r = query
            l -= 1
            lidx = l // L
            ridx = r // L
            if lidx == ridx:
                # [l, r) が1つの区間に収まる
                if C[lidx] != -1:
                    y = C[lidx]
                    Lm = r - l
                    ans = [[Lm if i <= y <= j else 0 for j in range(K)] for i in range(K)]
                else:
                    ans = genB(A[l:r])
            else:
                # 左
                if C[lidx] != -1:
                    y = C[lidx]
                    Ll = (lidx+1)*L - l
                    Bl = [[Ll if i <= y <= j else 0 for j in range(K)] for i in range(K)]
                else:
                    Bl = genB(A[l:(lidx+1)*L])
                # 右
                if C[ridx] != -1:
                    y = C[ridx]
                    Lr = r - ridx*L
                    Br = [[Lr if i <= y <= j else 0 for j in range(K)] for i in range(K)]
                else:
                    Br = genB(A[ridx*L:r])
                ans = Bl
                for i in range(lidx+1, ridx):
                    ans = merB(ans, B[i])
                ans = merB(ans, Br)
            print(ans[0][-1])
        else:
            # 更新クエリ
            _, l, r, x = query
            l -= 1
            x -= 1
            lidx = l // L
            ridx = r // L
            if lidx == ridx:
                # [l, r) が1つの区間に収まる
                if C[lidx] != -1:
                    y = C[lidx]
                    for i in range(lidx*L, l):
                        A[i] = y
                    for i in range(r, min((lidx+1)*L, N)):
                        A[i] = y
                    C[lidx] = -1
                for i in range(l, r):
                    A[i] = x
                B[lidx] = genB(A[lidx*L:(lidx+1)*L])
            else:
                # 左
                if C[lidx] != -1:
                    y = C[lidx]
                    for i in range(lidx*L, l):
                        A[i] = y
                    C[lidx] = -1
                for i in range(l, (lidx+1)*L):
                    A[i] = x
                B[lidx] = genB(A[lidx*L:(lidx+1)*L])
                # 右
                if C[ridx] != -1:
                    y = C[ridx]
                    for i in range(r, min((ridx+1)*L, N)):
                        A[i] = y
                    C[ridx] = -1
                for i in range(ridx*L, r):
                    A[i] = x
                B[ridx] = genB(A[ridx*L:(ridx+1)*L])
                # 中
                for midx in range(lidx+1, ridx):
                    C[midx] = x
                    B[midx] = BO[x]

if __name__ == "__main__":
    main()
0