本文主要是介绍CodeForces 547B. Mike and Feet 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一个长度为n的数组a
a中一个连续区间的strength是区间内的最小值，对x=1,2,...,n分别求长度为x的连续区间中，strength的最大值是多少
思路：
对于每个a[i]找出在a[i]左边，离a[i]最近且比a[i]小的数的下标，记为VL[i],若不存在则VL[i]=0;
找出在a[i]右边，离a[i]最近且比a[i]小的数的下标，记为VR[i],若不存在则VR[i]=n+1;
(VL和VR数组可以用栈计算出，具体直接见代码)
那么，a[i]是区间(VL[i],VR[i])内的最小值，也就是说，a[i]会出现在长度为1,2,...,VR[i]-VL[i]-1 的组的strength中，于是就用a[i]去更新这些最大值
易知a[i]不会成为长度大于VR[i]-VL[i]-1的区间的最小值，也就不需要更新这些最大值。
现在给定一个数列ans[1],ans[2],..,ans[n]，初值为0
对于每个a[i],让区间[1,VR[i]-VL[i]-1]内的ans都与a[i]取最大值
要实现这个操作，可以用线段树。
在所有操作结束后一次性下传所有最大值标记，然后输出最后的ans数组即可。
看题解，第二点是不需要线段树来实现的，第二步可以做到O(n)
首先用ans[i]代表从i往左全部都与ans[i]进行max操作，这就相当于差分的思想
于是，前面第一步，直接令ans[ VR[i]-VL[i]-1 ]与a[i]进行max操作
然后倒着线性递推一遍ans[i]=max(ans[i],ans[i+1])就可以了。
线段树代码(6400KB 124ms)：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#define maxn 200007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
using namespace std;
int n;
int a[maxn];
int vl[maxn];
int vr[maxn];
stack<int> s;
int ans[maxn<<2];
void PushDown(int rt){if(ans[rt]){ans[rt<<1]=max(ans[rt],ans[rt<<1]);ans[rt<<1|1]=max(ans[rt],ans[rt<<1|1]);ans[rt]=0;}
}
void build(int l,int r,int rt){if(l==r){ans[rt]=0;return;}int m=(l+r)>>1;build(ls);build(rs);ans[rt]=0;
}
void Add(int L,int R,int C,int l,int r,int rt){if(L <= l && r <= R){ans[rt]=max(ans[rt],C);return;}int m=(l+r)>>1;if(L <= m) Add(L,R,C,ls);if(R > m) Add(L,R,C,rs);
}
void PushDownAll(int l,int r,int rt){if(l==r) {a[l]=ans[rt];return;}int m=(l+r)>>1;PushDown(rt);PushDownAll(ls);PushDownAll(rs);
}
int main(void)
{while(~scanf("%d",&n)){for(int i=1;i<=n;++i) scanf("%d",&a[i]);while(!s.empty()) s.pop();//初始化vl数组 for(int i=1;i<=n;++i){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();if(s.empty()) vl[i]=0;else vl[i]=s.top();s.push(i);}while(!s.empty()) s.pop();//初始化vr数组 for(int i=n;i>=1;--i){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();if(s.empty()) vr[i]=n+1;else vr[i]=s.top();s.push(i);}build(1,n,1);//初始化线段树 for(int i=1;i<=n;++i){Add(1,vr[i]-vl[i]-1,a[i],1,n,1);//操作 }PushDownAll(1,n,1);//下传所有标记并将结果存入a[i] for(int i=1;i<=n;++i){//输出答案 printf("%d",a[i]);if(i==n) printf("\n");else printf(" ");}}
return 0;
}方法二代码(4000KB 108ms)：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <cstring>
#define maxn 200007
using namespace std;
int n;
int a[maxn];
int vl[maxn];
int vr[maxn];
stack<int> s;
int ans[maxn];
int main(void)
{while(~scanf("%d",&n)){for(int i=1;i<=n;++i) scanf("%d",&a[i]);while(!s.empty()) s.pop();//初始化vl数组 for(int i=1;i<=n;++i){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();if(s.empty()) vl[i]=0;else vl[i]=s.top();s.push(i);}while(!s.empty()) s.pop();//初始化vr数组 for(int i=n;i>=1;--i){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();if(s.empty()) vr[i]=n+1;else vr[i]=s.top();s.push(i);}memset(ans,0,sizeof(ans));for(int i=1;i<=n;++i){int maxLen=vr[i]-vl[i]-1;ans[maxLen]=max(ans[maxLen],a[i]);}for(int i=n-1;i>0;--i) ans[i]=max(ans[i],ans[i+1]);for(int i=1;i<=n;++i){//输出答案 printf("%d",ans[i]);if(i==n) printf("\n");else printf(" ");}}
return 0;
}
这篇关于CodeForces 547B. Mike and Feet 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
