I've a big problem: Given N number a[1],a[2],..,a[N] and M queries. (N,M <= 10^5)

Each query, change a[v] to x, and find the maximum sum subsequence such that no two elements are adjacent.

Example: a = {1,1,1,1,1,1}

• First query, change a[5] to 3, thus a = {1,1,1,1,3,1} -> the answer is 5 (choose a[1],a[3],a[5])

• Second query, change a[2] to 4, thus a = {1,4,1,1,3,1} -> the answer is 7 (choose a[2],a[5])

• And so on..

I think use DP to solve this problem, but the complexity is O(N*M) can't run with N,M <= 10^5.

Could you help me? Thanks all.

UPD: I've solved this problem, thanks for all.