CF1156E Special Segments of Permutation

思路：笛卡尔树？（好像并不一定要建出来，但是可以更好理解）

提交：2次

错因：没有判左右儿子是否为空来回溯导致它T了

题解：

建出笛卡尔树，考虑如何计算答案：

先预处理每一个值出现的位置 \(pos[]\)；

对于每一个有左右儿子的点，设他在原序列中的值为 \(mx\)，根据笛卡尔树的性质，他比自己的子树中的任何一个元素都大。这样，我们遍历他的轻儿子中的元素 \(vl\) ，查询 \(pos[mx-vl]\) 是否在重子树中。

其实可以不建树，直接求出每个点作为最大值能够向左右扩展的区间，枚举小的区间就够了。

复杂度 \(O(nlogn)\) ，原因是类似树剖，每个点最多只会向上跳 \(logn\) 条轻边；而一个点被计算，只有在枚举轻子树的时候；其实类似dsu on tree。

当然，不建树的做法的复杂度虽然解释不同，但本质都是一样的、

代码：

#include<bits/stdc++.h>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

} const int N=250010;

int n,rt,a[N],pos[N],ans;

struct node {int ls,rs,sz,l,r;} t[N];

#define ls(tr) t[tr].ls

#define rs(tr) t[tr].rs

#define sz(tr) t[tr].sz

#define l(tr) t[tr].l

#define r(tr) t[tr].r

int stk[N],top;

inline void calc(int tr,int rn,int mx) {

  for(R i=l(tr);i<=r(tr);++i)

    ans+=(pos[mx-a[i]]>=l(rn)&&pos[mx-a[i]]<=r(rn));

}

inline void dfs(int tr) {

  sz(tr)=1,l(tr)=r(tr)=tr;

  if(ls(tr)) dfs(ls(tr)),l(tr)=l(ls(tr));

  if(rs(tr)) dfs(rs(tr)),r(tr)=r(rs(tr));

  if(!ls(tr)||!rs(tr)) return ;

  sz(tr)=sz(ls(tr))+sz(rs(tr));

  if(sz(ls(tr))<sz(rs(tr))) calc(ls(tr),rs(tr),a[tr]);

  else calc(rs(tr),ls(tr),a[tr]);

}

inline void main() {

  n=g(); for(R i=1;i<=n;++i) a[i]=g(),pos[a[i]]=i;

  stk[++top]=0,a[0]=1e9;

  for(R i=1;i<=n;++i) { R lst=0;

    while(a[stk[top]]<a[i]) lst=stk[top],--top;

    ls(i)=lst,rs(stk[top])=i; stk[++top]=i;

  } rt=stk[2];

  dfs(rt); printf("%d\n",ans);

}

} signed main() {Luitaryi::main(); return 0;}

2019.09.15

61

巴特西

CF1156E Special Segments of Permutation

思路：笛卡尔树？（好像并不一定要建出来，但是可以更好理解）

提交：2次

错因：没有判左右儿子是否为空来回溯导致它T了

题解：

代码：

最新文章

热门文章