HDU 6406（线段树）

传送门

题面：

Taotao Picks Apples

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1873    Accepted Submission(s): 587
 

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.

题目描述：

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

题目分析：

    事实上这是一个bzoj2957原题，然而之前却没有做过。

    因为我们需要维护的是一段区间内的一个严格单调递增的序列，考虑到其具有的单调性，我们可以考虑运用线段树维护每一小段的最大值，并且通过最大值进行对长度的更新。

    现在考虑如何在push_up的过程中将严格上升序列长度进行更新。

    我们去维护一个区间中能够摘取多少个苹果，就是求[l,mid] 和[mid+1,r]两个区间的总贡献。很显然如果前面的苹果大于后面的苹果的话，那么后面的苹果必定无法摘得，所有一个区间的答案至少应该等于他左儿子的答案，那么对于右儿子我们需要用左儿子的最大值来计算他对当前区间的贡献。而对于右儿子的贡献，我们只需进行分类讨论即可。

    如上面的一颗二叉树作为例子进行讲解，1号结点的贡献必定是由左儿子2号结点的贡献再加上右儿子3号结点的贡献相加得到的。而对于3号结点对答案的贡献，我们设1号结点的左儿子2号结点的最大值为v，则有

    （1）倘若右儿子3号结点所对应的区间的最大值小于v，则证明3号结点对答案必定没有贡献，则直接返回0。

    （2）若3号结点对应区间的最大值大于v，且 3号结点的左儿子（6号结点）的最大值小于v，则证明6号结点对答案没有贡献，且3号结点的右儿子（7号结点）必定对答案有贡献，则我们即对7号结点进行递归寻找答案即可。

    （3）若3号结点的左儿子（6号结点）的最大值大于v，也就是说v对于7号结点是没有影响的，因此我们可以直接计算上7号结点的贡献即可（tr[rt].cnt-tr[rt<<1].cnt，注意一定不能是tr[rt<<1|1].cnt，因为那是对于右儿子的答案，而不是右儿子对当前区间的答案），然后跳转到区间的左儿子，重复以上过程  

    因为左右儿子只能够算一个，因此对于每一个push_up的过程的时间复杂度是O(logn)，对于整体来说时间复杂度为O(m*logn*loglogn)

代码：

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct ST{
    int cnt,maxx;
}tr[maxn<<2];
int a[maxn];
int query(int l,int r,int rt,int v){
    if(l==r) return tr[rt].maxx>v;//如果当前结点为根节点，则判断是否大于v，如果大于v答案+1
    if(tr[rt].maxx<=v) return 0;//如果当前的区间小于v，则整个区间对答案贡献为0
    int mid=(l+r)>>1;
    if(tr[rt<<1].maxx<=v) return query(mid+1,r,rt<<1|1,v);//如果当前区间的左儿子小于v,则直接返回右儿子的值
    else return tr[rt].cnt-tr[rt<<1].cnt+query(l,mid,rt<<1,v);//否则，直接将右儿子的值加上并递归求出左儿子的贡献
}
void build(int l,int r,int rt){//建树
    if(l==r){
        tr[rt].cnt=1;
        tr[rt].maxx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    //push_up的过程
    tr[rt].cnt=tr[rt<<1].cnt+query(mid+1,r,rt<<1|1,tr[rt<<1].maxx);
    tr[rt].maxx=max(tr[rt<<1].maxx,tr[rt<<1|1].maxx);
}
void update(int l,int r,int rt,int x,int y){//单点修改
    if(l==r){
        tr[rt].cnt=1;
        tr[rt].maxx=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,rt<<1,x,y);
    else update(mid+1,r,rt<<1|1,x,y);
    //push_up的过程
    tr[rt].cnt=tr[rt<<1].cnt+query(mid+1,r,rt<<1|1,tr[rt<<1].maxx);
    tr[rt].maxx=max(tr[rt<<1].maxx,tr[rt<<1|1].maxx);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            int tmp=a[x];
            update(1,n,1,x,y);
            printf("%d\n",tr[1].cnt);
            update(1,n,1,x,tmp);//注意这里要将之前的操作恢复
        }
    }
    return 0;
}