请求放大时限
查看原帖
请求放大时限
242524
JRzyh楼主2020/6/26 12:11

这题不开O2没发过,开了最后两点也会MLE,并且题目描述也不对,计算过程会爆long long

如果我错了,求帮忙卡常:

#include<bits/stdc++.h>
#define x1 x_1
#define y1 y_1
using namespace std;
int n,m;
class BIT
{
	private:
		#define lowbit(x) ((x)&-(x))
		long long t[2050][2050];
	public:
		void plus(int x,int y,long long val)
		{
			for(int i=x;i<=n;i+=lowbit(i))
			{
				for(int j=y;j<=m;j+=lowbit(j))
				{
					t[i][j]+=val;
				} 	
			} 
		}
		long long query(int x,int y)
		{
			long long res=0;
			for(int i=x;i>=1;i-=lowbit(i))
			{
				for(int j=y;j>=1;j-=lowbit(j))
				{
					res+=t[i][j];
				}
			}
			return res;
		}
}tree[4];
void add(int x,int y,int num)
{
	tree[0].plus(x,y,num);
	tree[1].plus(x,y,num*x);
	tree[2].plus(x,y,num*y);
	tree[3].plus(x,y,num*x*y);
}
long long ans(int x,int y)
{
	return tree[0].query(x,y)*(x*y+x+y+1)-
		   tree[1].query(x,y)*(y+1)-
		   tree[2].query(x,y)*(x+1)+
		   tree[3].query(x,y);
}
char opt;
int x1,x2,y1,y2,num;
int main()
{
	scanf("X %d %d",&n,&m);
	while(cin>>opt)
	{
		switch(opt)
		{
			case 'L':
			{
				scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&num);
				add(x1,y1,num);
				add(x1,y2+1,-num);
				add(x2+1,y1,-num);
				add(x2+1,y2+1,num);
				break;
			}
			case 'k':
			{
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				printf("%lld\n",ans(x2,y2)-ans(x1-1,y2)-ans(x2,y1-1)+ans(x1-1,y1-1));
				break;
			}
		}
	}
	return 0;
}
2020/6/26 12:11
加载中...