HDU 6406 Taotao Picks Apples

Taotao Picks Apples

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

 

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.

 

 

Source

2018 Multi-University Training Contest 8

 

 

题意：有m次询问，每一次询问更改长度为n的序列中一个点的值，然后求以第一个元素为起点的最长上升子序列的长度。

思路：离线处理询问，按照询问点的大小，从小到大排序。以询问点为界限，将序列拆分成左右两部分，左边一个部分记录每一个询问点前有多少个比它大的数，至于右边一部分，因为求的是从头开始的严格上升子序列长度，这种严格递增，只要是比之前大就加上的之前的多校出现过，是hdu6319解法就是反着维护一个递减的单调队列。这里同样可以如此，从后往前维护一个递减的单调队列，然后二分找出每一个询问点之后第一个比它大的元素，之后就可以根据维护的单调队列知道询问点右边有多少比它大的数，左右两部分相加即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct node
{
    int pos,val,id;
    bool operator<(const node &a)const
    {
        if(pos==a.pos) return val<a.val;
        return pos<a.pos;
    }
}a[maxn];
int main()
{
    int t,n,m,num[maxn],ans[maxn],dp[maxn];
    int b[maxn];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a[i].pos,&a[i].val);
            a[i].id=i;
        }
        sort(a+1,a+m+1);
        int last=0,cnt=0,top=0;
        for(int i=1;i<=m;i++)
        {
            while(last<a[i].pos)//找出询问点前有多少比它大的元素
            {
                if(num[last]>top)
                {
                    top=num[last];
                    cnt++;
                }
                last++;
            }
            if(a[i].val>top)//如果询问点前最大的元素比修改后的值小，需要加上修改后的点本身
                ans[a[i].id]=cnt+1;
            else//如果询问点前最大的元素比修改后的大的话，把修改后的值更改为最大值
            {
                ans[a[i].id]=cnt;
                a[i].val=top;
            }
        }
        top=0,last=n;
        for(int i=m;i>=1;i--)
        {
            while(last>a[i].pos)//维护一个递减单调队列，dp值记录每一个点为起点的最长上升子序列
            {
                while(num[last]>=num[b[top]]&&top!=0)
                    top--;
                if(top==0) dp[last]=1;
                else dp[last]=dp[b[top]]+1;
                top++;
                b[top]=last;
                last--;
            }
            int l=1,r=top,mid,temp=0;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(num[b[mid]]>a[i].val)
                {
                    temp=b[mid];
                    l=mid+1;
                }
                else r=mid-1;
            }
            ans[a[i].id]+=dp[temp];
        }
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
}