結果
| 問題 |
No.2697 Range LIS Query
|
| コンテスト | |
| ユーザー |
 ゆにぽけ
|
| 提出日時 | 2024-03-22 22:27:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 425 ms / 10,000 ms |
| コード長 | 8,364 bytes |
| コンパイル時間 | 1,794 ms |
| コンパイル使用メモリ | 135,312 KB |
| 最終ジャッジ日時 | 2025-02-20 11:58:29 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
template<class T,T (*op)(T,T),T (*e)()> struct segtree
{
private:
int size,N;
vector<T> node;
public:
segtree(int N = 0) : segtree(vector<T>(N,e())) {}
segtree(const vector<T> &V)
{
N = (int)V.size();
size = 1;
while(size < N)
{
size <<= 1;
}
node.assign(2 * size,e());
for(int i = 0;i < N;i++)
{
node[i + size] = V[i];
}
for(int i = size - 1;i >= 1;i--)
{
node[i] = op(node[2 * i],node[2 * i + 1]);
}
}
void replace(int pos,T x)
{
func_update(pos,x,[](T u,T v){return u = v;});
}
void add(int pos,T x)
{
func_update(pos,x,[](T u,T v){return u + v;});
}
void func_update(int pos,T x)
{
func_update(pos,x,op);
}
void func_update(int pos,T x,T (*func)(T,T))
{
assert(0 <= pos && pos < N);
pos += size;
node[pos] = func(node[pos],x);
while(pos >> 1)
{
pos >>= 1;
node[pos] = op(node[2 * pos],node[2 * pos + 1]);
}
}
T operator[](int pos)
{
assert(0 <= pos && pos < N);
return node[pos + size];
}
int get_log()
{
int res = 0;
while(1 << res < size)
{
res++;
}
assert((1 << res) == size);
return res;
}
vector<vector<T>> tree_list()
{
vector<vector<T>> res;
int log = get_log();
res.reserve(log + 1);
for(int i = 0;i <= log;i++)
{
int L = 1 << log,R = L << 1;
vector<T> cur(node.begin() + L,node.begin() + R);
res.push_back(cur);
}
return res;
}
//suppose that class T has ostream &operator<<
void print(int k)
{
assert(0 <= k && k <= get_log());
int L = 1 << k,R = L << 1;
for(int i = L;i < R;i++)
{
cerr << node[i] << (i + 1 == R ? "\n":" ");
}
}
void print()
{
int log = get_log();
for(int k = 0;k <= log;k++)
{
int L = 1 << k,R = L << 1;
const string unit((1 << (log - k)) - 1,' ');
for(int i = L;i < R;i++)
{
if(i == L)
{
cerr << unit;
}
cerr << node[i];
if(i + 1 < R)
{
cerr << unit << unit << ' ';
}
else
{
cerr << unit;
}
}
cerr << "\n";
}
}
T prod(int l,int r)
{
assert(0 <= l && l <= r && r <= N);
T L = e(),R = e();
l += size,r += size;
while(l < r)
{
if(l & 1)
{
L = op(L,node[l++]);
}
if(r & 1)
{
R = op(node[--r],R);
}
l >>= 1,r >>= 1;
}
return op(L,R);
}
T prod()
{
return node[1];
}
template<class F> int max_right(int l,F f)
{
assert(0 <= l && l <= N);
assert(f(e()));
if(l == N)
{
return N;
}
l += size;
T val = e();
do
{
while(!(l & 1))
{
l >>= 1;
}
if(!f(op(val,node[l])))
{
while(l < size)
{
l <<= 1;
if(f(op(val,node[l])))
{
val = op(val,node[l++]);
}
}
return l - size;
}
val = op(val,node[l++]);
} while((l & -l) != l);
return N;
}
template<class F> int min_left(int r,F f)
{
assert(0 <= r && r <= N);
assert(f(e()));
if(r == 0)
{
return 0;
}
r += size;
T val = e();
do
{
r--;
while(r > 1 && (r & 1))
{
r >>= 1;
}
if(!f(op(node[r],val)))
{
while(r < size)
{
r <<= 1;
r++;
if(f(op(node[r],val)))
{
val = op(node[r--],val);
}
}
return r + 1 - size;
}
val = op(node[r],val);
} while((r & -r) != r);
return 0;
}
};
template<class T,T (*op)(T,T),T e(),class F,T (*mapping)(F,T),F (*composition)(F,F),F id()> struct LazySegmentTree
{
private:
vector<T> node;
vector<F> lazy;
int siz,log;
void map_and_comp(F f,int u)
{
node[u] = mapping(f,node[u]);
if(u < siz) lazy[u] = composition(f,lazy[u]);
}
void propagate(int u)
{
assert(0 <= u && u < siz);
map_and_comp(lazy[u],2*u);
map_and_comp(lazy[u],2*u+1);
lazy[u] = id();
}
void recalculate(int u) {node[u] = op(node[2*u],node[2*u+1]);}
public:
LazySegmentTree(int n = 0) : LazySegmentTree(vector<T>(n,e())) {}
LazySegmentTree(const vector<T> &V)
{
siz = 1;
log = 0;
while(siz < (int)V.size()) siz <<= 1,log++;
node.assign(2*siz,e());
lazy.assign(siz,id());
for(int i = 0;i < (int)V.size();i++) node[i+siz] = V[i];
for(int i = siz-1;i >= 1;i--) recalculate(i);
}
void fill(T x,int l = 0,int r = -1) {if(r < 0){r = siz;} for(int i = l;i < r;i++) replace(i,x);}
void clear() {fill(e());}
void replace(int pos,T x) {func_update(pos,x,[](T u,T v){return u = v;});}
void add(int pos,T x) {func_update(pos,x,[](T u,T v){return u + v;});}
void func_update(int pos,T x,T (*func)(T,T))
{
assert(0 <= pos && pos < siz);
pos += siz;
for(int i = log;i >= 1;i--) propagate(pos >> i);
node[pos] = func(node[pos],x);
for(int i = 1;i <= log;i++) recalculate(pos >> i);
}
T operator[](int pos)
{
assert(0 <= pos && pos < siz);
pos += siz;
for(int i = log;i >= 1;i--) propagate(pos >> i);
return node[pos];
}
void apply(int pos,F f)
{
assert(0 <= pos && pos < siz);
pos += siz;
for(int i = log;i >= 1;i--) propagate(pos >> i);
node[pos] = mapping(f,node[pos]);
for(int i = 1;i <= log;i++) recalculate(pos >> i);
}
void apply(int l,int r,F f)
{
assert(0 <= l && l <= r && r <= siz);
if(l == r) return;
l += siz;
r += siz;
int l0 = l/(l & -l);
int r0 = r/(r & -r);
for(int i = log;i >= 1;i--) propagate(l0 >> i);
for(int i = log;i >= 1;i--) propagate((r0-1) >> i);
while(l < r)
{
if(l & 1) map_and_comp(f,l++);
if(r & 1) map_and_comp(f,--r);
l >>= 1;
r >>= 1;
}
for(int i = 1;i <= log;i++) recalculate(l0 >> i);
for(int i = 1;i <= log;i++) recalculate((r0-1) >> i);
}
T prod() {return node[1];}
T prod(int l,int r)
{
assert(0 <= l && l <= r && r <= siz);
l += siz;
r += siz;
int l0 = l/(l & -l);
int r0 = r/(r & -r);
for(int i = log;i >= 1;i--) propagate(l0 >> i);
for(int i = log;i >= 1;i--) propagate((r0-1) >> i);
T Lval = e(),Rval = e();
while(l < r)
{
if(l & 1) Lval = op(Lval,node[l++]);
if(r & 1) Rval = op(node[--r],Rval);
l >>= 1;
r >>= 1;
}
return op(Lval,Rval);
}
};
struct dat
{
int len;
int dp[4][4]{};
};
dat op(dat a,dat b)
{
dat x;
x.len = a.len + b.len;
for(int i = 0;i < 4;i++)
{
for(int j = i;j < 4;j++)
{
for(int k = j;k < 4;k++)
{
for(int l = k;l < 4;l++)
{
x.dp[i][l] = max(x.dp[i][l],a.dp[i][j] + b.dp[k][l]);
}
}
x.dp[i][j] = max(x.dp[i][j],a.dp[i][j]);
x.dp[i][j] = max(x.dp[i][j],b.dp[i][j]);
}
}
return x;
}
dat e()
{
dat x;
x.len = 0;
for(int i = 0;i < 4;i++)
{
for(int j = 0;j < 4;j++)
{
x.dp[i][j] = -(int)1e9;
}
}
return x;
}
dat mp(int f,dat x)
{
if(f != -1)
{
for(int i = 0;i < 4;i++)
{
for(int j = i;j < 4;j++)
{
x.dp[i][j] = 0;
}
}
x.dp[f][f] = x.len;
}
return x;
}
int cp(int f,int g)
{
if(f != -1)
{
swap(g,f);
}
return g;
}
int id()
{
return -1;
}
void Main()
{
int N;
cin >> N;
vector<dat> init(N);
for(int i = 0;i < N;i++)
{
int a;
cin >> a;
a--;
init[i].len = 1;
init[i].dp[a][a] = 1;
}
LazySegmentTree<dat,op,e,int,mp,cp,id> seg(init);
int Q;
cin >> Q;
for(;Q--;)
{
int t;
cin >> t;
if(t == 1)
{
int l,r;
cin >> l >> r;
l--;
dat x = seg.prod(l,r);
int ans = 0;
for(int i = 0;i < 4;i++)
{
for(int j = i;j < 4;j++)
{
ans = max(ans,x.dp[i][j]);
}
}
cout << ans << "\n";
}
else
{
int l,r,x;
cin >> l >> r >> x;
x--; l--;
seg.apply(l,r,x);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
/* cin >> tt; */
while(tt--) Main();
}