Chef Likes Good Sequences Codechef October Lunchtime Problem solution

 Chef Likes Good Sequences Codechef October Lunchtime Problem solution -

Lets read the problem statement carefully. 

Problem statement- 

Link-https://www.codechef.com/problems/GSUB

Chef calls a sequence good if it does not contain any two adjacent identical elements.

Initially, Chef has a sequence a1,a2,…,aN$a_1,a_2,\dots ,a_N$. He likes to change the sequence every now and then. You should process Q$Q$ queries. In each query, Chef chooses an index x$x$ and changes the x$x$-th element of the sequence to y$y$. After each query, can you find the length of the longest good subsequence of the current sequence?

Note that the queries are not independent.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and Q$Q$.
• The second line contains N$N$ space-separated integers a1,a2,…,aN$a_1,a_2,\dots ,a_N$.
• Q$Q$ lines follow. Each of these lines contains two space-separated integers x$x$ and y$y$ describing a query.

Output

After each query, print a single line containing one integer ― the length of the longest good subsequence.

Constraints

• 1≤T≤5$1\le T\le 5$
• 1≤N,Q≤105$1\le N,Q\le {10}^5$
• 1≤ai≤109$1\le a_i\le {10}^9$ for each valid i$i$
• 1≤x≤N$1\le x\le N$
• 1≤y≤109$1\le y\le {10}^9$

Subtasks

Subtask #1 (35 points): Q=1$Q=1$

Subtask #2 (65 points): original constraints

Example Input

1
5 2
1 1 2 5 2
1 3
4 2

Example Output

5
3




Solution-

First of all do not confuse with subarray and subsequence. 

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A subarray will always be contiguous but a subsequence need not be contiguous.

It's easy problem follow some simply step-

step 1- Calculate the longest subsequence in the initial array without changes.

Now think that if you made changes at xth position of array it will affect initial length if y!= a[x]

$otherwise\; there\; will\; no\; change\; in\; initial\; length.$

if y!=a[x] there occur some cases  for which initial length may affect. You have to observe these cases and handle initial length accordingly. 

• Case 1 : ($a_x == a_{x-1}$) and ($a_x == a_{x+1}$), then answer will increase by $2$ as it will make $1$ segment into $3$ segments.
• Case 2 : ($a_x \neq a_{x-1}$) and ($a_x == a_{x+1}$), then the answer will increase by $1$ as earlier $a_x == a_{x+1}$ and $y$ will introduce an extra segment. If $y$ $=$ $a_{x-1}$ then we will reduce the answer by $1$ as earlier we added $1$ as changing to $y$ increased the segment count but now it will be merged with previous segment. Example : let $a_x = a_{x+1} = 1$ and $a_{x-1} = 2$, so If $y$ $=$ $3$ answer will increase by $1$, and if $y = 2$ then there will no change to the answer.
• Case 3 : ($a_x == a_{x-1}$) and ($a_x \neq a_{x+1}$), similar to above case, we will increase the answer by $1$. if $y=a_{x+1}$ then we will reduce the answer by $1$.
• Case 4 : ($a_x \neq a_{x-1}$) and ($a_x \neq a_{x+1}$), then if $y=a_{x-1}$ we will reduce answer by $1$. if $y = a_{x+1}$ we will reduce answer by $1$.(Note that you might reduce the answer by $2$ when $y=a_{x-1}=a_{x+1}$).

Must join my telegram channel -https://t.me/competitiveProgrammingDiscussion

Follow my code -