ZOJ 2112 Dynamic Rankings

這里是題目地址

其實就是帶修改的區間第K大。

寫了一下BIT套主席樹，內存飛起，似乎需要特別的優化技巧 = =?所以還是寫了一下線段樹套平衡樹，跑了1s左右。

其實線段樹套平衡樹就是歸并樹的自然擴展而已。

歸并樹是把歸并排序的過程建成一顆線段樹，每個節點是一個數組，存的是這個節點對應區間的元素的正序：

空間復雜度O( n log n ) 。

每次查詢的時候二分答案，問題轉化成詢問區間中有多少個數比k小。外層查詢和一般的線段樹一樣，只是在線段樹的節點處需要再次二分得到節點區間中比k小的數的個數。這樣二分答案有一個log ，線段樹中詢問也需要一個log ，線段樹節點處二分需要一個log ，每次詢問的復雜度為O( log^3 n ) 。

加入修改操作的時候，只需要把線段樹節點的數組改為平衡樹實現就好了。這是很自然的，線段樹節點維護對應節點的順序，又要支持修改，顯然平衡樹符合要求。

平衡樹用splay實現了一下跑了1080ms ，然后用Treap實現了一下RE得渾身難受。。。實在是碼力不行啊Orz

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std ;
  5 const int N = 50000 +10 ,INF = ~1u>>1;
  6 int M ,num[N] ;
  7 struct node{
  8     node *ch[2] ,*p ;
  9     int size ,val ;
 10     bool d() ;
 11     void setc( node * ,bool ) ,rol() ,pushup() ;
 12 }pool[N*19] ,*cur ,NU ,*null = &NU ;
 13 bool node::d(){
 14     return p->ch[1] == this ;
 15 }
 16 void node::setc( node *c ,bool d ){
 17     ch[d] = c ,c->p = this ;
 18 }
 19 void node::rol(){
 20     node *s = p ;
 21     int dd = d() ;
 22     s->p->setc( this ,p->d() ) ;
 23     s->setc( ch[!dd] ,dd ) ;
 24     setc( s ,!dd ) ;
 25     s->pushup() ;
 26 }
 27 void node::pushup(){
 28     size = ch[0]->size + ch[1]->size + 1 ;
 29 }
 30 struct Splay{
 31     node *root ;
 32     void splay( node * ,node * ) ,insert( node * ) ;
 33     void change( int ,int ) ,find( int ) ,init() ;
 34     node *get( int ) ;
 35     int rank( int ) ;
 36 }tree[N<<2] ;
 37 
 38 node *newnode( int val ){
 39     cur->val = val ;
 40     cur->size = 1 ;
 41     cur->ch[0] = cur->ch[1] = cur->p = null ;
 42     return cur ++ ;
 43 }
 44 void Splay::init(){
 45     root = newnode(-INF) ;
 46 }
 47 void Splay::splay( node *x ,node *p = null ){
 48     while( x->p != p ){
 49         if( x->p->p != p )
 50             x->d() == x->p->d() ? x->p->rol() : x->rol() ;
 51         x->rol() ;
 52     }
 53     x->pushup() ;
 54     if( p == null ) root = x ;
 55 }
 56 void Splay::insert( node *x ){
 57     if( root == null ) root = x ,root->p = null ;
 58     else for( node *t = root ;; ){
 59         ++t->size ;
 60         node *&s = t->ch[ x->val > t->val ] ;
 61         if( s == null ){
 62             s = x ,s->p = t ;
 63             splay( x ) ;
 64             break ;
 65         }
 66         t = s ;
 67     }
 68 }
 69 void Splay::find( int x ){
 70     for( node *t = root ;; ){
 71         if( x == t->val ){
 72             splay( t ) ;
 73             return ;
 74         }
 75         t = t->ch[ x > t->val ] ;
 76     }
 77 }
 78 void Splay::change( int x ,int val ){
 79     find( x ) ;
 80     node *p = root ;
 81     node *t = get( root->ch[0]->size ) ;
 82     splay( t ,root ) ;
 83     t->setc( root->ch[1] ,1 ) ;
 84     t->pushup() ,root = t ,t->p = null ;
 85     p->val = val ,p->size = 1 ;
 86     p->ch[0] = p->ch[1] = null ;
 87     insert( p ) ;
 88     return ;
 89 }
 90 node *Splay::get( int s ){
 91     for( node *t = root ;; ){
 92         int k = t->ch[0]->size ;
 93         if( s == k + 1 ) return t ;
 94         if( s > k + 1 ) s -= k + 1 ,t = t->ch[1] ;
 95         else t = t->ch[0] ;
 96     }
 97 }
 98 int Splay::rank( int x ){
 99     int res = 0 ;
100     for( node *t = root ;; ){
101         node *&s = t->ch[ x > t->val ] ;
102         if( t->val < x ) res += t->ch[0]->size + 1 ;
103         if( s == null ){
104             splay(t) ;
105             return res - 1 ;
106         }
107         t = s ;
108     }
109 }
110 void setIt( int p ,int k ,int s = M ,int x = 1 ){
111     tree[x].insert( newnode(k) ) ;
112     if( s == 1 ) return ;
113     if( p <= s/2 ) setIt( p ,k ,s/2 ,x<<1 ) ;
114     else setIt( p - s/2 ,k ,s - s/2 ,x<<1|1 ) ;
115 }
116 void change( int p ,int u ,int v ,int s = M ,int x = 1 ){
117     tree[x].change( u ,v ) ;
118     if( s == 1 ) return ;
119     if( p <= s/2 ) change( p ,u ,v ,s/2 ,x<<1 ) ;
120     else change( p-s/2 ,u ,v ,s-s/2 ,x<<1|1 ) ;
121 }
122 int Q ;
123 void query( int l ,int r ,int ans ,int s = M ,int x = 1 ){
124     if( l <= 1 && r >= s ){
125         Q += tree[x].rank(ans) ;
126         return ;
127     }
128     if( l <= s/2 ) query( l ,r ,ans ,s/2 ,x<<1 ) ;
129     if( r > s/2 ) query( l-s/2 ,r-s/2 ,ans ,s-s/2 ,x<<1|1 ) ;
130 }
131 bool judge( int l ,int r ,int ans ,int kth ){
132     Q = 0 ;
133     query( l ,r ,ans ) ;
134     if( Q <= kth - 1 ) return 1;
135     return 0 ;
136 }
137 void init(){
138     cur = pool ;
139 }
140 void build( int x = 1 ,int s = M ){
141     tree[x].init() ;
142     if( s == 1 ) return ;
143     build( x<<1 ,s/2 ) ;
144     build( x<<1|1 ,s-s/2 ) ;
145 }
146 int main(){
147     int n ,m ,x ,s ,t ,u ;
148     int T ;
149     scanf( "%d" ,&T ) ;
150     while( T -- ){
151         scanf("%d %d" ,&n ,&m ) ;
152         M = n ;
153         init() ;
154         int minn = 0 ,maxn = 0 ;
155         build();
156         for( int i = 1 ;i <= n ;i ++ ){
157             scanf( "%d" ,&x ) ;
158             num[i] = x ;
159             setIt( i ,x ) ;
160             minn = min ( minn ,x ) ;
161             maxn = max ( maxn ,x ) ;
162         }
163         char o[2];
164         while( m -- ){
165             scanf( "%s" ,&o ) ;
166             if( o[0] == 'C' ){
167                 scanf( "%d %d" ,&s ,&t ) ;
168                 minn = min( minn ,t ) ;
169                 maxn = max( maxn ,t ) ;
170                 change( s ,num[s] ,t ) ;
171                 num[s] = t ;
172                 continue ;
173             }
174             scanf( "%d %d %d" ,&s ,&t ,&u ) ;
175             int l = minn ,r = maxn ;
176             while( l < r ){
177                 int mid = ( l + r >> 1 ) + 1 ;
178                 if( judge( s ,t ,mid ,u ) ) l = mid ;
179                 else r = mid - 1 ;
180             }
181             printf( "%d\n" ,l ) ;
182         }
183     }
184 }

CODE

轉載于:https://www.cnblogs.com/MyWither/p/3563779.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273854.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273854.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273854.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！