2018HDU多校8-1010-Taotao Picks Apples(hdu 6406)-线段树+预处理

题意：

给出一个数列，每次修改其中一个数，求该数列的严格最长上升序列(只要后一个数大于之前最大数，就必须要选)

思路：

先讨论全部情况，可得到以下结论，对于一个修改p，q，以p位置为断点，分别考虑1~p-1，和p+1~n两段
对于前段，若q>premax[p-1]，则表示修改后的p位置一定会被选，则ans+=pre[p-1]+1
否则，表示修改后p位置不被选择，前半段的贡献就是pre[p-1]，则ans+=pre[p-1]
对于后段，p变大会导致原来可选的部分不可选了，要把这部分减去，p变小，可能会使原来不可选的变可选，要把这部分加上
val=max(premax[p-1],q)，val即为当前最大值，在p+1~n中找到第一个大于val的数的位置cur，ans+=suf[cur]
结合两段的值，就是最后答案
为实现上述做法，需要预处理出pre[]表示1~n每个位置的最大上升序列长度，premax[]表示1~n每个位置的前序最大值，suf[]表示i~n每个位置的最大上升序列长度
为得到suf[],需要利用单调栈，从后向前处理
为找到p+1~n中第一个大于val的值，需要利用线段树查询

思考：

使用线段树找区间中第一个大于k值的位置(下标)；使用单调栈处理出每个位置向左遍历，第一个大于它的数的位置，即可知这段区间的长度。

代码：

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int n,m;
int a[100005];
int pre[100005];
int premax[100005];
int suf[100005];


struct node
{
    int Max,id;
}tree[500005];

void push_up(int rt)
{
    int ls=(rt<<1),rs=(rt<<1|1);
    tree[rt].Max=max(tree[ls].Max,tree[rs].Max);
    if(tree[ls].Max>tree[rs].Max)
        tree[rt].id=tree[ls].id;
    else
        tree[rt].id=tree[rs].id;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt].Max=a[l];
        tree[rt].id=l;
        return;
    }
    int m=(l+r)/2;
    build(lson);
    build(rson);
    push_up(rt);
}
int cur;

void query(int l,int r,int rt,int ql,int qr,int k)//求区间第一个大于k的数的下标
{
    if(l==r)
    {
        if(tree[rt].Max>k)
        cur=min(cur,tree[rt].id);
        return;
    }
    int ls=rt*2,rs=rt*2+1,m=(l+r)/2;
    if(l>=ql&&r<=qr)
    {
        if(tree[ls].Max>k)
        query(l,m,ls,ql,qr,k);
        else if(tree[rs].Max>k)
        query(m+1,r,rs,ql,qr,k);
        return;
    }
    if(ql<=m)
    query(l,m,ls,ql,qr,k);
    if(qr>m)
    query(m+1,r,rs,ql,qr,k);
}
stack<int>s;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        while(s.size()) s.pop();
        cin>>n>>m;
        int Max=0;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]>Max)
            {
                cnt++;
                Max=a[i];
            }
            pre[i]=cnt;
            premax[i]=Max;
        }
        build(1,n,1);

        suf[n]=1;
        s.push(a[n]);
        for(int i=n-1;i>=1;i--)
        {
             while(s.size() && a[i]>=s.top()) s.pop();
             s.push(a[i]);
             suf[i]=s.size();
        }

        for(int i=0;i<m;i++)
        {
            long long ans=0;
            int p,q;
            cin>>p>>q;
            if(premax[p-1]>=q) ans=pre[p-1];
            else ans=pre[p-1]+1;
            cur=n+1;
            int val=max(premax[p-1],q);
            if(p!=n)
                query(1,n,1,p+1,n,val);
            if(cur<=n)
                ans+=suf[cur];
            cout<<ans<<endl;
        }
    }
    return 0;
}