题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1062
首先把每个云抽象成一个点(x,y)，表示该云在mod 2len意义下到达最左端的时间为x和长度为y，那么我们发现统计的时候可以补成统计两块平行四边形的点，那么坐标转一下，对于每个平行四边形，分别把坐标轴旋转45度，这样就变成了矩形，可以方便的用BIT统计了。
代码（细节超多，注意边界的重复）：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
const int maxc = 1010000 ;
const int maxl = 1005 ;
struct BIT {
int N , M , T[ maxl * 2 ][ maxl * 5 ] ;
inline void Init( int _N , int _M ) {
N = _N , M = _M ;
rep( i , N ) rep( j , M ) T[ i ][ j ] = 0 ;
}
#define lowbit( x ) ( ( - x ) & x )
inline void add( int x , int y , int v ) {
for ( int i = x ; i <= N ; i += lowbit( i ) ) {
for ( int j = y ; j <= M ; j += lowbit( j ) ) {
T[ i ][ j ] += v ;
}
}
}
inline int query( int x , int y ) {
int sum = 0 ;
for ( int i = x ; i ; i -= lowbit( i ) ) {
for ( int j = y ; j ; j -= lowbit( j ) ) {
sum += T[ i ][ j ] ;
}
}
return sum ;
}
inline int Query( int lx , int rx , int ly , int ry ) {
if ( lx > rx || ly > ry ) return 0 ;
int rec = query( rx , ry ) + query( lx - 1 , ly - 1 ) ;
int ret = query( lx - 1 , ry ) + query( rx , ly - 1 ) ;
return rec - ret ;
}
} bit[ 2 ] ;
int n , len , cl[ maxc ][ 2 ] ;
inline void trans0( int &x , int &y ) {
y = y - x ; x ++ , y += 3 * len ;
}
inline void trans1( int &x , int &y ) {
y = x + y ; x ++ , y += ( len + 1 ) ;
}
inline void change0( int x , int y , int v ) {
trans0( x , y ) ; bit[ 0 ].add( x , y , v ) ;
}
inline void change1( int x , int y , int v ) {
trans1( x , y ) ; bit[ 1 ].add( x , y , v ) ;
}
inline void modify( int t , int c , int l , int r , int d ) {
int x = ( t - d * l + len * 2 ) % ( len * 2 ) ;
int y = r - l ;
cl[ c ][ 0 ] = x , cl[ c ][ 1 ] = y ;
change0( x , y , 1 ) , change1( x , y , 1 ) ;
}
inline int query( int t , int l , int r ) {
t %= ( len << 1 ) ;
int ans = 0 ;
if ( t >= r ) {
int lx = t - r , rx = t , ly = l - r , ry = len + r ;
trans0( lx , ly ) , trans0( rx , ry ) ;
ans += bit[ 0 ].Query( lx , rx , ly , ry ) ;
} else {
int lx = 0 , rx = t , ly = l - t , ry = len + r ;
trans0( lx , ly ) , trans0( rx , ry ) ;
ans += bit[ 0 ].Query( lx , rx , ly , ry ) ;
lx = 2 * len - ( r - t ) , rx = 2 * len - 1 ;
ly = l - r , ry = len + r - t - 1 ;
trans0( lx , ly ) , trans1( rx , ry ) ;
ans += bit[ 0 ].Query( lx , rx , ly , ry ) ;
}
if ( ! r ) return ans ;
if ( t + r < 2 * len ) {
int lx = t + 1 , rx = t + r , ly = l - 1 , ry = len ;
if ( r == len ) -- rx , ++ ry ;
trans1( lx , ly ) , trans1( rx , ry ) ;
ans += bit[ 1 ].Query( lx , rx , ly , ry ) ;
} else {
int lx , rx , ly , ry ;
if ( t + 1 < 2 * len ) {
lx = t + 1 , rx = 2 * len - 1 ;
ly = l - 1 , ry = r - len + t + 2 ;
trans1( lx , ly ) , trans1( rx , ry ) ;
ans += bit[ 1 ].Query( lx , rx , ly , ry ) ;
}
lx = 0 , rx = t + r - 2 * len ;
ly = l - 2 * len + t , ry = len ;
if ( r == len ) -- rx , ++ ry ;
trans1( lx , ly ) , trans1( rx , ry ) ;
ans += bit[ 1 ].Query( lx , rx , ly , ry ) ;
}
return ans ;
}
inline void Delete( int c ) {
int x = cl[ c ][ 0 ] , y = cl[ c ][ 1 ] ;
trans0( x , y ) ; bit[ 0 ].add( x , y , -1 ) ;
x = cl[ c ][ 0 ] , y = cl[ c ][ 1 ] ;
trans1( x , y ) ; bit[ 1 ].add( x , y , -1 ) ;
}
int main( ) {
scanf( "%d%d" , &n , &len ) ;
bit[ 0 ].Init( 2 * len , 5 * len ) , bit[ 1 ].Init( 2 * len , 5 * len ) ;
int type , t , l , r , d , c ;
rep( i , n ) {
scanf( "%d" , &type ) ;
switch ( type ) {
case 1 :
scanf( "%d%d%d%d%d" , &t , &c , &l , &r , &d ) ; modify( t , c , l , r , d ) ;
break ;
case 2 :
scanf( "%d%d%d" , &t , &l , &r ) ; printf( "%d\n" , query( t , l , r ) ) ;
break ;
case 3 :
scanf( "%d%d" , &t , &c ) ; Delete( c ) ;
break ;
}
}
return 0 ;
}
网友评论