結果
問題 | No.2697 Range LIS Query |
ユーザー |
|
提出日時 | 2024-03-22 23:24:10 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 10,000 ms |
コード長 | 4,410 bytes |
コンパイル時間 | 4,376 ms |
コンパイル使用メモリ | 264,124 KB |
実行使用メモリ | 37,668 KB |
最終ジャッジ日時 | 2024-09-30 12:42:30 |
合計ジャッジ時間 | 7,846 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC target("avx,avx2")#include <bits/stdc++.h>#define INF 1000000001LL#define LNF 1000000000000000001LL#define MOD 998244353LL#define MAX 2001#define long long long#define all(x) x.begin(),x.end()using namespace std;struct Node{int value[4][4] = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};};class SegTree{private:vector<Node> arr;vector<Node> tree;vector<int> lazy;int n;Node trash; //의미없는 값 입력Node merge(Node a, Node b){//여기를 커스텀 구현Node res;for(int i = 0; i<4; i++){for(int j = i; j<4; j++){for(int k=i;k<=j; k++){res.value[i][j] = max(res.value[i][j],a.value[i][k]+b.value[k][j]);}}}return res;}void lazyUpdate(int node, int start, int end){if(lazy[node] == -1)return;for(int x = 0; x<4; x++){for(int y = x; y<4; y++){if(x <= lazy[node] && y >= lazy[node])tree[node].value[x][y] = end-start+1;elsetree[node].value[x][y] = 0;}}if(start != end){lazy[node*2] = lazy[node];lazy[node*2+1] = lazy[node];}lazy[node] = -1;}Node init(int node, int start, int end){if(start == end)return tree[node] = arr[start];int mid = (start+end)/2;return tree[node] = merge(init(node*2,start,mid),init(node*2+1,mid+1,end));}Node query(int node, int start, int end, int left, int right){lazyUpdate(node,start,end);if(start > right || end < left)return trash;if(start >= left && end <= right)return tree[node];int mid = (start+end)/2;return merge(query(node*2,start,mid,left,right),query(node*2+1,mid+1,end,left,right));}Node update(int node, int start, int end, int left, int right, long l){lazyUpdate(node,start,end);if(start > right || end < left)return tree[node];if(start >= left && end <= right){lazy[node] = l;lazyUpdate(node,start,end);return tree[node];}int mid = (start+end)/2;return tree[node]=merge(update(node*2,start,mid,left,right,l),update(node*2+1,mid+1,end,left,right,l));}public:void init(int l){n = l;arr = vector<Node>(n);tree = vector<Node>(4*n);}void init(vector<Node> a){n = a.size();arr = a;tree = vector<Node>(4*n);init(1,0,n-1);}void init(vector<long> a){n = a.size();arr = vector<Node>(n);for(int i = 0; i<n; i++){for(int x = 0; x<4; x++){for(int y = x; y<4; y++){if(x <= a[i] && y >= a[i])arr[i].value[x][y] = 1;}}}tree = vector<Node>(4*n);lazy = vector<int>(4*n,-1);init(1,0,n-1);}long query(int left, int right){if(left > right)swap(left,right);// for(int x = 0; x<4; x++)// {// for(int y = 0; y<4; y++)// {// cout << query(1,0,n-1,left,right).value[x][y] << " ";// }// cout << "\n";// }return query(1,0,n-1,left,right).value[0][3];}void update(int left,int right, long val){update(1,0,n-1,left,right,val);}};int main(){ios_base::sync_with_stdio(0);cin.tie(0);int n;cin >> n;vector<long> arr(n);for(int i = 0; i<n; i++){cin >> arr[i];arr[i]--;}SegTree seg;seg.init(arr);int q;cin >> q;while(q--){int t,l,r;cin >> t >> l >> r;l--;r--;if(t == 1)cout << seg.query(l,r) << "\n";else{int x;cin >> x;seg.update(l,r,x-1);}}return 0;}