Coloring a Number Line

Problem Statement

Coloring a Number Line A number line covers the coordinates 0, 1, ..., length - 1 . Every coordinate starts with color 0 , which means "not colored yet". You are given q queries. The i -th query is a pair coord color : paint coordinate coord with color , overwriting whatever color that coordinate had before. After each query, count the adjacent pairs of coordinates that share the same color , that is the number of coordinates j with 0 <= j <= length - 2 such that color[j] == color[j + 1] and that shared color is not 0 . Report that count for every query, in order. Input Format The first line contains the integer length . The second line contains the integer q , the number of queries. Each of the next q lines contains two integers coord and color — one query. Output Format Print q integers separated by single spaces on one line: the i -th of them is the number of adjacent same-color pairs after the i -th query has been applied. Constraints 1 <= length <= 10^9 1 <= q <=