玄关:站外题(二维树状数组)求条
  • 板块学术版
  • 楼主llamn
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/15 17:50
  • 上次更新2024/5/15 17:54:02
查看原帖
玄关:站外题(二维树状数组)求条
1038651
llamn楼主2024/5/15 17:50

给出一个 n×mn×m的零矩阵 AA ,你需要完成如下操作:

  • 1 a b c d k:表示左上角为 (a,b)(a,b) ,右下角为 (c,d)(c,d) 的子矩阵内所有数都自增 kk
  • 2 x y:表示询问元素Ax,yA_{x,y} 的值

样例输入:

2 2
1 1 1 2 2 5
1 1 2 2 2 -3
2 1 1
2 1 2
2 2 1
2 2 2

样例输出:

5
2
5
2

代码 (WA\textrm WA):

#include <cstdio>
#define eggy using
#define party namespace 
#define lb(x) ((x)&(-x))
eggy party std;
int i,j,k;
long long n,m,t[100];
long long c[4100][4100];
void add(long long x, long long y, long long v);
long long sum(long long x, long long y);
int main()
{
    /*return 0;*/
    scanf("%lld %lld",&n,&m);
    while(scanf("%d",&k) != EOF)
    {
        if (k == 1)
        {
            scanf("%lld %lld %lld %lld %lld",&t[2],&t[3],&t[4],&t[5],&t[6]); getchar();
            t[4]++; t[5]++;
            add(t[2],t[3],t[6]);
            add(t[2],t[5],0-t[6]);
            add(t[3],t[4],0-t[6]);
            add(t[4],t[5],t[6]);
        }
        else
        {
            scanf("%lld %lld",&t[2],&t[3]); getchar();
            printf("%lld\n",sum(t[2],t[3]) );
        }
    }
    return 0;
}
void add(long long x, long long y, long long v)
{
    for (i = x; i <= n; i += lb(i))
        for (j = y; j <= m; j += lb(j))
            c[i][j] += v;
}
long long sum(long long x, long long y)
{
    long long num = 0ll;
    for (i = x; i > 0; i -= lb(i))
        for (j = y; j > 0; j -= lb(j))
            num += c[i][j];
    return num;
}
2024/5/15 17:50
加载中...