链接：http://acm.hdu.edu.cn/showproblem.php?pid=6406
思路：
暴力，预处理三个前缀和：【1,n】桃子会被摘掉，1到当前点的最大值，1到当前点被摘掉的桃子的数量，然后我们枚举修改p点造成的所有影响，：
1，假如新输入的点比原先的点的值更大，那么我们对修改后p这个点的值和【1,p-1】的最大值关系进行分析，也就是分析前半段的影响：（1）如果p点大于1-p-1的最大值的时候我们直接利用前缀和O(1)得到【1，p-1】有多少个桃子被摘掉，然后加上当前这个。（2）如果p点小于等于【1，p-1】的最大值时，对前半段和后半段都不会造成影响，直接输出预处理的到的【1，n】的值就好了；然后我们分析后半段的影响：（1）如果p点大于【1,p-1】的最大值，那么后半段中只有被摘掉的桃子会受到影响，我们直接二分找到【p+1,n】中被摘掉的桃子的值大于被修改后的值c的下标，减一下，就得出了，后半段会被摘掉的桃子中有几个在p点被修改后依旧需要摘掉，将后半段的值与前半段的值加起来就好了。（2）如果p点小于等于【1,p-1】的最大值，那么后半段不造成影响，
2.假如新输入的点小于等于原先的点值，依旧对修改后p这个点的值和【1,p-1】的最大值进行分析：先分析前半段的影响：（1）如果p点大于1-p-1的最大值的时候我们直接利用前缀和O(1)得到【1，p-1】有多少个桃子被摘掉，然后加上当前这个。（2）如果p点小于等于【1,p-1】的最大值，那么这个点依旧对前半段不造成影响，前半段的值等于【1,p-1】中被摘掉的桃子的数量，
接下来就是最难得后半段的讨论：
之前处理这里思路被卡了很久：（1）如果p点大于1-p-1的最大值
因为当前点变小了，对后面点造成的影响就是会摘掉一些原先不会被摘的桃子，那么怎么确定这些桃子的具体是那些呢？ 实际上我们可以推出，这些多摘的桃子都是在1到当前坐标中只小于p的数，因为这些数是当p变小了才多出来的，那么他们在1到当前点肯定是只小于p点，那么我们把它加到前一维为p的vecvector数组里，至于怎么找到这些值，我们只要多维护一个第二大值就可以了，这些第二大值就是有可能会多摘的桃子。当p点为原先会被摘的桃子时我们对存在v[p]里的值进行二分找到比p值修改后大的那些值，也就是后半段新增的值，再加上原先就要摘得值。
（2） 如果小于等于的话，依旧不造成影响，直接去前缀和就好了
3，假设输入的点和原来的点值一样，直接前缀和取
这样一共是五种主要情况： 两种用二分O(logn)，另外三种直接前缀和O(1)，稍微计算便可知不会超时。最后跑了405ms，题目给了2000mS,算跑的很快的了， 就是实现有点复杂，应该还有更好的解法，不过比赛的时候没想那么多，直接暴力莽过去了，还好过了要不改代码要改到吐。。QAQ
实现代码：
#include<bits/stdc++.h> using namespace std; const int M = 1e5+10; struct node{ int id,val; }; vector<int>v[M]; int a[M],ans[M],maxx[M],b[M],arr[M]; int main() { int t,n,q,p,c; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i = 1;i <= n;i ++){ scanf("%d",&a[i]); } node mx,mx1; mx.val = 0; mx1.val = 0,mx.id = 0,mx1.id = 0; int cnt = 0,num = 0; maxx[0] = 0; for(int i = 1;i <= n;i ++){ if(mx.val < a[i]){ mx1.val = mx.val; mx1.id = mx.id; mx.val = a[i]; mx.id = i; b[cnt++] = a[i]; num++; } else if(mx1.val < a[i]){ mx1.val = a[i]; mx1.id = i; v[mx.id].push_back(a[i]); } maxx[i] = mx.val; ans[i] = num; } while(q--){ scanf("%d%d",&p,&c); int sum = 0; if(c > a[p]){ if(c > maxx[p-1]){ sum ++; sum += ans[p-1]; int kk = upper_bound(b,b+cnt,c) - b; if(kk != cnt) sum += cnt-kk; } else sum = ans[n]; } else if(c == a[p]) sum = ans[n]; else{ if(c > maxx[p-1]) sum++,sum += ans[p-1]; else sum += ans[p-1]; if(a[p] == maxx[p]){ int kk = upper_bound(v[p].begin(),v[p].end(),c)-v[p].begin(); sum += v[p].size() - kk; int kk1 = upper_bound(b,b+cnt,a[p]) - b; if(kk1 != cnt) sum += cnt-kk1; } else sum = ans[n]; } printf("%d\n",sum); } for(int i = 0;i <= n;i ++){ maxx[i] = 0; ans[i] = 0; v[i].clear(); } for(int i = 0;i <= cnt;i ++) b[i] = 0; } return 0; }
hdu 6406 Taotao Picks Apples （2018 Multi-University Training Contest 8 1010）（二分，前缀和）