bzoj 2770 堆的中序遍历性质

我们知道二叉搜索树的中序遍历是一个已经排好序的序列，知道序列我们无法确定树的形态（因为有多种）。

但是，Treap如果告诉我们它的关键字以及权值，那么就可以唯一确定树的形态（Treap的O(logn)的期望时间复杂度就是依靠一个随机堆的深度不会太深）

具体的，已知关键字序列：k1,k2,k3...kn和优先级序列：p1,p2,p3,...pn，

如果我们想要找ki的父亲，只需要找“左边第一个p比它大的和右边第一个p比它大的中，p较小的那个“

至于lca(ki,kj)，是对应的pi~pj中的最小值（因为是小根堆）

至于深度，多次找父亲，路径长度就是深度，然后画一下图可以发现轨迹的特点，然后就可以搞了（求两段递增子序列长度）

 /**************************************************************

     Problem: 2770

     User: idy002

     Language: C++

     Result: Accepted

     Time:6140 ms

     Memory:46124 kb

 ****************************************************************/

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 #define oo 0x6FFFFFFF

 #define maxn 400010

 using namespace std;

 typedef pair<int,int> dpr;

 struct Node {

     int lf, rg, mid;

     dpr st;

     bool leaf;

     Node *ls, *rs;

 } pool[maxn*], *tail=pool, *root;

 vector<Node*> stk;

 int disc[maxn], ntot;

 int sv[maxn];

 int pr[maxn][];

 Node *build( int lf, int rg ) {

     Node *nd = ++tail;

     nd->lf=lf, nd->rg=rg, nd->mid=(lf+rg)>>;

     if( lf==rg ) {

         nd->st = dpr( oo,  );

         nd->leaf = true;

     } else {

         nd->ls = build( lf, nd->mid );

         nd->rs = build( nd->mid+, rg );

         nd->st = dpr( oo,  );

         nd->leaf = false;

     }

     return nd;

 }

 dpr qu_min( Node *nd, int lf, int rg ) {

     if( lf <= nd->lf && nd->rg <= rg ) return nd->st;

     dpr rt = dpr( oo,  );

     if( lf <= nd->mid )

         rt = qu_min( nd->ls, lf, rg );

     if( rg > nd->mid )

         rt = min( rt, qu_min( nd->rs, lf, rg ) );

     return rt;

 }

 void pushup( Node *nd ) {

     nd->st = min( nd->ls->st, nd->rs->st );

 }

 void modify( Node *nd, int pos, int val ) {

     if( nd->leaf ) {

         nd->st = dpr( val, pos );

         return;

     }

     if( pos <= nd->mid )

         modify( nd->ls, pos, val );

     else

         modify( nd->rs, pos, val );

     pushup( nd );

 }

 int lca( int u, int v ) {

     if( u>v ) swap(u,v);

     return qu_min( root, u, v ).second;

 }

 int main() {

     int n, m, T;

     scanf( "%d%d", &n, &m );

     T = n+m;

     for( int i=; i<=n; i++ ) {

         pr[i][] = ;

         scanf( "%d", pr[i]+ );

         disc[++ntot] = pr[i][];

     }

     for( int i=; i<=n; i++ )

         scanf( "%d", pr[i]+ );

     for( int i=n+; i<=T; i++ ) {

         char opt[];

         scanf( "%s", opt );

         pr[i][] = opt[]=='I' ?  :

                    opt[]=='D' ?  : ;

         if( pr[i][]== ) {

             scanf( "%d%d", pr[i]+, pr[i]+ );

             disc[++ntot] = pr[i][];

         } else if( pr[i][]== ) {

             scanf( "%d", pr[i]+ );

         } else {

             scanf( "%d%d", pr[i]+, pr[i]+ );

         }

     }

     sort( disc+, disc++ntot );

     ntot = unique( disc+, disc++ntot ) - disc - ;

     for( int i=; i<=T; i++ ) {

         pr[i][] = lower_bound( disc+, disc++ntot, pr[i][] )-disc;

         if( pr[i][]== )

             pr[i][] = lower_bound( disc+, disc++ntot, pr[i][] )-disc;

     }

     root = build( , ntot );

     for( int i=; i<=T; i++ ) {

         if( pr[i][]== ) {

             modify( root, pr[i][], pr[i][] );

         } else if( pr[i][]== ) {

             modify( root, pr[i][], oo );

         } else {

             int u = pr[i][];

             int v = pr[i][];

             printf( "%d\n", disc[lca(u,v)] );

         }

     }

 }

巴特西

bzoj 2770 堆的中序遍历性质

最新文章

热门文章