問題一覧 > 通常問題

No.2697 Range LIS Query

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 69
作問者 : nouka28 / テスター : KowerKoint2010 hibit_at 👑 seekworser isee
お気に入りにしたユーザー ProblemId : 10622 / 自分の提出
問題文最終更新日: 2024-03-21 21:50:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 423 (Asakatsu Presents 3) (順位表) の他の問題:

Story

hibit, an evil doctor, is studying longest increasing subsequences for the sake of his ambitions.
After a while, hibit came across the following problem, but since it was already late at night, he decided to go to bed to prepare for tomorrow's virtual contest "Asakatsu".
You, hibit's rival, have decided to solve the problem before he wakes up.

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots ,A_n)$ of length $N$ consisting of integers between $1$ and $4$, inclusive.

You are given $Q$ queries; process them in order. There are the following $2$ types of queries.

  • 1 l r : For the contiguous subarray $B=(A_l,A_{l+1},\dots ,A_r)$ of $A$, print the length of a longest non-decreasing subsequence of $B$.
  • 2 l r x : For each integer $i$ satisfying $l\leq i \leq r$, update $A_i$ to $x$.

Notes

  • A subsequence of a sequence $X$ : a sequence obtained by extracting some elements of $X$ and arranging them in their original order
  • A contiguous subarray of a sequence $X$ : a sequence obtained by taking only some contiguous segment of $X$ and keeping its order
  • A longest non-decreasing subsequence of a sequence $X$ : a subsequence of maximum length among the non-decreasing subsequences of $X$

Constraints

  • All inputs are integers
  • $1\leq N\leq 10^5$
  • $1\leq A_i\leq 4$
  • $1\leq Q\leq 10^5$
  • For queries of types $1$ , $2$ : $1\leq l\leq r\leq N$
  • For queries of type $2$ : $1\leq x\leq 4$

Input

The input is given from standard input in the following format.
$N$
$A_1\ A_2\  \dots \ A_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

Each query $query_i\, (1\leq i\leq Q)$ is given in the form

$1$ $l$ $r$

or

$2$ $l$ $r$ $x$

as shown above.

Output

Let $q$ be the number of queries of type $1$. Print $q$ lines. On line $i(1\leq i\leq q)$, print the answer to the $i$-th query of type $1$.

Sample

Sample 1
Input
7
1 2 4 3 2 1 3
3
1 1 7
2 2 4 1
1 3 6
Output
4
3

Initially, $A=(1,2,4,3,2,1,3)$. Processing the queries in order goes as follows.

  • $B=(1,2,4,3,2,1,3)$. $1$ of the longest non-decreasing subsequences of $B$ is $(1,2,2,3)$, whose length is $4$, so print $4$.
  • Update all of $A_2,A_3,A_4$ to $1$. Thus, $A=(1,1,1,1,2,1,3)$.
  • $B=(1,1,2,1)$. $1$ of the longest non-decreasing subsequences of $B$ is $(1,1,2)$, whose length is $3$, so print $3$.
Sample 2
Input
4
4 3 2 1
1
1 1 4
Output
1

Sample 3
Input
17
2 1 3 3 2 3 3 3 4 2 3 2 2 2 1 4 1
15
2 5 17 1
1 8 10
1 11 13
2 2 8 2
2 6 17 2
1 11 17
2 13 17 4
1 9 13
2 6 6 4
2 1 16 4
1 2 5
2 16 16 1
2 3 6 2
1 3 6
1 2 2
Output
3
3
7
5
4
4
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。