結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 1000000000000000001

using 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;
}
0