HDU6406 Taotao Picks Apples(2018HDU多校联赛第八场,线段树)

Problem Description

There is an apple tree in front of Taotao’s house. When autumn comes, n apples on the tree ripen, and Taotao will go to pick these apples.
When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple; otherwise, he will not pick.
Given the heights of these apples h1,h2,⋯,hn, you are required to answer some independent queries. Each query is two integers p,q, which asks the number of apples Taotao would pick, if the height of the p-th apple were q (instead of hp). Can you answer all these queries?

Input

The first line of input is a single line of integer T (1≤T≤10), the number of test cases.
Each test case begins with a line of two integers n,m (1≤n,m≤105), denoting the number of apples and the number of queries. It is then followed by a single line of n integers h1,h2,⋯,hn (1≤hi≤109), denoting the heights of the apples. The next m lines give the queries. Each of these m lines contains two integers p (1≤p≤n) and q (1≤q≤109), as described in the problem statement.

Output

For each query, display the answer in a single line.

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.

思路

题意是给一个序列，每次贪心选取比前一个数大的数。每次询问修改一个数，求修改后的序列的能选出 多少个数。询问不叠加。

定义:

• dp[i]表示从1到i之间最多能递增多少个
• dp2[i]表示从i到n之间最多能递增多少个

对于一个位置，假设当前要改的位置为pos，那么我们就可以分成三段:

• [1,pos-1]

• [pos,pos]

• [pos+1,n]

我们只需要找到[1,pos-1]这个区间的最大值及其位置，那么左边的最多递增的答案就是ans+=dp[cur],如果当前改的位置的值大于左边的最大值那么ans+=1，接下来我们只需要求出右边部分的大于左边部分的最大值的第一个位置cur，再ans+=dp2[cur]就是答案。

很明显dp[]数组非常容易求出，那么dp2[]如何来求呢，我们从n~1倒着来，每次求出当前位置i到n的大于a[i]的第一个位置cur，如果大于a[i],dp2[i]=dp2[cur]+1

我们可以用一棵线段树维护一下区间的最大值及其位置即可。

附上官方题解,方法不一样，但是大体思路一样

代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 100;
int a[N], dp[N], dp2[N];
int MAX[N << 2], id[N << 2];
void pushup(int rt)
{
    int ma1 = MAX[rt << 1];
    int ma2 = MAX[rt << 1 | 1];
    if (ma1 > ma2)
    {
        MAX[rt] = ma1;
        id[rt] = id[rt << 1];
    }
    else
    {
        MAX[rt] = ma2;
        id[rt] = id[rt << 1 | 1];
    }
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        MAX[rt] = a[l];
        id[rt] = l;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}
struct node
{
    int maxx;
    int id;
};
node maxnode(node a, node b)
{
    node res;
    if (a.maxx > b.maxx)
    {
        res.maxx = a.maxx;
        res.id = a.id;
    }
    else
    {
        res.maxx = b.maxx;
        res.id = b.id;
    }
    return res;
}
node query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        node res;
        res.maxx = MAX[rt];
        res.id = id[rt];
        return res;
    }
    int m = (l + r) >> 1;
    node ans;
    ans.maxx = 0;
    if (L <= m)
        ans = maxnode(ans, query(L, R, lson));
    if (R > m)
        ans = maxnode(ans, query(L, R, rson));
    return ans;
}
int cur;
void qmax_id(int L, int R, int l, int r, int rt, int k) //查[L,R]大于k的第一个位置
{
    if (l == r)
    {
        if (MAX[rt] > k)
            cur = min(cur, l);
        return;
    }
    int m = (l + r) >> 1;
    if (L <= l && r <= R)
    {
        if (MAX[rt << 1] > k)
            qmax_id(L, R, lson, k);
        else if (MAX[rt << 1 | 1] > k)
            qmax_id(L, R, rson, k);
        return;
    }
    if (L <= m)
        qmax_id(L, R, lson, k);
    if (R > m)
        qmax_id(L, R, rson, k);
}
void solve()
{
    int x, pos, tmp, n, m;
    scanf("%d%d", &n, &m);
    dp[0] = 0, dp[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (i == 1)
        {
            tmp = a[i];
            continue;
        }
        if (a[i] > tmp)
        {
            tmp = a[i];
            dp[i] = dp[i - 1] + 1;
        }
        else
            dp[i] = dp[i - 1];
    }
    build(1, n, 1);
    for (int i = n; i >= 1; i--)
    {
        cur = n + 1;
        qmax_id(i, n, 1, n, 1, a[i]);
        if (cur > n)
            cur = 0;
        dp2[i] = dp2[cur] + 1;
    }
    while (m--)
    {
        int ans = 0, max_id = 0;
        scanf("%d%d", &pos, &x);
        if (pos > 1)
            max_id = query(1, pos - 1, 1, n, 1).id;
        ans += dp[max_id];
        if (x > a[max_id])
            ans++;
        else
            x = a[max_id];
        cur = n + 1;
        qmax_id(pos + 1, n, 1, n, 1, x);
        if (cur <= n)
            ans += dp2[cur];
        printf("%d\n", ans);
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}