转载请注明出处:http://tokitsukaze.live/

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6406


题意:
一个数轴上有n个苹果,放在位置1到n。刚开始篮子里没有苹果,一个人从1走到n,如果第i个位置的苹果严格大于篮子里所有苹果,就把那个苹果放进篮子。然后有q个询问,每次询问如果把位置x的苹果替换成大小为y的苹果,那么从1走到n,篮子里会有多少苹果。注意询问的替换不是真正的替换。


题解:
因为没有修改(不是真正的替换),所以离线做。
先预处理出一个dp数组。dp[i]表示区间[i,n]的答案。倒着for,从区间[i+1,n]中找出第一个比v[i]大的数的位置转移过来,不存在的话dp[i]=1。
对询问按x从小到大排序,然后扫过去。
对于查询的一个位置x:
区间[1,x-1]的最大值记为mx。
1.对于区间[1,x-1]的答案是确定,记为now。
2.考虑x这个位置修改后的数字val:
(1)如果val大于mx,那么ans=now+1+dp[pos]。pos为区间[x+1,n]中第一个比val大的数的位置。
(2)如果val小于等于mx,那么ans=now+dp[pos]。pos为区间[x+1,n]中第一个比mx大的数的位置。

至于怎么找区间中第一个比x大的数的位置,我们可以预处理一下RMQ,然后二分区间,查询区间最大值调整二分边界。

总复杂度是O(nlogn+qlogn)。

代码:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=998244353;
/********************************* head *********************************/
int v[MAX],maxx[MAX][20];
void RMQ(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
maxx[i][0]=v[i];
for(j=1;1<<(j-1)<=n;j++) maxx[i][j]=0;
}
for(j=1;1<<(j-1)<=n;j++)
{
for(i=1;i+(1<<j)-1<=n;i++)
{
int t=1<<(j-1);
maxx[i][j]=max(maxx[i][j-1],maxx[i+t][j-1]);
}
}
}
int query(int l,int r)
{
int j=(int)(log10(r-l+1)/log10(2))+1;
int i=r-(1<<(j-1))+1;
return max(maxx[l][j-1],maxx[i][j-1]);
}
struct node
{
int x,v,id;
void input(int i)
{
read(x,v);
id=i;
}
friend bool operator<(node a,node b){return a.x<b.x;}
}qs[MAX];
int ans[MAX],dp[MAX];
void go()
{
int t,i,j,n,q,now,mx,pos;
read(t);
while(t--)
{
read(n,q);
for(i=1;i<=n;i++) read(v[i]);
RMQ(n);
auto getpos=[&](int _l,int _r,int v)->int
{
int l,r,mid;
l=_l;
r=_r;
if(l>r) return -1;
while(l<r)
{
mid=(l+r)>>1;
if(query(l,mid)<=v) l=mid+1;
else r=mid;
}
if(query(l,l)<=v) return -1;
return l;
};
dp[n]=1;
for(i=n-1;i;i--)
{
pos=getpos(i+1,n,v[i]);
if(pos!=-1) dp[i]=dp[pos]+1;
else dp[i]=1;
}
for(i=1;i<=q;i++) qs[i].input(i);
sort(qs+1,qs+1+q);
now=0;
mx=-1;
for(i=1,j=1;i<=q;i++)
{
while(j<qs[i].x)
{
if(v[j]>mx)
{
mx=v[j];
now++;
}
j++;
}
ans[qs[i].id]=now;
if(qs[i].v>mx)
{
pos=getpos(j+1,n,qs[i].v);
ans[qs[i].id]++;
}
else pos=getpos(j+1,n,mx);
if(pos!=-1) ans[qs[i].id]+=dp[pos];
}
for(i=1;i<=q;i++) printf("%d\n",ans[i]);
}
}