hdu 6406 Taotao Picks Apples

【题目链接】

题目意思

给你一个序列，从第一个数字开始，当这个数字大于我之前找到的最大值时，（一定）取这个数字并更新最大值，每次询问给两个数字p,q，将a[p]的值修改为q，问每次单点修改后最多可以取多少个数字。

Sample Input
1
5 3
1 2 3 4 4
1 5
5 5
2 3
Sample Output
1
5
3

Hint

For the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first apple.
For the second query, the heights of the apples were 1, 2, 3, 4, 5, so Taotao would pick all these five apples.
For the third query, the heights of the apples were 1, 3, 3, 4, 4, so Taotao would pick the first, the second and the fourth apples.

解题思路

比赛的时候调了挺久，还是错了，之后看了大佬代码才懂怎么写。
思路的话我就不重复讲了，直接看大佬讲解吧。
附上大佬博客，顺便说一下大佬博客中的数组作用，方便大家理解。
【链接】

各数组的作用

a数组：原数组
ans数组：假设从1开始取数字，最多可以取多少个数字
b数组：假设从1开始取数字，能取到的所有数字（数字的值）
max数组：假设从1开始取数字，取到当前位置的最大值
v[i]：假设没有下标为i的数字，可能取的数字。
（假设原数组为（1，2，5，3，4），v [ 3 ] = { 3 , 4 } ）

AC代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef struct node
{
    int id, val;
}Node;
int a[N], ans[N], maxn[N], b[N];
int main()
{
    int t, n, q, p, c;
    scanf("%d", &t);
    while (t--)
    {
        vector<int>v[N];
        memset(maxn, 0, sizeof(maxn));
        memset(ans, 0, sizeof(ans));
        memset(b, 0, sizeof(b));
        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;
        maxn[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];
            }
            else if (mx1.val < a[i])
            {
                mx1.val = a[i];
                mx1.id = i;
                v[mx.id].push_back(a[i]);
            }
            maxn[i] = mx.val;
            ans[i] = cnt;
        }
        while (q--)
        {
            scanf("%d%d", &p, &c);
            int sum = 0;
            if (c > a[p])
            {
                if (c > maxn[p - 1])
                {
                    sum++;
                    sum += ans[p - 1];
                    int kk = upper_bound(b, b + cnt, c) - b;
                    sum += cnt - kk;
                }
                else
                    sum = ans[n];
            }
            else if (c == a[p])
                sum = ans[n];
            else
            {
                sum += ans[p - 1];
                if (c > maxn[p - 1])
                    sum++;
                if (a[p] == maxn[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;
                    sum += cnt - kk1;
                }
                else
                    sum = ans[n];
            }
            printf("%d\n", sum);
        }
    }
}