[hdoj6406]Taotao Picks Apple

Taotao Picks Apples

题意

一段序列,从中挑选的子序列是这样规定的

能取就取,而且取得数字一定要比上一次取得数字要大。

已知一段序列,问如果改变序列中的一个数字,那么取得数字的个数是多少。

题解

每次查询将数组分为两部分$[1,p-1],[p+1,n]$,前半部分的最长长度就是可以通过预处理得到。很容易想到先处理出从头到$i$的最大长度$dl[i]$。然后针对后半段,我们要得到的是置换的$q$,然后大于他的第一个数字到末尾的最大长度。

有一个细节就是,如果置换的数字小于前面最大的数字,那么就是从前面最大的数字到$[p+1,n]$中间大于这个数字的第一个数字开始。

如果置换的数字大于前面最大的数字,那么答案就是$dl([1,p-1])+1+dr([p+1,n])$这个意思。

寻找第一个比该数字大的最前数字用的是线段树。


+1 判断最大值的时候直接用mmax判断,应该用a[x]判断

+1 得到dr数组的时候范围搞错了,应该是[i,n]的范围内比a[i]大的第一个数字。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5+100;
int n,m;
int a[maxn];
struct Segtree{
int mmax[maxn<<2]={0},id[maxn<<2]={0},cur=0;
void pushup(int rt){
int x = id[rt<<1],y = id[rt<<1|1];
id[rt] = a[x]>a[y]?x:y;
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = a[l];
id[rt] = l;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
pushup(rt);
}
void query1(int val,int L,int R,int l,int r,int rt){
if(l==r){
if(mmax[rt]>val) cur = min(cur,id[rt]);
return;
}
int mid = l+r>>1;
if(L<=l && r<=R){
if(mmax[rt<<1]>val) query1(val,L,R,lson);
else if(mmax[rt<<1|1]>val) query1(val,L,R,rson);
return;
}
if(L<=mid) query1(val,L,R,lson);
if(mid<R) query1(val,L,R,rson);
}
void query2(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
if(mmax[rt]>a[cur]) cur = id[rt];
return;
}
int mid = l+r>>1;
if(L<=mid) query2(L,R,lson);
if(mid<R) query2(L,R,rson);
}
}st;
int dl[maxn],dr[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
rep(i,1,n+1) scanf("%d",a+i);
st.build(1,n,1);
int mx = 0;
memset(dr,0,sizeof(dr));
memset(dl,0,sizeof(dl));
rep(i,1,n+1){
if(a[i]>mx){
mx = a[i];
dl[i] = dl[i-1]+1;
}else{
dl[i] = dl[i-1];
}
}
per(i,1,n+1){
st.cur = n+1;
st.query1(a[i],i,n,1,n,1);
if(st.cur>n) st.cur = 0;
dr[i] = dr[st.cur]+1;
}
while(m--){
int p,q;scanf("%d%d",&p,&q);
int ans = 0; st.cur = 0;
if(p>1) st.query2(1,p-1,1,n,1);
ans += dl[st.cur];
if(q > a[st.cur]) ans ++;
if(q <= a[st.cur]) q = a[st.cur];
st.cur = n+1;
if(p<n) st.query1(q,p+1,n,1,n,1);
if(st.cur<=n) ans += dr[st.cur];
printf("%d\n",ans);
}
}

return 0;
}