点击打开SPOJ 1029
思路: 二维树状数组
分析:
1 简单的二维树状数组,注意因为数据量很大TLE了多次,之后把memset改成for循环A了
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1100;
int n;
int mat[MAXN][MAXN];
int treeNum[MAXN][MAXN];
int lowbit(int x){
return x&(-x);
}
void add(int x , int y , int val){
for(int i = x ; i < MAXN ; i += lowbit(i))
for(int j = y ; j < MAXN ; j += lowbit(j))
treeNum[i][j] += val;
}
long long getSum(int x , int y){
long long ans = 0;
for(int i = x ; i > 0 ; i -= lowbit(i))
for(int j = y ; j > 0 ; j -= lowbit(j))
ans += treeNum[i][j];
return ans;
}
void solve(){
char str[10];
int x , y , val;
int x1 , y1 , x2 , y2;
while(scanf("%s" , str) && str[0] != 'E'){
if(str[1] == 'E'){
scanf("%d%d%d%*c" , &x , &y , &val);
add(x+1 , y+1 , val-mat[x+1][y+1]);
mat[x+1][y+1] = val;
}
else{
scanf("%d%d%d%d%*c" , &x1 , &y1 , &x2 , &y2);
x1++ , y1++ , x2++ , y2++;
long long ans = getSum(x2 , y2);
ans -= getSum(x1-1 , y2);
ans -= getSum(x2 , y1-1);
ans += getSum(x1-1 , y1-1);
printf("%lld\n" , ans);
}
}
}
int main(){
int cas;
scanf("%d" , &cas);
while(cas--){
scanf("%d%*c" , &n);
for(int i = 0 ; i <= n ; i++)
for(int j = 0 ; j <= n ; j++)
treeNum[i][j] = mat[i][j] = 0;
solve();
}
return 0;
}
分享到:
相关推荐
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ-Solutions:SPOJ算法问题的解决方案
My solution for some spoj problems
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
SPOJ( )上选定问题的解决方案
联系 Python中SPOJ问题的解决方案。
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
spoj MSTS kruskal +生成树
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
cp:一些SPOJ问题的解决方案
gcd(a,b)= d (d为素数,1,1)