【hdu 6406】Taotao Picks Apples

题意相当于问你改变一个位置之后。从左往右扫描最大值。这个最大值会改变多少次。

【题解】

假设我们改变的是i这个位置,下面说的a[i]都是改成q之后的a[i] 我们完全可以直接暴力算出来左边的最大值会改变多少次以及右边的最大值会改变多少次。那么如何找呢? 首先在1..i-1当中找到那个最大值a[idx1] 这个可以用st表预处理出来。然后如果a[i]这个位置是更新最大值中的某一次的话ans++。显然a[i]要满足>a[idx1] 如果不满足的话,那么a[i]就不是更新最大值中的某一次,ans不变就好仍然为0 然后我们可以通过一次扫描就能预处理出来到达a[idx1]需要更新多少次最大值。

然后我们可以用ST表。找出来最近的且大于key的数字a[idx2]
(只需看看L..mid这一段最大值(用st表获得)是不是大于key,是的话R = mid-1否则L = mid +1,这样写一下二分就能求出a[idx2]了
这里的key,如果a[i]>a[idx1],那么key = a[i]否则key = a[idx1];(因为要满足递增的性质。
(注意千万别以为是upper_bound....upper_bound找的是最小的且大于key的数字a[idx2]...比如a={2 4 3}|,set.upper_bound(2)的结果是3而不是离他更近的4.。。。。
之后只要求出a[idx2]开始还要更新多少次最大值就可以了。

这个可以从后往前维护一个单调队列。单调队列的长度就是更新最大值的次数。
ans+=到达idx1更新的次数+idx2到最后更新的次数。
输出ans就好。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 1E5;

int n,m,a[N+10],_size[N+10];
int dl[N+10],h,t,step[N+10],dp[N+10][20];

int ma(int i,int j){
    if (a[i]>=a[j]) return i;
    return j;
}

int get_ma(int l,int r){
    if (l>r) return 0;
    int len  = log2(r-l+1);
    return ma(dp[l][len],dp[r-(1<<len)+1][len]);
}

int get_first_bigger(int q,int L){
    int l = L,r = n,temp = -1;
    while (l <= r){
        int mid = (l+r)>>1;
        if (a[get_ma(L,mid)]>q){
            temp = mid;
            r = mid-1;
        }else l = mid + 1;
    }
    return temp;
}

int main(){
    //freopen("D:\rush.txt","r",stdin);
    //freopen("D:\rush_out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
        h = 1,t = 0;
        for (int i = n;i >= 1;i--){
            while (h<=t && a[i]>=a[dl[t]]) t--;
            dl[++t] = i;
            _size[i] = t-h+1;
        }
        step[1] = 1;
        int cur = 1;
        for (int i = 2;i <= n;i++)
            if (a[i]>a[cur]){
                step[i] = step[cur]+1;
                cur = i;
            }
        for (int i = 0;i <= n;i++) dp[i][0] = i;
        for (int l = 1;l <= 17;l++){
            for (int i = 1;i <= n;i++){
                if ((i+(1<<l)-1)>n) break;
                dp[i][l] = ma(dp[i][l-1],dp[i+(1<<(l-1))][l-1]);
            }
        }
        for (int i = 1;i <= m;i++){
            int p,q;
            scanf("%d%d",&p,&q);
            int idx = get_ma(1,p-1);
            int key = q,ans = 0;
            if (q<=a[idx]){
                key = a[idx];
                ans = -1;
            }
            int idx2 = get_first_bigger(key,p+1);
            if (idx2==-1){
                ans += step[idx]+1;
            }else{
                ans += step[idx]+1+_size[idx2];
            }
            printf("%d
",ans);
        }
    }
    return 0;
}