标签: 线段树优化建图

「CodeForces 1158C」Permutation recovery

Vasya has written some permutation 𝑝1,𝑝2,…,𝑝𝑛 of integers from 1 to 𝑛, so for all 1≤𝑖≤𝑛 it is true that 1≤𝑝𝑖≤𝑛 and all 𝑝1,𝑝2,…,𝑝𝑛 are different. After that he wrote 𝑛 numbers 𝑛𝑒𝑥𝑡1,𝑛𝑒𝑥𝑡2,…,𝑛𝑒𝑥𝑡𝑛. The number 𝑛𝑒𝑥𝑡𝑖 is equal to the minimal index 𝑖<𝑗≤𝑛, such that 𝑝𝑗>𝑝𝑖. If there is no such 𝑗 let's let's define as 𝑛𝑒𝑥𝑡𝑖=𝑛+1.