4 棵树状数组爆零求调
查看原帖
4 棵树状数组爆零求调
232460
xiaoqian02楼主2022/12/1 21:51

样例输出就不对,一直输出 0,但又一直看不出来哪里错了。

#include<bits/stdc++.h>
using namespace std;
int n,m,p,l,r,s,t;
char c;
int tr1[2055][2055],tr2[2055][2055],tr3[2055][2055],tr4[2055][2055];
int lowbit(int x)
{
	return x&(-x);
}
void update1(int x,int y,int p)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j)) tr1[i][j]+=p;
	return;
}
void update2(int x,int y,int p)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j)) tr2[i][j]+=p;
	return;
}
void update3(int x,int y,int p)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j)) tr3[i][j]+=p;
	return;
}
void update4(int x,int y,int p)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j)) tr4[i][j]+=p;
	return;
}
void update(int a,int b,int c,int d,int p)
{
	update1(b+1,d+1,p);
	update1(a,d+1,-p);
	update1(b+1,c,-p);
	update1(a,c,p);
	update2(b+1,d+1,p*(b+1));
	update2(a,d+1,-p*a);
	update2(b+1,c,-p*(b+1));
	update2(a,c,p*a);
	update3(b+1,d+1,p*(d+1));
	update3(a,d+1,-p*(d+1));
	update3(b+1,c,-p*c);
	update3(a,c,p*c);
	update4(b+1,d+1,p*(b+1)*(d+1));
	update4(a,d+1,-p*(d+1)*a);
	update4(b+1,c,-p*c*(b+1));
	update4(a,c,p*a*c);
	return;
}
int qzh1(int x,int y)
{
	int sm=0;
	for(int i=x;i>=1;i-=lowbit(i))
		for(int j=y;j>=1;j-=lowbit(j)) sm+=tr1[i][j];
	return sm;
}
int qzh2(int x,int y)
{
	int sm=0;
	for(int i=x;i>=1;i-=lowbit(i))
		for(int j=y;j>=1;j-=lowbit(j)) sm+=tr2[i][j];
	return sm;
}
int qzh3(int x,int y)
{
	int sm=0;
	for(int i=x;i>=1;i-=lowbit(i))
		for(int j=y;j>=1;j-=lowbit(j)) sm+=tr3[i][j];
	return sm;
}
int qzh4(int x,int y)
{
	int sm=0;
	for(int i=x;i>=1;i-=lowbit(i))
		for(int j=y;j>=1;j-=lowbit(j)) sm+=tr4[i][j];
	return sm;
}
int qzh(int x,int y)
{
	return qzh4(x,y)-(x+1)*qzh3(x,y)-(y+1)*qzh2(x,y)+(x+1)*(y+1)*qzh1(x,y);
}
int query(int a,int b,int c,int d)
{
	return qzh(b,d)-qzh(a-1,d)-qzh(b,c-1)+qzh(a-1,c-1);
}
int main()
{
	cin>>c;
	cin>>n>>m;
	while(cin>>c)
	{
        cin>>l>>r>>s>>t;
		if(c=='L')
		{
			cin>>p;
			update(l,r,s,t,p);
		}
		else cout<<query(l,r,s,t)<<endl;
	}
    return 0;
}
2022/12/1 21:51
加载中...