2018 Multi-University Training Contest 8 Taotao Picks Apples[离线+单调队列+二分]

题目大意：给你n个数，然后你可以从左到右每次选择最大的，总共可以选k个数，然后现在给你q次修改，每次修改某个位置的某个数，问你现在还能选几个数

分析：这个题目有点类似前几场做过的一个单调队列的题，我们如果倒过来把所有的数放在一个单调递减的队列里面，那么这个队列里的数就是由第i个数开始能够选的个数，那么我们只要离线把所有的询问按照修改的位置从大到小排序，相同的情况，按照修改的数由小到大排序，那么我们只要对于每次询问，都算一下按照修改的数开头（其实并不完全是按照修改的数开头，如果前面的最大值比当前修改的值来的大，应该是按照前面的最大值开头）需要选多少个，这里只要二分这个数在队列中的位置即可。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn = 1e5 + 50;
typedef long long ll;
int mod = 1e9 + 7;
int h[maxn];
int que[maxn];
int fir[maxn];
int mt[maxn];
struct node
{
    int id;
    int num;
    int ans;
    int org;
};
bool cmp1(node a, node b)
{
    if (a.id == b.id)
    {
        return a.num<b.num;
    }
    else return a.id>b.id;
}
bool cmp2(node a, node b)
{
    return a.org<b.org;
}
node a[maxn];
int cnt;
bool check(int mid, int q)
{
    if (mid>cnt)return true;
    if (que[mid] <= q)return true;
    else return false;
}
int bi_search(int q)
{
    int l = 0, r = maxn;
    while (l <= r)
    {
        int mid = (r + l) / 2;
        if (check(mid, q))r = mid - 1;
        else l = mid + 1;
    }
    return l - 1;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        cl(que); cl(a); cl(h); cl(fir);
        scanf("%d%d", &n, &m);
        int r = 0;
        for (int i = 1; i <= n; i++)
        {
            fir[i] = fir[i - 1];
            mt[i] = mt[i - 1];
            scanf("%d", &h[i]);
            if (h[i]>r)
            {
                fir[i]++;
                r = h[i];
                mt[i] = r;
            }
        }
        for (int i = 1; i <= m; i++)
        {
            node tmp;
            scanf("%d%d", &tmp.id, &tmp.num);
            tmp.org = i;
            a[i] = tmp;
        }
        sort(a + 1, a + 1 + m, cmp1);
        int pre = 1;
        cnt = 0;
        int j = 1;
        que[0] = 0x3f3f3f3f;
        for (int i = n; i >= 1; i--)
        {
            while (a[j].id == i)
            {
                int q = a[j].num;
                if (q >= que[1]) { a[j].ans = 1; j++; continue; }
                if (q < mt[i-1]) { q = mt[i - 1]; a[j].num = q; }
                if (q >= que[1]) { a[j].ans = 1; j++; continue; }
                int t = bi_search(q);
                a[j].ans = t + 1;
                j++;
            }
            while (cnt != 0 && que[cnt] <= h[i])
            {
                cnt--;
            }
            que[++cnt] = h[i];

        }
        sort(a + 1, a + 1 + m, cmp2);
        for (int i = 1; i <= m; i++)
        {
            int j = a[i].id;
            int k = a[i].num;
            if (k <= mt[j - 1]) printf("%d\n", fir[j - 1] + a[i].ans - 1);
            else printf("%d\n", fir[j - 1] + a[i].ans);
        }
    }
    return 0;
}