【hdu 6406】Taotao Picks Apples
2024-08-31 08:40:30
【链接】 我是链接,点我呀:)
【题意】
题意相当于问你改变一个位置之后。
从左往右扫描最大值。这个最大值会改变多少次。
【题解】
假设我们改变的是i这个位置,下面说的a[i]都是改成q之后的a[i]
我们完全可以直接暴力算出来左边的最大值会改变多少次以及右边的最大值会改变多少次。
那么如何找呢?
首先在1..i-1当中找到那个最大值a[idx1]
这个可以用st表预处理出来。
然后如果a[i]这个位置是更新最大值中的某一次的话ans++。
显然a[i]要满足>a[idx1]
如果不满足的话,那么a[i]就不是更新最大值中的某一次,ans不变就好仍然为0
然后我们可以通过一次扫描就能预处理出来到达a[idx1]需要更新多少次最大值。
然后我们可以用ST表。找出来最近的且大于key的数字a[idx2]
(只需看看L..mid这一段最大值(用st表获得)是不是大于key,是的话R = mid-1否则L = mid +1,这样写一下二分就能求出a[idx2]了
这里的key,如果a[i]>a[idx1],那么key = a[i]否则key = a[idx1];(因为要满足递增的性质。
(注意千万别以为是upper_bound....upper_bound找的是最小的且大于key的数字a[idx2]...比如a={2 4 3}|,set.upper_bound(2)的结果是3而不是离他更近的4.。。。。
之后只要求出a[idx2]开始还要更新多少次最大值就可以了。
这个可以从后往前维护一个单调队列。单调队列的长度就是更新最大值的次数。
ans+=到达idx1更新的次数+idx2到最后更新的次数。
输出ans就好。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5;
int n,m,a[N+10],_size[N+10];
int dl[N+10],h,t,step[N+10],dp[N+10][20];
int ma(int i,int j){
if (a[i]>=a[j]) return i;
return j;
}
int get_ma(int l,int r){
if (l>r) return 0;
int len = log2(r-l+1);
return ma(dp[l][len],dp[r-(1<<len)+1][len]);
}
int get_first_bigger(int q,int L){
int l = L,r = n,temp = -1;
while (l <= r){
int mid = (l+r)>>1;
if (a[get_ma(L,mid)]>q){
temp = mid;
r = mid-1;
}else l = mid + 1;
}
return temp;
}
int main(){
//freopen("D:\\rush.txt","r",stdin);
//freopen("D:\\rush_out.txt","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
h = 1,t = 0;
for (int i = n;i >= 1;i--){
while (h<=t && a[i]>=a[dl[t]]) t--;
dl[++t] = i;
_size[i] = t-h+1;
}
step[1] = 1;
int cur = 1;
for (int i = 2;i <= n;i++)
if (a[i]>a[cur]){
step[i] = step[cur]+1;
cur = i;
}
for (int i = 0;i <= n;i++) dp[i][0] = i;
for (int l = 1;l <= 17;l++){
for (int i = 1;i <= n;i++){
if ((i+(1<<l)-1)>n) break;
dp[i][l] = ma(dp[i][l-1],dp[i+(1<<(l-1))][l-1]);
}
}
for (int i = 1;i <= m;i++){
int p,q;
scanf("%d%d",&p,&q);
int idx = get_ma(1,p-1);
int key = q,ans = 0;
if (q<=a[idx]){
key = a[idx];
ans = -1;
}
int idx2 = get_first_bigger(key,p+1);
if (idx2==-1){
ans += step[idx]+1;
}else{
ans += step[idx]+1+_size[idx2];
}
printf("%d\n",ans);
}
}
return 0;
}
最新文章
- SQL Injection bypass WAF
- C# 操作PPt,去掉文本框的边框
- 使用 dynamic 标记解析JSON字符串
- Return 和 Break 的区别
- iOS UICollectionView 入门 07 点击cell放大图片
- new[]上面居然有一个内存计数,怪不得delete[]从来不出错
- phpmailer{群发并且发送附件}
- 原生js判断css3动画过度(transition)结束 transitionend事件 以及关键帧keyframes动画结束(animation)回调函数 animationEnd 以及 css 过渡 transition无效
- C++中的引用和移动语义
- CSS 三条横线等分
- unity 面试题(答案)
- 使用Java面向对象单词必备
- Nginx 缓存深入理解
- Python 和 Scikit-Learn
- kernel: INFO: task sadc:14833 blocked for more than 120 seconds.
- 【转】C语言宏高级用法 [总结]
- 集成学习之Boosting —— XGBoost
- Codeforces1106F 【BSGS】【矩阵快速幂】【exgcd】
- static &; abstract
- pyspark视频