CF1572F Stations

There are $ n $ cities in a row numbered from $ 1 $ to $ n $ . The cities will be building broadcasting stations. The station in the $ i $ -th city has height $ h_i $ and range $ w_i $ . It can broadcast information to city $ j $ if the following constraints are met: - $ i \le j \le w_i $ , and - for each $ k $ such that $ i < k \le j $ , the following condition holds: $ h_k < h_i $ . In other words, the station in city $ i $ can broadcast information to city $ j $ if $ j \ge i $ , $ j $ is in the range of $ i $ -th station, and $ i $ is strictly highest on the range from $ i $ to $ j $ (including city $ j $ ).At the beginning, for every city $ i $ , $ h_i = 0 $ and $ w_i = i $ . Then $ q $ events will take place. During $ i $ -th event one of the following will happen: - City $ c_i $ will rebuild its station so that its height will be strictly highest among all stations and $ w_{c_i} $ will be set to $ g_i $ . - Let $ b_j $ be the number of stations that can broadcast information to city $ j $ . Print the sum of $ b_j $ over all $ j $ satisfying $ l_i \le j \le r_i $ . Your task is to react to all events and print answers to all queries.

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 2\cdot10^5 $ ) — number of cities and number of events. Then $ q $ lines follow. The $ i $ -th line begins with an integer $ p_i $ ( $ p_i = 1 $ or $ p_i = 2 $ ). If $ p_i = 1 $ a station will be rebuilt. Then two integers $ c_i $ and $ g_i $ ( $ 1 \le c_i \le g_i \le n $ ) follow — the city in which the station is rebuilt and its new broadcasting range. If $ p_i = 2 $ you are given a query. Then two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) follow — the range of cities in the query.

For each query, print in a single line the sum of $ b_j $ over the given interval.

In the first test case, only station $ 1 $ reaches city $ 1 $ before and after it is rebuilt. In the second test case, after each rebuild, the array $ b $ looks as follows: 1. $ [1, 1, 1, 2, 1] $ ; 2. $ [1, 2, 2, 3, 2] $ ; 3. $ [1, 2, 2, 1, 2] $ ; 4. $ [1, 1, 2, 1, 2] $ ; 5. $ [1, 1, 2, 1, 1] $ .