郑州网站推,国外网站dns 地址禁止,西安网站建设招聘,江宁区建设工程质量监督站网站题目大意
有一个长度为 n n n的序列 h i h_i hi#xff0c;一段区间 [ l , r ] [l,r] [l,r]的有趣程度为这段区间上 h i h_i hi的最大值 \times 最小值 \times 区间长度。求所有区间中有趣程度的最大值#xff0c;输出这个最大值。
保证答案在 unsigned long long \t…题目大意
有一个长度为 n n n的序列 h i h_i hi一段区间 [ l , r ] [l,r] [l,r]的有趣程度为这段区间上 h i h_i hi的最大值 × \times ×最小值 × \times ×区间长度。求所有区间中有趣程度的最大值输出这个最大值。
保证答案在 unsigned long long \text{unsigned long long} unsigned long long的范围内。 1 ≤ n ≤ 2 × 1 0 6 , 1 ≤ h i ≤ 1 0 9 1\leq n\leq 2\times 10^6,1\leq h_i\leq 10^9 1≤n≤2×106,1≤hi≤109 题解
假设我们已经确定了区间的最小值 h i h_i hi那么对于包含 h i h_i hi的区间 [ l , r ] [l,r] [l,r]在保证区间中 h i h_i hi为最小值的情况下则区间长度肯定是越大越好因为取的数越多最大值只会增大或不变而区间长度只会增大有趣程度也就不断增大了。
也就是说对于每个 h i h_i hi求出以 h i h_i hi最小值的最大区间并用这个区间来更新答案即可。
那怎么求以 h i h_i hi最小值的最大区间呢用并查集可以解决。
我们可以按 h i h_i hi的值从大到小枚举 h i h_i hi对于一个 h i h_i hi如果 h i − 1 h_{i-1} hi−1在之前就被枚举过了那么显然其值是比 h i h_i hi大的其所在联通块的最小值也一定比 h i h_i hi大在连通块中的都是在之前被枚举过的 h h h值那么就将 h i h_i hi加入 h i − 1 h_{i-1} hi−1所在的连通块。对 h i 1 h_{i1} hi1也是如此。然后 h i h_i hi所在的连通块即为以 h i h_i hi最小值的最大区间用这个区间更新答案即可。
时间复杂度为 O ( n ⋅ α ( n ) ) O(n\cdot \alpha(n)) O(n⋅α(n))。
code
#includebits/stdc.h
using namespace std;
int n,v[2000005],id[2000005],fa[2000005],siz[2000005],z[2000005];
unsigned long long mn[2000005],mx[2000005];
unsigned long long ans0;
bool cmp(int ax,int bx){return v[ax]v[bx];
}
int find(int ff){if(fa[ff]!ff) fa[ff]find(fa[ff]);return fa[ff];
}
void pt(int x,int y){xfind(x);yfind(y);if(xy) return;fa[y]x;siz[x]siz[y];mn[x]min(mn[x],mn[y]);mx[x]max(mx[x],mx[y]);ansmax(ans,mx[x]*mn[x]*siz[x]);
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,v[i]);ansmax(ans,1ull*v[i]*v[i]);mn[i]mx[i]v[i];siz[i]1;fa[i]id[i]i;}sort(id1,idn1,cmp);for(int i1;in;i){int xid[i];z[x]1;if(z[x-1]) pt(x-1,x);if(z[x1]) pt(x1,x);}printf(%llu,ans);return 0;
}
