hdu6406----Taotao Picks Apples(模拟)
Taotao Picks ApplesTime Limit: 2000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1904 Accepted Submission(s): 597 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.
Input The first line of input is a single line of integer T (1≤T≤10) , the number of test cases.
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.
|
题目是TT摘苹果,第一个必须摘掉,后面必须按照严格递增的规则摘。会有m个查询,每一个查询给出p和q,意思是把第p个苹果的高度改成q,TT还能摘到几个苹果。
思路:先把原序列被选择的元素记录一下,然后进行处理。
分成两大类五小类情况:
1:第p个元素不在原来被选择的序列中:(1)比原来的数小(2)比原来的数大
2:第p个元素在原来被选择的序列中:(1)比原来的数大(2)比原来的数小,但是比上一个选择的数大(3)上一个选择的数小
先把原先的序列处理一下,在查询的时候对五种情况中分别处理就ok了。
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100010
#define mod 7
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[maxn];
int b[maxn];
int c[maxn];
int d[maxn];
vector<int>v[maxn];
vector<int>w[maxn];
int vis[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++){v[i].clear();w[i].clear();a[i]=0;b[i]=0;c[i]=0;d[i]=0;vis[i]=0;}
int l=0;
int r=0;
int maxx=-1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>maxx){ maxx=a[i];vis[i]=1;b[i]=maxx;c[l++]=maxx;d[i]=r;r=i;}
else if(a[i]<=maxx){ vis[i]=0;b[i]=maxx;}
}
int k=0;
for(int i=1;i<=n;i++){
if(vis[i]==1){k=i;continue;}
int x=v[k].size();
if(x==0||(x>0&&a[i]>v[k][x-1]))
v[k].push_back(a[i]);
}
int j1=0,j2=0;
a[0]=-1;
for(int i=1;i<=n;i++){
if(vis[i]==1){j1=j2;j2=i;continue;}
int x=w[j1].size();
if((x==0&&a[i]>a[j1])||(x>0&&a[i]>w[j1][x-1]))
w[j1].push_back(a[i]);
}
int p,q;
for(int i=1;i<=m;i++){
scanf("%d%d",&p,&q);
if(vis[p]==0&&q<=b[p])printf("%d\n",l);
if(vis[p]==0&&q>b[p]){
int x=l-((upper_bound(c,c+l,q)-c)-(upper_bound(c,c+l,b[p])-c));
printf("%d\n",x+1);
}
if(vis[p]==1&&q>=b[p]){
int x=l-((upper_bound(c,c+l,q)-c)-(upper_bound(c,c+l,b[p])-c));
printf("%d\n",x);
}
if(vis[p]==1&&q<b[p]){
if(p==1||q>b[p-1]){
int x=upper_bound(v[p].begin(),v[p].end(),maxx)-upper_bound(v[p].begin(),v[p].end(),q);
printf("%d\n",l+x);
}
else {
int x=upper_bound(w[d[p]].begin(),w[d[p]].end(),maxx)-upper_bound(w[d[p]].begin(),w[d[p]].end(),a[d[p]]);
printf("%d\n",l-1+x);
}
}
}
}
}
上一篇: HDU 6406 Taotao Picks Apples(线段树)
下一篇: 离散化板子
推荐阅读
-
HDU6406 Taotao Picks Apples(2018HDU多校联赛第八场,线段树)
-
2018HDU多校8-1010-Taotao Picks Apples(hdu 6406)-线段树+预处理
-
【hdu 6406】Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples (线段树)
-
HDU 6406 Taotao Picks Apples
-
Taotao Picks Apples HDU - 6406
-
HDU 6406 Taotao Picks Apples
-
hdu 6406 Taotao Picks Apples
-
HDU 6406 Taotao Picks Apples