题解 - Vijos

2

我不懂你们在骚什么好吧，二维树状数组？线段树？（黑人问号）
就直接维护前缀和啊
10000*1000又不会t
代码简单多少

#include<iostream>
#include<cstdio>
using namespace std;
long long sum[1026][1026];
int main()
{
int n;
cin>>n;
int m;
cin>>m;
while (m!=3)
{
int ans=0;
if (m==1)
{
int x,y,k;
cin>>x>>y>>k;
x++;
y++;
for (int i=y;i<=n;i++) sum[x][i]+=k;
}
if (m==2)
{
int x,y,_x,_y;
cin>>x>>y>>_x>>_y;
x++;
y++;
_x++;
_y++;
for (int i=_x;i>=x;i--) ans+=sum[i][_y];
for (int i=_x;i>=x;i--) ans-=sum[i][y-1];
printf("%d\n",ans);
}
scanf("%d",&m);
}
//for (int i=0;i<=n;i++,cout<<endl)
// for (int j=0;j<=n;j++) cout<<sum[i][j]<<" ";
}

1

zenmehuiyourenjiaolizhen LV 6 @ 7 年前

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

int main()
{
int n;
cin >> n;

int **range=new int*[n];
for (int i = 0; i < n; i++)
range[i] = new int[n];

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
range[i][j] = 0;
while (1)
{
int judge;
cin >> judge;
if (judge == 1)
{
//printf("输入1\n");
int x, y, z;
cin >> x >> y >> z;
range[x][y] += z;
//cout << range[x][y];
}
if (judge == 2)
{
//printf("输入2\n");
int a, b, c, d; int sum = 0;
cin >> a >> b >> c >> d;

for (int i = a; i <= c; i++)
for (int j = b; j <= d; j++)
sum += range[i][j];
cout << sum << endl;
}
if (judge == 3)
{

system("pause");
return 0;
}
}

}

1

Sky1231 (sky1231) LV 10 @ 8 年前

Vijos本题(SuperBrother打鼹鼠)Code

#include <cstdio>
#include <cstring>
#define rs 1024
using namespace std;

int c[rs+2][rs+2];

void add_1(int x,int y,int data,int s)
{
    for (int i=x;i<=s;i+=i&-i)
        for (int j=y;j<=s;j+=j&-j)
            c[i][j]+=data;
}

int sum_1(int x,int y)
{
    int ans=0;
    for (int i=x;i>0;i-=i&-i)
        for (int j=y;j>0;j-=j&-j)
            ans+=c[i][j];
    return ans;
}

int ask_1(int x1,int y1,int x2,int y2)
{
    int sum_c[5];
    sum_c[1]=sum_1(x2,y2),sum_c[2]=sum_1(x1-1,y1-1),sum_c[3]=sum_1(x1-1,y2),sum_c[4]=sum_1(x2,y1-1);
    return sum_c[1]+sum_c[2]-sum_c[3]-sum_c[4];
}

int main()
{
    int o,s,x,y,d,l,b,r,t;
    memset(c,0,sizeof(c));
    scanf("%d",&s);
    while (1)
    {
        scanf("%d",&o);
        if (o==1)
        {
            scanf("%d%d%d",&x,&y,&d);
            x++,y++;
            add_1(x,y,d,s);
        }
        else if (o==2)
        {
            scanf("%d%d%d%d",&l,&b,&r,&t);
            l++,b++,r++,t++;
            printf("%d\n",ask_1(l,b,r,t));
        }
        else if (o==3)
            break;
    }
}

Poj原题(Mobile phones)Code
http://poj.org/problem?id=1195

#include <cstdio>
#include <cstring>
#define rs 1024
using namespace std;

int c[rs+2][rs+2];

void add_1(int x,int y,int data,int s)
{
    for (int i=x;i<=s;i+=i&-i)
        for (int j=y;j<=s;j+=j&-j)
            c[i][j]+=data;
}

