华企在线网站建设,网站充值这么做,榆中建设投资有限公司网站,wordpress html地图正题
题目链接:https://www.luogu.com.cn/problem/CF5E 题目大意
圆上有nnn个山#xff0c;两个山之间可以看到当且仅当它们之间的两条弧中有一条满足所有山都不高于它们两个。
求可以看到的山的对数。 3≤n≤106,1≤hi≤1093\leq n\leq 10^6,1\leq h_i\leq 10^93≤n≤106,…正题
题目链接:https://www.luogu.com.cn/problem/CF5E 题目大意
圆上有nnn个山两个山之间可以看到当且仅当它们之间的两条弧中有一条满足所有山都不高于它们两个。
求可以看到的山的对数。
3≤n≤106,1≤hi≤1093\leq n\leq 10^6,1\leq h_i\leq 10^93≤n≤106,1≤hi≤109 解题思路
先找到最高的山然后先考虑它之外的点对再考虑这座山的贡献因为这样矮的点之间肯定有一座高山挡着。
然后前后各维护一个单调队列每个元素被弹出的时候就会统计一个点对。
然后考虑相同的情况对于前后中的一个做的时候弹完之后在单调队列上二分相同的位置即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int n,m,mx,top,a[N],b[N],s[N],v[N];
long long ans;
int main()
{scanf(%d,m);mx1;for(int i1;im;i){scanf(%d,b[i]);if(b[i]b[mx])mxi;}for(int imx1;im;i)a[n]b[i];for(int i1;imx;i)a[n]b[i];for(int i1;in;i){while(top0a[s[top]]a[i])top--,ans;int l1,rtop;while(lr){int mid(lr)1;if(a[s[mid]]a[i])rmid-1;else lmid1;}anstop-r;s[top]i;}top0;for(int in;i1;i--){while(top0a[s[top]]a[i])top--,ans;s[top]i;}for(int i1,z0;in;i)if(a[i]z)za[i],ans!v[i],v[i]1;for(int in,z0;i1;i--)if(a[i]z)za[i],ans!v[i],v[i]1;printf(%lld\n,ans);return 0;
}
