HDU Taotao Picks Apples 【二分】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6406

先离线记录从左到右的单调递增数列，记为 h[]

下面分几种情况：

修改的点x不在h里面：

1，值减少，答案不变；

2，值增加，二分h数组，答案减去点x右端比修改值小或者等于的个数。

修改的点x在h里面：

1，值减少；

(1) x的值小于或者等于左端的值，答案加上x和x右端之间的最小值大于x左端值的单调递增个数并且减去1 (减去x)

(2) x值大于左端的值，和上面一样，只是不用减1

2，值增加； 二分h数组，答案减去右端比修改值小或者等于的个数。

ps：h数列两端的单调递增数列要另外离线求出来。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int Maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const long long LINF = 1e18;

int num[Maxn], h[Maxn], a[Maxn];
vector<int> x[Maxn];

int main(void)
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
        int cnt = 0;
        num[cnt] = 0; h[cnt] = a[0]; cnt++;
        for(int i = 1; i < n; ++i) {
            if(a[i] > h[cnt-1]) {
                num[cnt] = i; h[cnt] = a[i];
                cnt++;
            }
        }
        num[cnt] = n;
        for(int i = 0; i <= n; ++i) x[i].clear();
        for(int i = 0; i < cnt; ++i) {
            int ct = 0;
            for(int j = num[i]+1; j < num[i+1]; ++j) {
                if(x[i].size() == 0 || x[i][ct-1] < a[j]) {
                    x[i].push_back(a[j]);
                    ct++;
                }
            }
        }

        int p, val;
        while(m--) {
            scanf("%d%d", &p, &val);
            p--;
            int pp = lower_bound(num, num+cnt, p)-num, ans = cnt;

            if(pp < cnt && num[pp] == p) {
                if(h[pp] > val) {
                    if(pp > 0 && h[pp-1] >= val)
                            ans += (x[pp].end()-upper_bound(x[pp].begin(), x[pp].end(), h[pp-1])-1);
                    else ans += (x[pp].end()-upper_bound(x[pp].begin(), x[pp].end(), val));
                } else if(h[pp] < val) {
                    int xx = upper_bound(h+pp+1, h+cnt, val)-h;
                    ans -= (xx-pp-1);
                }
            } else {
                if(pp > 0 && h[pp-1] >= val);
                else {
                    int xx = upper_bound(h, h+cnt, val)-h;
                    ans -= (xx-pp);
                    ans++;
                }
            }
            printf("%d\n", ans);
        }
    }
	return 0;
}