結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:02:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 452 ms / 10,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 4,796 ms |
コンパイル使用メモリ | 269,376 KB |
実行使用メモリ | 28,144 KB |
最終ジャッジ日時 | 2024-09-30 11:33:42 |
合計ジャッジ時間 | 10,288 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001using A = pair<array<array<int,4>,4>,int>;A e(){A ret;rep(i,4){for(int j=0;j<4;j++)ret.first[i][j] = 0;}ret.second = 0;return ret;}A op(A a,A b){A ret = e();rep(i,4){for(int j=i;j<4;j++){for(int k=j;k<4;k++){for(int l=k;l<4;l++){ret.first[i][l] = max(ret.first[i][l],a.first[i][j] + b.first[k][l]);}}}}ret.second = a.second + b.second;return ret;}A mapping(int a,A b){if(a==-1)return b;rep(i,4){rep(j,4)b.first[i][j] = 0;}b.first[a][a] =b.second;return b;}int composition(int a,int b){if(a==-1)return b;return a;}int id(){return -1;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;cin>>n;vector<int> a(n);rep(i,n){cin>>a[i];a[i]--;}lazy_segtree<A,op,e,int,mapping,composition,id> seg;{vector<A> ts;rep(i,n){A temp = e();temp.first[a[i]][a[i]] = 1;temp.second = 1;ts.push_back(temp);}seg = lazy_segtree<A,op,e,int,mapping,composition,id>(ts);}int q;cin>>q;rep(_,q){int t;cin>>t;int x,y;cin>>x>>y;if(t==1){auto ret = seg.prod(x-1,y);int ans = 0;rep(i,4){rep(j,4){ans = max(ans,ret.first[i][j]);}}cout<<ans<<endl;}else{int z;cin>>z;seg.apply(x-1,y,z-1);}}return 0;}