Chef Likes Good Sequences SOLUTION
Chef calls a sequence good if it does not contain any two adjacent identical elements.Initially, Chef has a sequence a1,a2,…,aN. He likes to change the sequence every now and then. You should process Q queries. In each query, Chef chooses an index x and changes the x-th element of the sequence to 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.
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and Q.
- The second line contains N space-separated integers a1,a2,…,aN.
- Q lines follow. Each of these lines contains two space-separated integers x and y describing a query.
After each query, print a single line containing one integer ― the length of the longest good subsequence.
1≤ai≤109 for each valid i
Subtask #1 (35 points): Q=1
Subtask #2 (65 points): original constraints
1 1 2 5 2
SOLUTION AFTER CONTEST
October Lunchtime 2020 CodeChef SOLUTIONS