結果

問題 No.2697 Range LIS Query
コンテスト
ユーザー detteiuu
提出日時 2025-07-21 23:45:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7,440 ms / 10,000 ms
コード長 2,019 bytes
コンパイル時間 7,211 ms
コンパイル使用メモリ 334,300 KB
実行使用メモリ 100,388 KB
最終ジャッジ日時 2025-07-21 23:47:15
合計ジャッジ時間 75,550 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;

struct Node {
    vector<vector<int>> L;
    int size;
};

Node op(Node left, Node right) {
    vector<vector<int>> A(4, vector<int> (4, 0));
    for (int i=0; i<4; i++) {
        for (int j=i; j<4; j++) {
            for (int k=i; k<j+1; k++) {
                for (int l=k; l<j+1; l++) {
                    A[i][j] = max(A[i][j], left.L[i][k]+right.L[l][j]);
                }
            }
        }
    }
    return Node(A, left.size+right.size);
}
Node e() {
    vector<vector<int>> A(4, vector<int> (4, 0));
    return Node(A, 0);
}
Node mapping(int top, Node bottom) {
    if (top == INF) {
        return bottom;
    }
    vector<vector<int>> A(4, vector<int> (4, 0));
    A[top-1][top-1] = bottom.size;
    return Node(A, bottom.size);
}
int composition(int top, int bottom) {
    if (top != INF) {
        return top;
    } else {
        return bottom;
    }
}
int id() {
    return INF;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i=0; i<N; i++) cin >> A[i];
    int Q;
    cin >> Q;

    vector<Node> B(N);
    for (int i=0; i<N; i++) {
        vector<vector<int>> C(4, vector<int> (4, 0));
        C[A[i]-1][A[i]-1] = 1;
        B[i] = Node(C, 1);
    }
    lazy_segtree<Node, op, e, int, mapping, composition, id> seg(B);
    while (Q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l --;
        r --;
        if (t == 1) {
            Node n = seg.prod(l, r+1);
            int ans = 0;
            for (int i=0; i<4; i++) {
                for (int j=i; j<4; j++) {
                    ans = max(ans, n.L[i][j]);
                }
            }
            cout << ans << endl;
        } else {
            int x;
            cin >> x;
            seg.apply(l, r+1, x);
        }
    }
}
0