CodeForces - 650D：Zip-line （LIS & DP）
Vasya has decided to build a zip-line on trees of a nearby forest. He wants the line to be as long as possible but he doesn't remember exactly the heights of all trees in the forest. He is sure that he remembers correct heights of all trees except, possibly, one of them.
It is known that the forest consists ofntrees staying in a row numbered from left to right with integers from1ton. According to Vasya, the height of thei-th tree is equal tohi. The zip-line of lengthkshould hang overk(1 ≤ k ≤ n) treesi1, i2, ..., ik(i1 < i2 < ... < ik) such that their heights form an increasing sequence, that ishi1 < hi2 < ... < hik.
Petya had been in this forest together with Vasya, and he now hasqassumptions about the mistake in Vasya's sequenceh. Hisi-th assumption consists of two integersaiandbiindicating that, according to Petya, the height of the tree numberedaiis actually equal tobi. Note that Petya's assumptions areindependentfrom each other.
Your task is to find the maximum length of a zip-line that can be built over the trees under each of theqassumptions.
In this problem the length of a zip line is considered equal to the number of trees that form this zip-line.
Input
The first line of the input contains two integersnandm(1 ≤ n, m ≤ 400 000)— the number of the trees in the forest and the number of Petya's assumptions, respectively.
The following line containsnintegershi(1 ≤ hi ≤ 109)— the heights of trees according to Vasya.
Each of the followingmlines contains two integersaiandbi(1 ≤ ai ≤ n,1 ≤ bi ≤ 109).
Output
For each of the Petya's assumptions output one integer, indicating the maximum length of a zip-line that can be built under this assumption.
Examples
4 4
1 2 3 4
1 1
1 4
4 3
4 5
4
3
3
4
4 2
1 3 2 6
3 5
2 4
4
3
题意：给定一个数组，Q次询问，询问之间彼此独立。每次询问改动一个数，问改动后的LIS。
思路：同今年南京（湘潭）的邀请赛J题，当时思路差不多对了，但是想复杂了，我和陈队花了一个半小时还是写WA了。注意到新LIS和原来的LIS最多相差1。也就是max-1，max，max+1三种情况，那么我们分两步去验证即可：
第一步，考虑没了原来的值：假设原来的LIS一定经过更改点，那么先把ans赋值为max-1；否则赋值ans为max。
第二步，考虑有了新来的值：即用到新的值，那么预处理的时候从前向后后从后向前扫，两遍预处理完，ans=max(ans,f[i]+g[i]-1)。
第二步用线段树或者树状数组即可搞定，常规操作。
第一步，其实也不难想，当时就是这里想复杂了。我们得到LISmax，然后f[i]表示以i为结束的LIS，g[i]表示以i为起点的LIS。如果f[i]+g[i]-1==max，那么种数那么cnt[f[i]]++; 讨论替换i点时，如果cnt[f[i]]==1，则说明原来的LIS必定经过i点。
优质内容筛选与推荐>>1、SOA体系结构之基础培训教程-大纲篇
2、【React 资料备份】React v16.3之后的生命周期
3、UTF8的编码规则
4、repair grub in Ubuntu
5、Hdu 1016 Prime Ring Problem (素数环经典dfs)