好久没写博客了.....
这段时间狂补一下
题目大意：
给定一个(n*n)的全0矩阵，每次有两种操作：
(L a b c d delta) 表示将左上角((a,b))，右下角((c,d))的矩阵加(delta)
(k a b c d) 表示求左上角((a,b))，右下角((c,d))的矩阵的和并输出
其中操作数(le 10^5)，(n le 2048)
(此题卡空间，所以不要开(long long))
qwq既然是套路题，就直接说了
这个题考察的主要是二维树状数组
首先，类比一维，二维的树状数组(c[i][j])表示，第(i)行 向上 (lowbit(i))行，第(j)列，向左(lowbit(j))列的和是多少。
那么修改也就显而易见了
struct BIT{
int c[maxn][maxn];
void modify(int x,int y,int p)
{
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=m;j+=lowbit(j))
{
c[i][j]+=p;
}
}
int query(int x,int y)
{
int ans=0;
for (int i=x;i;i-=lowbit(i))
{
for (int j=y;j;j-=lowbit(j))
{
ans=ans+c[i][j];
}
}
return ans;
}
};
然后，我们来考虑怎么实现区间加呢？
一维的时候，我们运用的是差分的思想
那么我们对于二维，不妨使用(d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i][j])
那么我们对于修改一个((x1,y1)->(x2,y2))的矩阵，我们只需要让(d[x1][y1]+=delta,d[x1][y2+1]-=delta,d[x2+1][y1]-=delta,d[x2+1][y2+1]+=delta)
就可以轻松完成了qwq
那....要是用差分数组，求和貌似就需要一点学问啊
对于求一个((1,1)->(x,y))的矩阵的和
就是
[ans = sum_{i=1}^{x} sum_{j=1}^{y}sum_{h=1}^{i} sum_{k=1}^{j} d[h][k]
]
我们可以通过计算每个d的出现次数
来化简这个式子
[ans = sum_{i=1}^{x} sum_{j=1}^{y} d[i][j]*(x-i+1)*(y-j+1)
]
然后最终的式子就是
[sum_{i=1}^{x} sum_{j=1}^{y} d[i][j]*(xy+x+y+1) - d[i][j]*i*(y+1)-d[i][j]*j*(x+1)+d[i][j]*i*j
]
那么我们只需要维护四个树状数组，就OK了
直接上代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 2051;
int lowbit(int x)
{
return (x & (-x));
}
int n,m;
struct BIT{
int c[maxn][maxn];
void modify(int x,int y,int p)
{
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=m;j+=lowbit(j))
{
c[i][j]+=p;
}
}
int query(int x,int y)
{
int ans=0;
for (int i=x;i;i-=lowbit(i))
{
for (int j=y;j;j-=lowbit(j))
{
ans=ans+c[i][j];
}
}
return ans;
}
};
BIT ymh,ymhi,ymhj,ymhij;
char s[10];
int x1,x2,yy,y2;
void add(int x,int y,int p)
{
ymh.modify(x,y,p);
ymhi.modify(x,y,p*x);
ymhj.modify(x,y,p*y);
ymhij.modify(x,y,p*x*y);
}
int sum(int x,int y)
{
return ymh.query(x,y)*(x*y+x+y+1)-ymhi.query(x,y)*(y+1)-ymhj.query(x,y)*(x+1)+ymhij.query(x,y);
}
signed main()
{
scanf("%s",s+1);
n=read(),m=read();
while (scanf("%s",s+1)!=EOF)
{
int p;
if (s[1]=='L')
{
x1=read(),yy=read(),x2=read(),y2=read();
p=read();
add(x1,yy,p);
add(x1,y2+1,-p);
add(x2+1,yy,-p);
add(x2+1,y2+1,p);
}
else
{
x1=read(),yy=read(),x2=read(),y2=read();
printf("%d
",sum(x2,y2)-sum(x2,yy-1)-sum(x1-1,y2)+sum(x1-1,yy-1));
}
}
return 0;
}