luogu1377 树的序（线段树）

题意：给你一个1~N的排列，然后让你按顺序把它们插到一个二叉搜索树里，然后问能插出同样的二叉搜索树的字典序最小的排列是什么

本来可以直接模拟建树然后dfs一下输出结果...然而有可能会退化成链，最差复杂度是O($n^2$)

然后貌似这题可以用笛卡尔树，先对输入排序然后实现O(n)建树..但我不会

考虑线段树做法，按照权值建线段树，维护区间中最小的序号

那我从根节点开始做（输入和输出的第一个数一定相同），每次找它左子树对应的权值区间范围中最小的序号，就是左子树的根；右子树同理

这样一直做下来，每做到一个数直接输出即可

复杂度是O(nlogn)

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 const int maxn=;

 int mi[maxn*],val[maxn],N;

 void insert(int p,int l,int r,int x,int y){

     if(l==r) mi[p]=y;

     else{

         int m=l+r>>;

         if(x<=m) insert(p<<,l,m,x,y);

         else insert(p<<|,m+,r,x,y);

         mi[p]=min(mi[p<<],mi[p<<|]);

     }

 }

 int query(int p,int l,int r,int x,int y){

     if(x<=l&&r<=y) return mi[p];

     else{

         int m=l+r>>;int re=0x3f3f3f3f;

         if(x<=m) re=min(query(p<<,l,m,x,y),re);

         if(y>m) re=min(query(p<<|,m+,r,x,y),re);

         return re;

     }

 }

 void solve(int x,int l,int r){

     if(x) printf("%d ",x);

     if(x>l+) solve(val[query(,,N,l+,x-)],l,x);

     if(x<r-) solve(val[query(,,N,x+,r-)],x,r);

 }

 int main(){

     int i,j,k,p,root;

     scanf("%d",&N);

     memset(mi,,sizeof(mi));

     for(i=;i<=N;i++){

         scanf("%d",&j);val[i]=j;

         insert(,,N,j,i);

     }solve(,,N+);

 }

巴特西

luogu1377 树的序（线段树）

最新文章

热门文章

巴特西

luogu1377 树的序 （线段树）

最新文章

热门文章

luogu1377 树的序（线段树）