luogu1377 树的序（线段树）

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

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

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

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

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

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

复杂度是O(nlogn)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<vector>
 6 using namespace std;
 7 const int maxn=100100;
 8 
 9 int mi[maxn*4],val[maxn],N;
10 
11 void insert(int p,int l,int r,int x,int y){
12     if(l==r) mi[p]=y;
13     else{
14         int m=l+r>>1;
15         if(x<=m) insert(p<<1,l,m,x,y);
16         else insert(p<<1|1,m+1,r,x,y);
17         mi[p]=min(mi[p<<1],mi[p<<1|1]);
18     }
19 }
20 int query(int p,int l,int r,int x,int y){
21     if(x<=l&&r<=y) return mi[p];
22     else{
23         int m=l+r>>1;int re=0x3f3f3f3f;
24         if(x<=m) re=min(query(p<<1,l,m,x,y),re);
25         if(y>m) re=min(query(p<<1|1,m+1,r,x,y),re);
26         return re;
27     }
28 }
29 
30 void solve(int x,int l,int r){
31     if(x) printf("%d ",x);
32     if(x>l+1) solve(val[query(1,1,N,l+1,x-1)],l,x);
33     if(x<r-1) solve(val[query(1,1,N,x+1,r-1)],x,r);
34 }
35 
36 int main(){
37     int i,j,k,p,root;
38     scanf("%d",&N);
39     memset(mi,127,sizeof(mi));
40     for(i=1;i<=N;i++){
41         scanf("%d",&j);val[i]=j;
42         insert(1,1,N,j,i);
43     }solve(0,0,N+1);
44     
45 }

luogu1377 树的序 （线段树）

luogu1377 树的序（线段树）