HDU - 6406 Taotao Picks Apples (RMQ+dp+二分)

题意：N个高度为hi的果子，摘果子的个数是从位置1开始从左到右的严格递增子序列的个数。有M次操作，每次操作对初始序列修改位置p的果子高度为q。每次操作后输出修改后能摘到得数目。

分析：将序列分为左、右两部分，每次修改之后的结果是p左部到p递增的子序列长度，加上右部第一个高度大于max(q,p位置之前最大的高度)位置开始的递增子序列长度。

左部的查询可以线性递推预处理得到，右部的查询需借助ST表预处理出区间最大值，并二分求得位置。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;

int N, m, tot;

int h[];

int st[MAXN][-__builtin_clz(MAXN)];

int dp[];

int sel[], pre[], c[];

void init_st() {

  int l =  - __builtin_clz(N);

  for(int i=;i<N;++i) st[i][] = h[i];

  for(int j=;j<l;++j)

    for (int i=;i<+N-(<<j);++i)

        st[i][j+] = max(st[i][j], st[i+(<<j)][j]);

}

int rmq(int l, int r) {

  int k =  - __builtin_clz(r - l + );

  return max(st[l][k], st[r-(<<k)+][k]);

}

int getbignext(int pos, int val) {

  int l = pos + , r = N, mid;

  while (r > l) {

    mid = (l + r) / ;

    if (rmq(pos+, mid) <= val) l = mid + ;

    else r = mid;

  }

  return l;

}

void initdp() {

  int cnt = ;

  dp[N] = ;

  for (int i = N - ; i >= ; i--) {

    int pos = getbignext(i, h[i]);

    dp[i] = dp[pos] + ;

  }

  sel[] = ; pre[] = -; c[] = ;

  int last = , lasth = h[];

  for (int i = ; i < N; i++) {

    pre[i] = last;

    if (h[i] > lasth){

      sel[i] = ;

      last = i;

      lasth = h[i];

      cnt++;

    } else sel[i] = ;

    c[i] = cnt;

  }

  tot = cnt;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int T;scanf("%d",&T);

    while(T--){

        int Q;

        scanf("%d%d",&N,&Q);

        for(int i=;i<N;++i) scanf("%d",&h[i]);

        init_st();

        initdp();

        int p,q;

        while(Q--){

            scanf("%d%d",&p,&q);

            p--;

            int res=;

            if(sel[p]){         //这个位置保持递增

                if(p==){

                    res = dp[getbignext(p,q)]+;

                }

                else{

                    if(q>h[pre[p]]){

                        res += c[p];

                        res += dp[getbignext(p,q)];

                    }

                    else{

                        res += c[pre[p]];

                        res += dp[getbignext(p,h[pre[p]])];

                    }

                }

            }

            else{

                if(q<=h[pre[p]]){

                    res= tot;

                }

                else{

                    res += c[pre[p]]+;

                    res += dp[getbignext(p,q)];

                }

            }

            printf("%d\n",res);

        }

    }

    return ;

}

巴特西

HDU - 6406 Taotao Picks Apples (RMQ+dp+二分)

最新文章

热门文章