結果

問題 No.2697 Range LIS Query
ユーザー iseeisee
提出日時 2024-02-06 21:55:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,316 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 134,956 KB
最終ジャッジ日時 2024-02-07 21:30:25
合計ジャッジ時間 13,098 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,588 KB
testcase_01 AC 41 ms
53,588 KB
testcase_02 AC 38 ms
53,588 KB
testcase_03 AC 299 ms
78,216 KB
testcase_04 AC 302 ms
78,216 KB
testcase_05 AC 299 ms
78,208 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

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)])
    
    answers = []

    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)
            answers.append(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]
    print('\n'.join(map(str, answers)))

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