题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3249
官方题目和数据：http://www.ioi2013.org/competition/tasks/
刚开始以为怎么这么一道傻叉数据结构题怎么没有什么人去写，不就一裸线段树套线段树，或者线段树（动态建树）套平衡树，还是平衡树套平衡树还是线段树神马的啊，然后就开始狂码上半天sgt+splay，交上去，果断TLE，然后又试了各种常数优化，IO优化神马的都上了，还要跑了260s+（交了好几次，差不多总共TLE了5次，卡20min左右，BZOJ上的同学们对不起啊），BZOJ的时限只有250s，最后无语的把splay改成SBT一次就A了，快了一倍左右。（Splay树的巨大常数说多了都是泪啊。。。以后不是那种要翻转的区间维护我是不会写splay的就是了。。。）
NOI官网上的IOI题解里大神的题解说是trie套trie，太神奇实在没想通，trie树居然还有这种神奇功能（孤陋寡闻啊我）。
代码（百度空间脑残了，贴不了这么长的高亮代码，贴代码的功能高亮又不知道哪里去了。。。QaQ）：
c75c10385343fbf25afdea4bb27eca8064388f81.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXN 3000100
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define Gcd( t ) Gcd[ t ]
#define Max( t ) Max[ t ]
#define Min( t ) Min[ t ]
#define V( t ) value[ t ]
#define K( t ) key[ t ]
#define S( t ) size[ t ]
#define inf 0x7fffffff
#define ll long long
void getint( int &t ) {
int ch ; for ( ch = getchar( ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t *= 10 , t += ch - '0' ;
}
void getll( ll &t ) {
int ch ; for ( ch = getchar( ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t *= 10 , t += ch - '0' ;
}
int ans[ 20 ] ;
void putll( ll t ) {
if ( ! t ) putchar( '0' ) ; else {
ans[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
while ( ans[ 0 ] ) putchar( '0' + ans[ ans[ 0 ] -- ] ) ;
}
putchar( '\n' ) ;
}
struct Pos {
int x , y ;
bool operator < ( const Pos &a ) const {
return y < a.y || ( y == a.y && x < a.x ) ;
}
bool operator == ( const Pos &a ) const {
return x == a.x && y == a.y ;
}
bool operator > ( const Pos &a ) const {
return y > a.y ||( y == a.y && x > a.x ) ;
}
} key[ MAXN ] , Max[ MAXN ] , Min[ MAXN ] ;
Pos make( int _x , int _y ) {
Pos u ; u.x = _x , u.y = _y ;
return u ;
}
int left[ MAXN ] , right[ MAXN ] , size[ MAXN ] , Node = 0 ;
ll value[ MAXN ] , Gcd[ MAXN ] ;
ll gcd( ll x , ll y ) {
if ( x < y ) swap( x , y ) ;
ll k ;
while ( y ) {
k = y ;
y = x % y ;
x = k ;
}
return x ;
}
void update( int t ) {
if ( ! t ) return ;
Gcd( t ) = gcd( gcd( Gcd( L( t ) ) , Gcd( R( t ) ) ) , V( t ) ) ;
S( t ) = S( L( t ) ) + S( R( t ) ) + 1 ;
Max( t ) = R( t ) ? Max( R( t ) ) : K( t ) ;
Min( t ) = L( t ) ? Min( L( t ) ) : K( t ) ;
}
void left_ratote( int &t ) {
int k = R( t ) ;
R( t ) = L( k ) ; update( t ) ;
L( k ) = t ; update( k ) ;
t = k ;
}
void right_ratote( 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_ratote( t ) ;
maintain( R( t ) ) ; maintain( t ) ;
return ;
}
if ( S( R( R( t ) ) ) > S( L( t ) ) ) {
left_ratote( t ) ;
maintain( L( t ) ) ; maintain( t ) ;
return ;
}
if ( S( R( L( t ) ) ) > S( R( t ) ) ) {
left_ratote( L( t ) ) ; right_ratote( t ) ;
maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;
return ;
}
if ( S( L( R( t ) ) ) > S( L( t ) ) ) {
right_ratote( R( t ) ) ; left_ratote( t ) ;
maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;
return ;
}
}
void Insert( Pos k , ll v , int &t ) {
if ( ! t ) {
t = ++ Node ;
S( t ) = 1 , L( t ) = R( t ) = 0 , V( t ) = Gcd( t ) = v , K( t ) = Max( t ) = Min( t ) = k ;
return ;
}
if ( k == K( t ) ) {
V( t ) = v ; update( t ) ; return ;
}
Insert( k , v , k < K( t ) ? L( t ) : R( t ) ) ;
update( t ) ; maintain( t ) ;
}
ll query( Pos l , Pos r , int t ) {
if ( ! t ) return 0 ;
if ( ! ( Min[ t ] < l ) && ! ( Max[ t ] > r ) ) return Gcd( t ) ;
if ( r < K( t ) ) return query( l , r , L( t ) ) ;
if ( l > K( t ) ) return query( l , r , R( t ) ) ;
ll rec = V( t ) ;
if ( l < K( t ) ) rec = gcd( rec , query( l , Max[ L( t ) ] , L( t ) ) ) ;
if ( r > K( t ) ) rec = gcd( rec , query( Min[ R( t ) ] , r , R( t ) ) ) ;
return rec ;
}
struct Node_sgt {
Node_sgt *left , *right ;
int roof ;
} *sgt , *null = new( Node_sgt ) ;
void Init_sgt_sbt( ) {
sgt = null -> left = null -> right = null , null -> roof = 0 ;
L( 0 ) = R( 0 ) = S( 0 ) = V( 0 ) = Gcd( 0 ) = 0 , Max( 0 ) = make( - inf , - inf ) , Min( 0 ) = make( inf , inf ) ;
}
void Change( int l , int r , int x , int y , ll v , Node_sgt *&t ) {
if ( t == null ) {
t = new( Node_sgt ) ;
t -> left = t -> right = null , t -> roof = 0 ;
}
Insert( make( x , y ) , v , t -> roof ) ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
if ( x <= mid ) Change( l , mid , x , y , v , t -> left ) ; else
Change( mid + 1 , r , x , y , v , t -> right ) ;
}
ll Query( int l , int r , int x0 , int y0 , int x1 , int y1 , Node_sgt *t ) {
if ( l == x0 && r == x1 ) return query( make( x0 , y0 ) , make( x1 , y1 ) , t -> roof ) ;
int mid = ( l + r ) >> 1 ;
if ( x1 <= mid ) return Query( l , mid , x0 , y0 , x1 , y1 , t -> left ) ;
if ( x0 > mid ) return Query( mid + 1 , r , x0 , y0 , x1 , y1 , t -> right ) ;
return gcd( Query( l , mid , x0 , y0 , mid , y1 , t -> left ) , Query( mid + 1 , r , mid + 1 , y0 , x1 , y1 , t -> right ) ) ;
}
int n , m , q ;
int main( ) {
Init_sgt_sbt( ) ;
getint( n ) , getint( m ) , getint( q ) ;
while ( q -- ) {
int x ; getint( x ) ;
if ( x == 1 ) {
int px , py ; ll pv ; getint( px ) , getint( py ) ; getll( pv ) ;
Change( 0 , n - 1 , px , py , pv , sgt ) ;
} else {
int x0 , x1 , y0 , y1 ; getint( x0 ) , getint( y0 ) , getint( x1 ) , getint( y1 ) ;
putll( Query( 0 , n - 1 , x0 , y0 , x1 , y1 , sgt ) ) ;
}
}
return 0 ;
}
网友评论