int sum_1(int x,int y)
{
    int ans=0;
    for (int i=x;i>0;i-=i&-i)
        for (int j=y;j>0;j-=j&-j)
            ans+=c[i][j];
    return ans;
}

int ask_1(int x1,int y1,int x2,int y2)
{
    int sum_c[5];
    sum_c[1]=sum_1(x2,y2),sum_c[2]=sum_1(x1-1,y1-1),sum_c[3]=sum_1(x1-1,y2),sum_c[4]=sum_1(x2,y1-1);
    return sum_c[1]+sum_c[2]-sum_c[3]-sum_c[4];
}

int main()
{
    int o,s,x,y,d,l,b,r,t;
    while (1)
    {
        scanf("%d",&o);
        if (o==0)
        {
            scanf("%d",&s);
            memset(c,0,sizeof(c));
        }
        else if (o==1)
        {
            scanf("%d%d%d",&x,&y,&d);
            x++,y++;
            add_1(x,y,d,s);
        }
        else if (o==2)
        {
            scanf("%d%d%d%d",&l,&b,&r,&t);
            l++,b++,r++,t++;
            printf("%d\n",ask_1(l,b,r,t));
        }
        else if (o==3)
            break;
    }
}

sky1231 @ 8 年前

不是一般的H2O

0

Goodhao LV 10 @ 8 年前

求矩形的时候犯了好几个BUG
1.直接用(0,0)-右下角的矩形减去(0,0)-左上角的矩形
2.左上角两个坐标都应该减1（画图就知道了）

0

205610760 LV 8 @ 8 年前

二维裸题。。记得要将下标＋1，否则当x or y==0时就完了。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;
#define lb(A) A&(-A)
int a[2000][2000];
int n,m,x1,y1,k,x2,y2;

void add(){
for(int i=x1+1;i<=n;i+=lb(i))
for(int j=y1+1;j<=n;j+=lb(j))
a[i][j]+=k;
}

int ask(int x,int y){
int ret=0;
for(int i=x+1;i;i-=lb(i))
for(int j=y+1;j;j-=lb(j))
ret+=a[i][j];
return ret;
}

int main(){
scanf("%d",&n);
while(scanf("%d",&m)==1&&m!=3){
if(m==1){
scanf("%d%d%d",&x1,&y1,&k);
add();
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1));
}
}
}

0

卡车cckk LV 7 @ 8 年前

#include<iostream>
#include<cstdio>
using namespace std;
int b[1025][1025];
int n = 0;
int lowbit(int a)
{
    return a&-a;
}
void add(int x,int y,int z)
{
    for (;x <= n;x= x + lowbit(x))
        for (;y <= n;y= y + lowbit(y))
        {
            b[x][y] = b[x][y] + z;
        }
}
int lll(int x, int y)
{
    int ans = 0;
    for (; x > 0; x=x - lowbit(x))
        for (; y > 0; y=y - lowbit(y))
        {
            ans += b[x][y];
        }
    return ans;
}
int main()
{
    scanf("%d",&n);/////修改为scanf
    while (1)
    {
        int m = 0;
        scanf("%d",&m);
        if (m == 3)break;
        else if(m == 1)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x+1, y+1, z);
        }
        else if (m == 2)
        {
            int x, y, xx,yy;
            scanf("%d%d%d%d", &x, &y, &xx, &yy);
            printf("%d\n", lll(xx+1, yy+1) - lll(x, yy+1)-lll(xx+1,y)+lll(x,y));
        }
    }
    return 0;
}

请问哪里错了！QAQ

0

wangzhongtao LV 9 @ 8 年前

随机数据就是水，一维树状数组都能过
n其实没什么卵用
#include<cstdio>
using namespace std;

const int maxn=1050;
int c[maxn][maxn],a[maxn],n,ans;

inline int lowbit(int x) { return x&(-x); }

void add(int v,int x,int d)
{
while ( x<=n) {
c[v][x]+=d;
x+=lowbit(x);
}
}

