Taotao Picks Apples

题目连接

[HDU 6406] 2018 Multi-University Training Contest 8--1010 Taotao Picks Apples

题解

高档题。题意大概是给定一组数字,按照如下规则以此取数:

  • 取出第一个数
  • 如果当前数字严格大于上一个选取的数字,取出当前数字

现在给出多个询问,每个询问处理将某个数字改成其他数字,求取出多少数字。

首先将原序列中取出的数字找出来,标记为关键点,之后将两两关键点之间以上一个关键点作为第一个取出的数字,找出区间内可以取到的关键点。接下来分为以下几种情况讨论

  • 修改的数字为第一组关键点

    • 将当前数字升高
      直接判断第一批关键点中严格大于修改后数字的第一个数字,输出原始序列答案减去两数之间的关键点数即可。
    • 将当前数字降低
      首先判断修改后数字的值是否严格大于上一个关键点。如果不是,将答案记录为原数字减一,之后再将答案加上该位置对应的第二组关键点中大于修改后数字的数量。
  • 修改的数字不是第一组关键点

    • 将当前数字升高

      • 修改后的值小于等于上一个第一组关键点
        直接输出原始序列的答案
      • 修改后的值大于上一个第一组关键点
        判断第一批关键点中严格大于当前位置值最小的一个,原始序列答案减去两数之间关键点数即为答案。
    • 将当前数字降低
      直接输出原始序列的答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int input[maxn];
int imp[maxn],pos[maxn];
int isimp[maxn];
vector<int> decc[maxn];
int main(){
//    freopen("1.in","r",stdin);
//    freopen("zj.out","w",stdout);
//    ios::sync_with_stdio(0);
//    cout.tie(0);
//    cin.tie(0);
    int t,n,m,pre,num,p,q;

    for (cin>>t;t;t--){
        memset(isimp,0,sizeof(isimp));
        memset(imp,0,sizeof(imp));
        memset(pos,0,sizeof(pos));
        num=0;

        cin>>n>>m;
        for(int i=1;i<=n;i++)decc[i].clear();
        for (int i=1;i<=n;i++){
            scanf("%d",&input[i]);
        }

        pre=input[1];
        imp[++num]=input[1];
        pos[num]=1;
        isimp[num]=1;
        for (int i=2;i<=n;i++){
            if(input[i]>pre){
                pre=input[i];
                imp[++num]=input[i];
                pos[num]=i;
                isimp[i]=num;
            }
        }
        for (int i=1;i<num;i++){
            pre=imp[i-1];
            for (int j=pos[i]+1;j<pos[i+1];j++){
                if (input[j]>pre){
                    pre=input[j];
                    decc[i].push_back(pre);
                }
            }
        }
        pre=imp[num-1];
        for (int j=pos[num]+1;j<=n;j++){
            if (input[j]>pre){
                pre=input[j];
                decc[num].push_back(pre);
            }
        }

        for (int i=1;i<=m;i++){
            cin>>p>>q;
            if (isimp[p]){
                if (q==input[p]){
                    //cout<<num<<endl;
                    printf("%d\n",num);
                }
                else if (q>input[p]){
                    int temp=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    printf("%d\n",isimp[p]+num-temp+1);
                    //cout<<isimp[p]+num-temp+1<<endl;
                }
                else if(q<input[p]){
                    int temp=(int)(upper_bound(decc[isimp[p]].begin(),decc[isimp[p]].end(),q)-decc[isimp[p]].begin());
                    //cout<<num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp<<endl;
                    printf("%d\n",num-(q>imp[isimp[p]-1]?0:1)+decc[isimp[p]].size()-temp);
                }
            }
            else{
                int temp=(int)(upper_bound(pos+1,pos+num+1,p)-pos);
                temp--;
                if (q<=imp[temp])printf("%d\n",num);
                else{
                    int temp1=(int)(upper_bound(imp+1,imp+num+1,q)-imp);
                    //cout<<temp+num-temp1+1+1<<endl;
                    printf("%d\n",temp+num-temp1+1+1);
                }

            }
        }
    }
}

标签: math

添加新评论