题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2120
写裸数据结构题最开心啦~~~
维护一下与每个位置颜色一样的前面和后面最近的数，不存在则设为无穷，然后每次查询就等价于查询该区间后缀大于r的数有多少个，然后就各种BST暴力维护就可以啦。
代码（差点就超时了。。。）：
d788d43f8794a4c2817d01480cf41bd5ad6e3973.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std ;
#define MAXN 10010
#define inf 0x7fffffff
#define MAXC 1000100
#define MAXV 500010
#define L( t ) t -> left
#define R( t ) t -> right
#define K( t ) t -> key
#define S( t ) t -> size
#define update( t )S( t )=S(L( t ))+S(R( t ))+1
#define lowbit( t )((- t )& t )
struct SBT{
struct node{
node *left ,*right ;
int key , size ;
}*roof ,*null ;
SBT( ){
roof = null =new( node );
S( null )=0,L( null )=R( null )= null ;
}
void left( node*&t ){
node *k =R( t );
R( t )=L( k );update( t );
L( k )= t ;update( k );
t = k ;
}
void right( node*&t ){
node *k =L( t );
L( t )=R( k );update( t );
R( k )= t ;update( k );
t = k ;
}
void maintain( node*&t ){
if(S(L(L( t )))>S(R( t ))){
right( t );
maintain(R( t ));maintain( t );
return;
}
if(S(R(L( t )))>S(R( t ))){
left(L( t ));right( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
if(S(R(R( t )))>S(L( t ))){
left( t );
maintain(L( t ));maintain( t );
return;
}
if(S(L(R( t )))>S(L( t ))){
right(R( t ));left( t );
maintain(L( t )),maintain(R( t ));maintain( t );
return;
}
}
void Insert(int k , node*&t ){
if( t == null ){
t =new( node );
L( t )=R( t )= null ,S( t )=1,K( t )= k ;
return;
}
Insert( k , k <K( t )?L( t ):R( t ));
update( t );maintain( t );
}
void Delete(int k , node*&t ){
if( k ==K( t )){
if(L( t )== null ){
node *u = t ;
t =R( t );
delete( u );
return;
}else if(R( t )== null ){
node *u = t ;
t =L( t );
delete( u );
return;
}else{
right( t );
Delete( k ,R( t ));
}
}else Delete( k , k <K( t )?L( t ):R( t ));
update( t );maintain( t );
}
int rank(int k , node *t ){
if( t == null )return 0;
return k <K( t )?rank( k ,L( t ))+S(R( t ))+1:rank( k ,R( t ));
}
void Push(int k ){
Insert( k , roof );
}
void Erase(int k ){
Delete( k , roof );
}
int Rank(int k ){
return rank( k , roof );
}
} sbt[ MAXN ];
set <int> rbt[ MAXC ];
int n , m , a[ MAXN ], suff[ MAXN ];
void Insert_bit(int pos ,int k ){
for(int i = pos ; i <= n ; i +=lowbit( i )) sbt[ i ].Push( k );
}
void Delete_bit(int pos ,int k ){
for(int i = pos ; i <= n ; i +=lowbit( i )) sbt[ i ].Erase( k );
}
int Rank_bit(int pos ,int k ){
int rec =0;
for(int i = pos ; i ; i -=lowbit( i )) rec += sbt[ i ].Rank( k );
return rec ;
}
int main( ){
scanf("%d%d",&n ,&m );
for(int i =0; i ++< n ;)scanf("%d",&a[ i ]);
for(int i =0; i ++< MAXC -1;){
rbt[ i ].clear( );
rbt[ i ].insert(- inf ), rbt[ i ].insert( inf );
}
for(int i =0; i ++< n ;) rbt[ a[ i ]].insert( i );
for(int i =0; i ++< n ;) suff[ i ]=*(++ rbt[ a[ i ]].lower_bound( i ));
for(int i =0; i ++< n ;)Insert_bit( i , suff[ i ]);
while( m --){
int ch , l , r ;for( ch =getchar( );!( ch =='Q'|| ch =='R'); ch =getchar( ));
if( ch =='Q'){
scanf("%d%d",&l ,&r );
printf("%d\n",Rank_bit( r , r )-Rank_bit( l -1, r ));
}else{
scanf("%d%d",&l ,&r );
int k =*(-- rbt[ a[ l ]].lower_bound( l ));
if( k >- inf ){
Delete_bit( k , suff[ k ]);
Insert_bit( k , suff[ k ]= suff[ l ]);
}
rbt[ a[ l ]].erase( l );
Delete_bit( l , suff[ l ]);
a[ l ]= r ;
rbt[ r ].insert( l );
set <int>:: iterator u = rbt[ r ].lower_bound( l );
k =*(-- u );
if( k >- inf ){
Delete_bit( k , suff[ k ]);
Insert_bit( k , suff[ k ]= l );
}
suff[ l ]=*(++ rbt[ r ].lower_bound( l ));
Insert_bit( l , suff[ l ]);
}
}
return 0;
}
网友评论