二维树状数组板子,IDE显示运行是错误,求条
  • 板块灌水区
  • 楼主kind_Ygg
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/2 21:01
  • 上次更新2024/8/2 22:05:07
查看原帖
二维树状数组板子,IDE显示运行是错误,求条
926886
kind_Ygg楼主2024/8/2 21:01
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=(1<<11)+5;
char str[10];
int n,m;//长宽
int dx,dy,fx,fy,val;//左上端点横纵坐标 右下端点横纵坐标 矩阵加的值 
int t1[N][N],t2[N][N];
int t3[N][N],t4[N][N];
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int y,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		for(int j=y;j<=m;j+=lowbit(j))
		{
			t1[i][j]+=val;
			t2[i][j]+=i*val;
			t3[i][j]+=j*val;
			t4[i][j]+=i*j*val;
		}
	}
}
int sum(int x,int y)
{
	int ans=0;
	int xx=x+1;
	int yy=y+1;
	for(int i=x;i;i-=lowbit(i))
	{
		for(int j=y;j;j-=lowbit(j))
		{
			ans+=t1[i][j]*xx*yy-t2[i][j]*yy-t3[i][j]*xx+t4[i][j];
		}
	}
	return ans;
}
signed main()
{
	cin>>str>>n>>m;
	while(scanf("%s%lld%lld%lld%lld",str,dx,dy,fx,fy)!=EOF)
	{
		if(str=="L")
		{
			cin>>val;
			update(dx,dy,val);
			update(dx,fy+1,-val);
			update(fx+1,dy,-val);
			update(fx+1,fy+1,val);
		}
		else
			cout<<sum(fx,fy)-sum(dx-1,fy)-sum(fx,dy-1)+sum(dx-1,dy-1)<<'\n';
	}
	return 0;
}

LinkLink

2024/8/2 21:01
加载中...