Codeforces Contest 1156 E Special Segments of Permutation —— 分治

本文主要是介绍Codeforces Contest 1156 E Special Segments of Permutation —— 分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你n个数，每个数都是1-n之间且没有两个数相同，一个区间是特殊的如果它的左端点的值+右端点的值=这个区间中最大的值。问你有多少个特殊的区间。

题解：

我看到data structure就在想线段树，CDQ当然也想过，想不出来。问了一下别人，她用一下子就想出来了，非常的敢单，反思一下自己还是太习惯套路了，都没有怎么用别的方法去做过。那么这道题就是for一遍从大到小查询每个数所负责的最大值的区间即可，每进来一个数都会讲一个区间划分为2个，我们每次查小的那一个就好了，时间复杂度最多是n/2+n/4+n/4+n/8+n/8+n/8+n/8+…在用一个set，时间复杂度是$O(n/2\ast logn\ast logn)$吧。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],pos[N];
set<int>st;
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;st.insert(0),st.insert(n+1);int ans=0;for(int i=n;i>=1;i--){int p=pos[i];set<int>::iterator it=st.upper_bound(p);it--;int l=*it+1;int r=*st.lower_bound(p)-1;if(p-l>r-p){for(int j=p+1;j<=r;j++){int res=i-a[j];if(l<=pos[res]&&pos[res]<p)ans++;}}else{for(int j=l;j<p;j++){int res=i-a[j];if(p<pos[res]&&pos[res]<=r)ans++;}}st.insert(pos[i]);}printf("%d\n",ans);return 0;
}

这篇关于Codeforces Contest 1156 E Special Segments of Permutation —— 分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---