求助
  • 板块灌水区
  • 楼主Otue
  • 当前回复19
  • 已保存回复19
  • 发布时间2021/11/29 19:08
  • 上次更新2023/11/3 23:16:29
查看原帖
求助
411727
Otue楼主2021/11/29 19:08

求大佬给予卡常之法!(在学校OJ上面一直TLE80)

相信不少大佬都知道这是什么题

我保证解法没问题,只是需要卡常

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int c1[2050][2050],c2[2050][2050],c3[2050][2050],c4[2050][2050];
inline int query(int x,int y){
	int ans=0;
	for(int i=x;i;i-=i&-i){
		for(int j=y;j;j-=j&-j){
			ans+=c1[i][j]*(x+1)*(y+1)-c2[i][j]*(y+1)-c3[i][j]*(x+1)+c4[i][j];
		}
	} 
	return ans;
}
inline void add(int x,int y,int z){
	for(int i=x;i<=n;i+=i&-i){
		for(int j=y;j<=m;j+=j&-j){
			c1[i][j]+=z;
			c2[i][j]+=z*x;
			c3[i][j]+=z*y;
			c4[i][j]+=z*x*y;
		}
	} 
}
inline int read(){
	char c=' ';
	int f=1,x=0;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1; 
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
signed main(){
	cin>>n>>m;
	int flag;
	while(cin>>flag){
		
		int a,b,c,d,x;
		if(flag==1){
			a=read();
			b=read();
			c=read();
			d=read();
			x=read();
			add(a,b,x);
			add(a,d+1,-x);
			add(c+1,b,-x);
			add(c+1,d+1,x);
		}
		if(flag==2){
			int x,y,r,l;
			x=read();
			y=read();
			r=read();
			l=read();
			printf("%lld\n",query(r,l)-query(r,y-1)-query(x-1,l)+query(x-1,y-1));
	
	
		}
	}
}
2021/11/29 19:08
加载中...