int sum(int v,int x)
{
int ans=0;
while (x>0) {
ans+=c[v][x];
x-=lowbit(x);
}
return ans;
}

int main()
{

scanf("%d",&n);
int m;
for (;;) {
scanf("%d",&m);
if (m==1) {
int x,y,k; scanf("%d%d%d",&x,&y,&k);
add(x+1,y+1,k);
}
if (m==2) {
int x1,y1,x2,y2,ans=0;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for (int i=x1+1;i<=x2+1;++i) {
ans+=sum(i,y2+1)-sum(i,y1);
}
printf("%d\n",ans);
}
if (m==3) break;
}
return 0;
}

0

starli LV 10 @ 9 年前

二维树状数组把所有的坐标都+1
然后左下角为(x1,y1),右上角为(x2,y2)的矩阵即为 (0,0)(x2,y2)-(0,0)(x1,y2-1)-(0,0)(x2,y1-1)+(0,0)(x1-1,y1-1)
注意不要涉及到0 ,求sum的时候不要复制上边的然后忘记改+-和大小等于号23333
接下来是代码

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1200][1200],n,m;

void add(int x,int y,int d){
for(int i=y;i<=n;i+=i&-i)
for(int j=x;j<=n;j+=j&-j) a[i][j]+=d;
}

int sum(int x,int y){
int ret=0;
for(int i=y;i;i-=i&-i)
for(int j=x;j;j-=j&-j) ret+=a[i][j];
return ret;
}

int main(){
scanf("%d",&n);
while(scanf("%d",&m)!=EOF){
if(m==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);x++,y++;
add(x,y,k);
}
else if(m==2){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;y1++,x2++,y2++;
printf("%d\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));
}else break;
}
return 0;
}

0

wang_yanheng LV 10 @ 9 年前

二维树状数组。坐标全部+1，因为树状数组从1开始存储

//Vijos P1512
#include <stdio.h>
#include <string.h>

int tree[1030][1030];
int size = 0;

int lowbit(int index);
void clear(void);
void add(int x, int y, int delta);
int Max(int a, int b);
int sumFromOrigin(int x, int y);
int sumRect(int x1, int y1, int x2, int y2);

int main(){
int cmd, x1, y1, x2, y2, n;

scanf("%d", &size);
clear();
while(scanf("%d", &cmd)!=EOF){
if(cmd==1){
scanf("%d %d %d", &x1, &y1, &n);
x1++, y1++;
add(x1, y1, n);
}else if(cmd==2){
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
x1++, y1++, x2++, y2++;
printf("%d\n", sumRect(x1, y1, x2, y2));
}else if(cmd==3){
return 0;
}
}

return 0;
}
int lowbit(int index){
return ((index-1)^index)&index;
}
void clear(){
int x, y;
for(x=0; x<=size; x++){
for(y=0; y<=size; y++)
tree[x][y] = 0;
}
}
void add(int x, int y, int delta){
int i, k;
if(delta==0)
return;
for(i=x; i<=size; i+=lowbit(i)){
for(k=y; k<=size; k+=lowbit(k))
tree[i][k] += delta;
}
}
int sumFromOrigin(int x, int y){
int i, k;
int tmp = 0;
if(x<=0 || y<=0)
return 0;
for(i=x; i>0; i-=lowbit(i)){
for(k=y; k>0; k-=lowbit(k))
tmp += tree[i][k];
}
return tmp;
}
int sumRect(int x1, int y1, int x2, int y2){
return sumFromOrigin(x2, y2) - sumFromOrigin(x1-1, y2) - sumFromOrigin(x2, y1-1) + sumFromOrigin(x1-1, y1-1);
}

0

zjwlvu LV 8 @ 10 年前

逐一树状数组里最好不要牵涉到0，容易出错。。。
#include<cstdio>
#include<cstring>

using namespace std;

int N,tree[1025][1025];

inline int lowbit(int x)
{
return ((x)&(-x));
}

