题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3343
看到q相当小，于是就偷懒了一下，手残地写了一下块状链套SBT，复杂度各种巨大:O(q log(sqrt(n)) sqrt(n)),居然还9s+卡过去了。。。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std ;
#define MAXN 2000100
#define MAXB 1100
#define L( t ) Left[ t ]
#define R( t ) Right[ t ]
#define K( t ) Key[ t ]
#define S( t ) Size[ t ]
#define update( t )S( t )=S(L( t ))+S(R( t ))+1
#define check( ch )( ch >='0'&& ch <='9')
void getint(int&t ){
int ch ;for( ch =getchar( );!check( ch ); ch =getchar( ));
t = ch -'0';
for( ch =getchar( );check( ch ); ch =getchar( )) t *=10, t += ch -'0';
}
int Left[ MAXN ], Right[ MAXN ], Key[ MAXN ], Size[ MAXN ], V =0;
void left(int&t ){
int k =R( t );
R( t )=L( k );update( t );
L( k )= t ;update( k );
t = k ;
}
void right(int&t ){
int k =L( t );
L( t )=R( k );update( t );
R( k )= t ;update( k );
t = k ;
}
void maintain(int&t ){
if(S(L(L( t )))>S(R( t ))){
right( 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(R(L( t )))>S(R( t ))){
left(L( t ));right( t );
maintain(L( t )),maintain(R( 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 ,int&t ){
if(! t ){
t =++ V ;
L( t )=R( t )=0;
S( t )=1,K( t )= k ;
return;
}
S( t )++;
Insert( k , k <K( t )?L( t ):R( t ));
maintain( t );
}
void Delete(int k ,int&t ){
if( k ==K( t )){
if(!L( t )){
t =R( t );return;
}
if(!R( t )){
t =L( t );return;
}
right( t );Delete( k ,R( t ));
}else Delete( k , k <K( t )?L( t ):R( t ));
update( t );
maintain( t );
}
int Rank(int k ,int t ){
if(! t )return 0;
if( k <=K( t ))return S(R( t ))+1+Rank( k ,L( t ));
return Rank( k ,R( t ));
}
int a[ MAXN ], block[ MAXN ], head[ MAXB ], tail[ MAXB ], roof[ MAXB ], C[ MAXB ];
int n , m , b =0;
int Query(int l ,int r ,int c ){
if( block[ l ]== block[ r ]){
int x = block[ l ];
if( head[ x ]== l && tail[ x ]== r )return Rank( c - C[ x ], roof[ x ]);
int cnt =0;
for(int i = l ; i <= r ; i ++)if( a[ i ]>= c - C[ x ]) cnt ++;
return cnt ;
}
int cnt =Query( l , tail[ block[ l ]], c )+Query( head[ block[ r ]], r , c );
for(int i = block[ l ]+1; i < block[ r ]; i ++){
cnt +=Rank( c - C[ i ], roof[ i ]);
}
return cnt ;
}
void Change(int l ,int r ,int c ){
if( block[ l ]== block[ r ]){
int x = block[ l ];
if( l == head[ x ]&& r == tail[ x ]){
C[ x ]+= c ;
return;
}
for(int i = l ; i <= r ; i ++){
Delete( a[ i ], roof[ x ]);
a[ i ]+= c ;
Insert( a[ i ], roof[ x ]);
}
return;
}
Change( l , tail[ block[ l ]], c ),Change( head[ block[ r ]], r , c );
for(int i = block[ l ]+1; i < block[ r ]; i ++){
C[ i ]+= c ;
}
}
int main( ){
memset( roof ,0,sizeof( roof ));
memset( C ,0,sizeof( C ));
L(0)=R(0)=S(0)=0;
getint( n ),getint( m );
for(int i =0; i ++< n ;)getint( a[ i ]);
b =int(sqrt( n ));
for(int i =0; i ++< b ;){
for(int j =( i -1)* b ; j ++< i * b ;){
block[ j ]= i ;
Insert( a[ j ], roof[ i ]);
}
head[ i ]=( i -1)* b +1, tail[ i ]= i * b ;
}
if( b * b < n ){
head[ b +1]= b * b +1, tail[ b +1]= n ;
for(int i = b * b ; i ++< n ;){
block[ i ]= b +1;
Insert( a[ i ], roof[ b +1]);
}
}
while( m --){
int ch , l , r , c ;
for( ch =getchar( );!( ch >='A'&& ch <='Z'); ch =getchar( ));
if( ch =='M'){
getint( l ),getint( r ),getint( c );
Change( l , r , c );
}else{
getint( l ),getint( r ),getint( c );
printf("%d\n",Query( l , r , c ));
}
}
return 0;
}
网友评论