結果
問題 | No.2697 Range LIS Query |
ユーザー |
|
提出日時 | 2024-02-03 16:24:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 569 ms / 10,000 ms |
コード長 | 1,219 bytes |
コンパイル時間 | 4,478 ms |
コンパイル使用メモリ | 261,488 KB |
最終ジャッジ日時 | 2025-02-19 01:11:12 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; const int K=4; struct S{ int length; int d[K][K]={0}; S(int length=0):length(length){} }; void expand(S &x){ for(int l=1;l<K;l++){ for(int i=0;i+l<K;i++){ x.d[i][i+l]=max(x.d[i][i+l],x.d[i+1][i+l]); x.d[i][i+l]=max(x.d[i][i+l],x.d[i][i+l-1]); } } } S op(S x,S y){ expand(x);expand(y); S z; for(int i=0;i<K;i++){ for(int j=i;j<K;j++){ for(int k=0;k<=i;k++){ z.d[k][j]=max(z.d[k][j],x.d[k][i]+y.d[i][j]); } } } z.length=x.length+y.length; return z; } S e(){ return S(); } S mapping(int f,S x){ if(f==-1)return x; x=S(x.length);x.d[f][f]=x.length;return x; } int composition(int f,int g){return (f==-1)?g:f;} int id(){return -1;} int main(){ int n;cin>>n; vector<int> a(n);for(auto &e:a){cin>>e;e--;} vector<S> s(n); for(int i=0;i<n;i++){ s[i].length=1;s[i].d[a[i]][a[i]]=1; } lazy_segtree<S,op,e,int,mapping,composition,id> seg(s); int q;cin>>q; while(q--){ int type;cin>>type; if(type==1){ int l,r;cin>>l>>r;l--; auto res=seg.prod(l,r);expand(res); cout<<res.d[0][K-1]<<endl; } if(type==2){ int l,r,x;cin>>l>>r>>x;l--;x--; seg.apply(l,r,x); } } }