Chef Likes Good Sequences Codechef October Lunchtime Problem solution -
Chef calls a sequence good if it does not contain any two adjacent identical elements.
Initially, Chef has a sequence . He likes to change the sequence every now and then. You should process queries. In each query, Chef chooses an index and changes the -th element of the sequence to . 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 denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains two space-separated integers and .
- The second line contains space-separated integers .
- lines follow. Each of these lines contains two space-separated integers and describing a query.
Output
After each query, print a single line containing one integer ― the length of the longest good subsequence.
Constraints
- for each valid
Subtasks
Subtask #1 (35 points):
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.
- Case 1 : () and (), then answer will increase by as it will make segment into segments.
- Case 2 : () and (), then the answer will increase by as earlier and will introduce an extra segment. If then we will reduce the answer by as earlier we added as changing to increased the segment count but now it will be merged with previous segment. Example : let and , so If answer will increase by , and if then there will no change to the answer.
- Case 3 : () and (), similar to above case, we will increase the answer by . if then we will reduce the answer by .
- Case 4 : () and (), then if we will reduce answer by . if we will reduce answer by .(Note that you might reduce the answer by when ).
Comments
Post a Comment