void update(int x,int y,int delta)
{
for(int i=x;i<=N;i+=lowbit(i))
for(int j=y;j<=N;j+=lowbit(j))
tree[i][j]+=delta;
}

int sum(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=tree[i][j];
return ans;
}

int query(int x1,int y1,int x2,int y2)
{
int ans=sum(x2,y2);
if (x1) ans-=sum(x1-1,y2);
if (y1) ans-=sum(x2,y1-1);
if (x1&&y1) ans+=sum(x1-1,y1-1);
return ans;
}

int main()
{
freopen("in.txt","r",stdin);
memset(tree,0,sizeof(tree));
scanf("%d",&N);
while (1)
{
int m;
scanf("%d",&m);
if (m==1)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
update(x+1,y+1,k);
}
else if (m==2)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",sum(x2+1,y2+1)+sum(x1,y1)-sum(x1,y2+1)-sum(x2+1,y1));
}
else if (m==3) return 0;
}
return -1;
}

0

Sanmee360 LV 8 @ 10 年前

var
i,n,m,x1,x2,y1,y2,x,y,k:longint;
a,c:array[1..1025,1..1025]of longint;
function lowbit(x:integer):longint;
begin
exit(x and-x);
end;
procedure modify(i,j:integer;aa:longint);
begin
inc(a[i,j],aa);
x:=i ;
while x<=n do
begin
y:=j;
while y<=n do
begin
inc(c[x,y],aa);
inc(y,lowbit(y));
end;
inc(x,lowbit(x))
end;
end;
function sum(i,j:longint):longint;
begin
sum:=0;
x:=i;
while x>0 do
begin
y:=j;
while y>0 do
begin
inc(sum,c[x,y]);
dec(y,lowbit(y));
end;
dec(x,lowbit(x));
end;
end;
begin
readln(n);
read(m);
while m<>3 do
begin
if m=1 then
begin
read(x,y,k);
x:=x+1;
y:=y+1;
modify(x,y,k);
end
else
begin
read(x1,y1,x2,y2);
inc(x2,1);inc(y2,1);
writeln(sum(x2,y2)+sum(x1,y1)-sum(x1,y2)-sum(x2,y1));
end;
read(m);
end;
end.

0

绿色的云 LV 10 @ 11 年前

第一次打树状数组好不容易A了
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
//#include <fstream>

using namespace std;

#define MAXN 1025

//ofstream fout("check.txt");

int t[MAXN][MAXN];
int Exp[31];

int Lowbit(int x){
return (x+(((~x)+1)&x));
}

int n;

int Add(int x,int y,int k){
int i=x;
while (i<=n){
int j=y;
while (j<=n){
t[i][j]+=k;
j=Lowbit(j);
}
i=Lowbit(i);
}
return 0;
}

int Find(int x){
int l=0,r=30;
while (1){
if (r-l==1){
return l;
}
if (Exp[l]==x){
return l;
}
if (Exp[r]==x){
return r;
}
int mid=(l+r)>>1;
if (Exp[mid]==x){
return mid;
}
if (Exp[mid]>x){
r=mid;
}
if (Exp[mid]<x){
l=mid;
}
}
}

int sum(int x,int y){
/* cout<<x<<" "<<y<<endl;
if (x==6&&y==8){
cout<<"!"<<endl;
}*/
int rec=0;
int i=0;
while (i<x){
i+=Exp[Find(x-i)];
int j=0;
while (j<y){
j+=Exp[Find(y-j)];
rec+=t[i][j];
}
}
return rec;
}
/*
void out(){
for (int i=0;i++<n;){
for (int j=0;j++<n;){
fout<<t[i][j]<<" ";
}
fout<<endl;
}
}
*/
int main(){
Exp[0]=1;
for (int i=0;i++<30;){
Exp[i]=Exp[i-1]*2;
}
memset(t,0,sizeof(t));
scanf("%d",&n);
while (1){
int m,x,y,k,h;
scanf("%d",&m);
if (m==3){
break;
}
if (m==1){
scanf("%d%d%d",&x,&y,&k);
Add(x+1,y+1,k);
}
if (m==2){
scanf("%d%d%d%d",&x,&y,&k,&h);
// out();
printf("%d\n",sum(k+1,h+1)-sum(x,h+1)-sum(k+1,y)+sum(x,y));
// fout<<sum(k+1,h+1)<<"-"<<sum(x,h+1)<<"-"<<sum(k+1,y)<<"-"<<sum(x,y)<<endl;
}
}
return 0;
}

