text: Queries to find longest subsequence having no similar adjacent elements with updates | C ++ program for the above approach ; Traverse the array arr [ ] ; If previous element is not same as current element ; Traverse the queries ; Replace element at index x with y ; Recalculate for index x ; Subtract contribution of element at index x ; Add contribution of y ; Recalculate for index x + 1 ; Subtract contribution of element at index x + 1 ; Adds contribution of y ; Replace the element ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void longestSubsequence ( int N , int Q , int arr [ ] , int Queries [ ] [ 2 ] ) { int count = 1 ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] != arr [ i - 1 ] ) { count += 1 ; } } for ( int i = 0 ; i < Q ; i ++ ) { int x = Queries [ i ] [ 0 ] ; int y = Queries [ i ] [ 1 ] ; if ( x > 1 ) { if ( arr [ x - 1 ] != arr [ x - 2 ] ) { count -= 1 ; } if ( arr [ x - 2 ] != y ) { count += 1 ; } } if ( x < N ) { if ( arr [ x ] != arr [ x - 1 ] ) { count -= 1 ; } if ( y != arr [ x ] ) { count += 1 ; } } cout << count << ' ▁ ' ; arr [ x - 1 ] = y ; } } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 5 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int Q = 2 ; int Queries [ Q ] [ 2 ] = { { 1 , 3 } , { 4 , 2 } } ; longestSubsequence ( N , Q , arr , Queries ) ; return 0 ; }