結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 2024-04-29 22:33:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 351 ms / 10,000 ms |
コード長 | 3,050 bytes |
コンパイル時間 | 717 ms |
コンパイル使用メモリ | 62,016 KB |
実行使用メモリ | 20,748 KB |
最終ジャッジ日時 | 2024-11-19 07:19:20 |
合計ジャッジ時間 | 6,201 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
/* -*- coding: utf-8 -*-** 2697.cc: No.2697 Range LIS Query - yukicoder*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;/* constant */const int MAX_N = 100000;const int K = 4;/* typedef */struct Elm {int cs[K][K];Elm(): cs() {}Elm(int x): cs() { cs[x][x] = 1; }Elm(int x, int c): cs() { cs[x][x] = c; }Elm operator+(const Elm &e) const {Elm r;for (int i = 0; i < K; i++)for (int j = i; j < K; j++) {int ss[K + 1]; ss[j + 1] = 0;for (int k = j; k >= i; k--) ss[k] = max(ss[k + 1], e.cs[k][j]);r.cs[i][j] = 0;for (int k = i; k <= j; k++)r.cs[i][j] = max(r.cs[i][j], cs[i][k] + ss[k]);}return r;}int val() const {int maxc = 0;for (int i = 0; i < K; i++)for (int j = i; j < K; j++)maxc = max(maxc, cs[i][j]);return maxc;}};struct SegTreeSumDelay {using T = Elm;int e2;vector<T> nodes;T defv;vector<int> dls;SegTreeSumDelay() {}void init(int n, T _defv) {defv = _defv;for (e2 = 1; e2 < n; e2 <<= 1);nodes.assign(e2 * 2, defv);dls.assign(e2 * 2, -1);}T &geti(int i) { return nodes[e2 - 1 + i]; }void seti(int i, T v) { geti(i) = v; }void setall() {for (int j = e2 - 2; j >= 0; j--)nodes[j] = nodes[j * 2 + 1] + nodes[j * 2 + 2];}void __update(int k, int l) {if (dls[k] >= 0) {int k0 = k * 2 + 1, k1 = k0 + 1, hl = l / 2;nodes[k0] = Elm(dls[k], hl), nodes[k1] = Elm(dls[k], hl);dls[k0] = dls[k1] = dls[k];dls[k] = -1;}}void set_range(int r0, int r1, int v, int k, int i0, int i1) {if (r1 <= i0 || i1 <= r0) return;if (r0 <= i0 && i1 <= r1) {nodes[k] = Elm(v, i1 - i0);dls[k] = v;return;}__update(k, i1 - i0);int im = (i0 + i1) / 2;int k0 = k * 2 + 1, k1 = k0 + 1;set_range(r0, r1, v, k0, i0, im);set_range(r0, r1, v, k1, im, i1);nodes[k] = nodes[k0] + nodes[k1];}void set_range(int r0, int r1, int v) { set_range(r0, r1, v, 0, 0, e2); }T sum_range(int r0, int r1, int k, int i0, int i1) {if (r1 <= i0 || i1 <= r0) return defv;if (r0 <= i0 && i1 <= r1) return nodes[k];__update(k, i1 - i0);int im = (i0 + i1) / 2;T v0 = sum_range(r0, r1, k * 2 + 1, i0, im);T v1 = sum_range(r0, r1, k * 2 + 2, im, i1);return v0 + v1;}T sum_range(int r0, int r1) { return sum_range(r0, r1, 0, 0, e2); }};/* global variables */int as[MAX_N];SegTreeSumDelay st;/* subroutines *//* main */int main() {int n;scanf("%d" ,&n);for (int i = 0; i < n; i++) scanf("%d", as + i), as[i]--;st.init(n, Elm());for (int i = 0; i < n; i++) st.seti(i, Elm(as[i]));st.setall();int qn;scanf("%d", &qn);while (qn--) {int op, l, r;scanf("%d%d%d", &op, &l, &r); l--;if (op == 1) {auto e = st.sum_range(l, r);printf("%d\n", e.val());}else {int x;scanf("%d", &x); x--;st.set_range(l, r, x);}}return 0;}