0

银翼枪骑兵 LV 6 @ 12 年前

坑呐……左下角（0，0），我竟然在没看完题的情况下debug了半小时，泪奔……

0

尖端才子 LV 10 @ 15 年前

ZYM好强大！……SuperBrother好强大！

{---|---|---|---|---|---|以上为不和谐内容可以省略---|---|---|---|---|---|---|-}

这题让我想到了二维的树状数组……

{---|---|---|---|---|---|---|---|--}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

搞定……

0

yzl609271536 LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

2次AC的

0

wll969 LV 8 @ 15 年前

苦恼，本来准备做到睡觉的，结果一遍AC没事干了

0

芒果木瓜榴莲 LV 9 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

const filename='p1512';

var

c:array[1..1025,1..1025]of longint;

i,j,n,m,k,x,y,x1,y1,ans:longint;

function lowbit(x:longint):longint;

begin exit(x and(x xor (x-1)));end;

procedure add(x,y,k:longint);

var z:longint;

begin

while x0do

begin

inc(q,c[x,z]);

dec(z,lowbit(z));

end;

dec(x,lowbit(x));

end;

exit(q);

end;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(n);

while true do

begin

read(m);if m=3 then break;

if m=1 then

begin

read(x,y,k);

add(x+1,y+1,k);

end

else begin

ans:=0;read(x,y,x1,y1);

ans:=getsum(x1+1,y1+1)-getsum(x1+1,y)-getsum(x,y1+1)+getsum(x,y);

writeln(ans);

end;

end;

close(input);close(output);

end.

#include

#include

#define lowbit(x) (x&(x^(x-1)))

using namespace std;

long i,j,k,n,m,x,y,x1,y1,ans,c[1025][1025]={0};

void add(long x,long y,long k)

{

long i,j;

for(i=x;i0;j-=lowbit(j))

s+=c[i][j];

return(s);

}

int main(){

// freopen("p1512.in","r",stdin);

// freopen("p1512.out","w",stdout);

scanf("%ld",&n);

for (;

{

scanf("%ld",&m);

if (m==3) break;

if (m==1)

{

scanf("%ld%ld%ld",&x,&y,&k);

add(x+1,y+1,k);

}

if (m==2)

{

scanf("%ld%ld%ld%ld",&x,&y,&x1,&y1);

ans=getsum(x1+1,y1+1)-getsum(x1+1,y)-getsum(x,y1+1)+getsum(x,y);

printf("%ld\n",ans);

}

}

return 0;

}

第一道C++，在super brother神牛的帮助下，终于过了，强烈Orz

1、发现了C++和fp的一点点区别，如果用fp写，add过程和getsum函数要写超多行，但是用C++写只用几行，暂时理解中……

2、cin/cout比scanf/printf慢很多（我用cin/cout提交357ms），很多数据结构题最好不要用cin/cout。 ——lql_accept & gnoggnoyil

0

Matt LV 10 @ 15 年前

左下角（0，0）

（0，0）...

0

chen199277 LV 10 @ 15 年前

一遍AC，爽啊。

0

陈亮宇 LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC 感觉真好！蛤蛤

题解

71 条题解

SuperBrother打鼹鼠

信息

状态

开发

支持

题解

71 条题解

SuperBrother打鼹鼠

信息

状态

开发

支持

还没有账户？

登录