UESTC2021暑假前集训 (树状数组区间修改区间查询)

UESTC2021暑假前集训 (树状数组区间修改区间查询)

 

UESTC2021暑假前集训 (树状数组区间修改区间查询)

 

 

 UESTC2021暑假前集训 (树状数组区间修改区间查询)

 

 这篇博客说的很好了  高级树状数组——区间修改区间查询、二维树状数组 - 胡小兔 - 博客园 (cnblogs.com)

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 #include <stack>
 7 #include <vector>
 8 #include <iostream>
 9 #include "algorithm"
10 using namespace std;
11 typedef long long LL;
12 const int MAX=1005;
13 LL n,m,q,a1[MAX][MAX],a2[MAX][MAX],a3[MAX][MAX],a4[MAX][MAX];
14 inline LL read(){
15     LL an(0),x=1;char c=getchar();
16     while (c<'0' || c>'9'){if (c=='-') x=-1;c=getchar();}
17     while (c>='0' && c<='9'){an=an*10+c-'0';c=getchar();}
18     return x*an;
19 }
20 void update(LL x,LL y,LL z){
21     LL i,j;
22     for (i=x;i<=n;i+=(i&-i))
23         for (j=y;j<=m;j+=(j&-j))
24             a1[i][j]+=z,a2[i][j]+=z*x,a3[i][j]+=z*y,a4[i][j]+=z*x*y;
25 }
26 void range_up(LL xa,LL ya,LL xb,LL yb,LL w){
27     update(xa,ya,w);update(xa,yb+1,-w);
28     update(xb+1,ya,-w);update(xb+1,yb+1,w);
29 }
30 LL search(LL x,LL y){
31     LL i,j,an=0;
32     for (i=x;i>=1;i-=(i&-i))
33         for (j=y;j>=1;j-=(j&-j))
34             an+=(x+1)*(y+1)*a1[i][j]
35                 -(y+1)*a2[i][j]-(x+1)*a3[i][j]
36                 +a4[i][j];
37     return an;
38 }
39 LL range_se(LL xa,LL ya,LL xb,LL yb){
40     return search(xb,yb)-search(xa-1,yb)-search(xb,ya-1)+search(xa-1,ya-1);
41 }
42 int main(){
43     freopen ("k.in","r",stdin);
44     freopen ("k.out","w",stdout);
45     LL i,j,k,o,x;
46     LL x1,y1,x2,y2,num,t;
47     n=read(),m=read(),q=read();
48     memset(a1,0,sizeof(a1));
49     memset(a2,0,sizeof(a2));
50     memset(a3,0,sizeof(a3));
51     memset(a4,0,sizeof(a4));
52     for (i=1;i<=n;i++)
53         for (j=1;j<=m;j++){
54             x=read();
55             range_up(i,j,i,j,x);
56         }
57     while (q--){
58         t=read();
59         if (t==1){
60             x1=read(),y1=read(),x2=read(),y2=read(),num=read();
61             range_up(x1,y1,x2,y2,num);
62         }
63         else{
64             x1=read(),y1=read(),x2=read(),y2=read();
65             printf("%lld\n",range_se(x1,y1,x2,y2));
66         }
67     }
68     return 0;
69 }

 

上一篇:C++ memset 踩坑


下一篇:char 、char[]、char*、 const char*、string(无效的const char *到XXXX的转化)