POJ-1195 Mobile phones 二维树状数组


  前面用二维线段树写了个,代码长不说,而且效率还慢的要死!!!!! Orz......

  这题如果用树状数组来解的话,代码量很小而且速度很快。二维树状数组就在循环上面再加一层循环。

  代码如下:

#include <cstdlib>
#include
<cstdio>
#include
<cstring>
#define LOWBIT( x ) (x) & -(x)
using namespace std;

int rec[1040][1040], N;

inline
void CinInt( int &t )
{
char f = 1, c;
while( c = getchar(), c < '0' || c > '9' || c == '-' )
{
if( c == '-' )
f
= -1;
}
t
= c - '0';
while( c = getchar(), c >= '0' && c <= '9' )
t
= t * 10 + c -'0';
t
= t * f;
}

inline
void CinStr( char *s )
{
int p = -1;
char c;
while( c = getchar(), c == ' ' || c == '\n' ) ;
s[
++p] = c;
while( c = getchar(), c != ' ' && c != '\n' )
s[
++p] = c;
s[
++p] = '\0';
}

inline
void CinDou( double &d )
{
d
= 0;
long long t = 0;
int bit = 0;
char c;
while( c = getchar(), ( c < '0' || c > '9' ) && c != '.' ) ;
if( c != '.' )
{
t
= c - '0';
while( c = getchar(), c >= '0' && c <= '9' && c != '.' )
t
= t * 10 + c - '0';
}
if( c == '.' )
{
while( c = getchar(), c >= '0' && c <= '9' )
{
d
= d * 10 + c - '0';
bit
++;
}
}
while( bit-- )
d
/= 10;
d
+= t;
}

inline
void modify( int x, int y, int add )
{
for( int i = x; i <= N; i += LOWBIT( i ) )
{
for( int j = y; j <= N; j += LOWBIT( j ) )
rec[i][j]
+= add;
}
}

inline
int query( int x, int y )
{
int ans = 0;
for( int i = x; i > 0; i -= LOWBIT( i ) )
{
for( int j = y; j > 0; j -= LOWBIT( j ) )
ans
+= rec[i][j];
}
return ans;
}

int main()
{
int op;
while( scanf( "%d", &op ), op != 3 )
{
switch( op )
{
case 0:
{
scanf(
"%d", &N );
break;
}
case 1:
{
int x, y, add;
scanf(
"%d %d %d", &x, &y, &add );
// CinInt( x ), CinInt( y ), CinInt( add );
modify( x + 1, y + 1, add );
break;
}
case 2:
{
int sx, ex, sy, ey;
scanf(
"%d %d %d %d", &sx, &sy, &ex, &ey );
// CinInt( sx ), CinInt( sy ), CinInt( ex ), CinInt( ey );
printf( "%d\n", query( ex + 1, ey + 1 ) - query( ex + 1, sy ) - query( sx, ey + 1 ) + query( sx, sy ) );
break;
}
}
}
return 0;
}

  该题还有奇怪的现象就是加了输入外挂后时间竟然增加了。

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告