asp access 手机站 用于做微网站,seo服务,属于网站开发的动态服务器,写网页的素材图片这里是题目地址 其实就是带修改的区间第K大。 写了一下BIT套主席树#xff0c;内存飞起#xff0c;似乎需要特别的优化技巧 所以还是写了一下线段树套平衡树#xff0c;跑了1s左右。 其实线段树套平衡树就是归并树的自然扩展而已。 归并树是把归并排序的过程建成一颗线段树…这里是题目地址 其实就是带修改的区间第K大。 写了一下BIT套主席树内存飞起似乎需要特别的优化技巧 所以还是写了一下线段树套平衡树跑了1s左右。 其实线段树套平衡树就是归并树的自然扩展而已。 归并树是把归并排序的过程建成一颗线段树每个节点是一个数组存的是这个节点对应区间的元素的正序 空间复杂度O( n log n ) 。 每次查询的时候二分答案 问题转化成询问区间中有多少个数比k小。外层查询和一般的线段树一样只是在线段树的节点处需要再次二分得到节点区间中比k小的数的个数。这样二分答案有一个log 线段树中询问也需要一个log 线段树节点处二分需要一个log 每次询问的复杂度为O( log^3 n ) 。 加入修改操作的时候只需要把线段树节点的数组改为平衡树实现就好了。这是很自然的线段树节点维护对应节点的顺序又要支持修改显然平衡树符合要求。 平衡树用splay实现了一下跑了1080ms 然后用Treap实现了一下RE得浑身难受。。。实在是码力不行啊Orz 1 #include iostream2 #include cstring3 #include cstdio4 using namespace std ;5 const int N 50000 10 ,INF ~1u1;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[N2] ;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 ,x1 ) ;
114 else setIt( p - s/2 ,k ,s - s/2 ,x1|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 ,x1 ) ;
120 else change( p-s/2 ,u ,v ,s-s/2 ,x1|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 ,x1 ) ;
129 if( r s/2 ) query( l-s/2 ,r-s/2 ,ans ,s-s/2 ,x1|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( x1 ,s/2 ) ;
144 build( x1|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
