【BZOJ 3132】上帝造题的七分钟 / 题解
BZOJ原题地址
洛谷原题地址
题面
写一个支持区间修改区间查询的二维数据结构。
请尝试自行推导公式。先放代码.
代码
#include
#define maxn 6000
using namespace std;
int n,m;
struct Bit{
int c[maxn][maxn];
int lb(int x){
return (x&-x);
}
void add(int x,int y,int z){
for (int i=x;i<=n;i+=lb(i)) for (int j="y;j<=m;j+=lb(j))" c[i][j]+="z;" } int qry(int x,int y){ r="0;" i="x;i;i-=lb(i))" r+="c[i][j];" return r; }a,b,c,d; void add(int y,int z){ a.add(x,y,z),b.add(x,y,z*x),c.add(x,y,z*y),d.add(x,y,z*x*y); a.qry(x,y)*(x+1)*(y+1)-b.qry(x,y)*(y+1)-c.qry(x,y)*(x+1)+d.qry(x,y); main(){ ios::sync_with_stdio(false); string x;cin>>X>>n>>m;
int a,b,x,y,T;
while(cin>>X){
cin>>a>>b>>x>>y;
if (X=="L"){
cin>>T;x++,y++;
Add(a,b,T),Add(x,y,T),Add(x,b,-T),Add(a,y,-T);
}
else{
a--,b--;
cout<
思路
用二维树状数组。
设原来的数组是 $a[i][j]$
有差分数组
公式挂掉了
区间加的时候,把一个区间拆成四个前缀区间,然后按定义维护$A,B,C,D$ 四个数组
求和直接用公式计算。