No.2697 Range LIS Query
タグ : / 解いたユーザー数 69
作問者 :
KowerKoint2010
hibit_at
👑 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もしくは右上の雲マークをクリックしてアカウントを作成してください。