前面用二维线段树写了个,代码长不说,而且效率还慢的要死!!!!! 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;
}
该题还有奇怪的现象就是加了输入外挂后时间竟然增加了。
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。