社区讨论

有没有帮忙看一下二维线段树的吖 哭哭

P4514上帝造题的七分钟参与者 4已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi7x0c2w
此快照首次捕获于
2025/11/21 04:59
4 个月前
此快照最后确认于
2025/11/21 04:59
4 个月前
查看原帖
看过题解了,也知道二维线段树过不了,但是我发现我二维线段树神奇地打挂了。
因为水平有限,不是很会线段树套线段树,用的普通的那种,每个父节点有四个儿子那种。
目前已知的问题,但是还没有改的:
intint应该换成long longlong~long
因为是一些小问题,所以准备等代码框架弄对之后再说,现在还意识到好像1×21\times2的小矩阵需要特判,但是不知道具体该怎么办,或者或许也不需要特判嘛(我也不确定 希望高人指教
下面是代码
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
template<typename sp>
inline void qread(sp &x){
	char ch=getchar(),lst=' ';
	while(ch<'0'||ch>'9') lst=ch,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(lst=='-') x=-x;
}
long long d[3000<<4],b[3000<<4];
int n,m;
char what;
inline long long pushup(int p){
	d[p]=d[(p<<2)-2]+d[(p<<2)-1]+d[p<<2]+d[(p<<2)|1];
}
inline void pushdown(int sx,int sy,int tx,int ty,int p){
	int midx=(sx+ty)>>1,midy=(sy+ty)>>1;
	d[(p<<2)-2]+=(midy-sy+1)*(midx-sx+1)*b[p];
	d[(p<<2)-1]+=(ty-midy)*(midx-sx+1)*b[p];
	d[p<<2]+=(midy-sy+1)*(tx-midx)*b[p];
	d[(p<<2)|1]+=(ty-midy)*(tx-midx)*b[p];
	b[(p<<2)-2]=b[(p<<2)-1]=b[p<<2]=b[(p<<2)|1]=b[p];
	b[p]=0;
}
inline void update(int lx,int ly,int rx,int ry,int c,int sx,int sy,int tx,int ty,int p){
	if(lx<=sx&&tx<=rx&&ly<=sy&&ty<=ry){
		d[p]+=(tx-sx+1)*(ty-sy+1)*c;
		b[p]+=c;
		return;
	}
	if(b[p]) pushdown(sx,sy,tx,ty,p);
	int midx=(sx+tx)>>1,midy=(sy+ty)>>1;
	if(ly<=midy&&lx<=midx) update(lx,ly,rx,ty,c,sx,sy,midx,midy,(p<<2)-2);
	if(ly>midy&&lx<=midx) update(lx,ly,rx,ty,c,sx,midy+1,midx,ty,(p<<2)-1);
	if(ly<=midy&&lx>midx) update(lx,ly,rx,ty,c,midx+1,sy,tx,midy,p<<2);
	if(ly>midy&&lx>midx) update(lx,ly,rx,ty,c,midx+1,midy+1,tx,ty,(p<<2)|1);
	pushup(p);
}
inline int getans(int lx,int ly,int rx,int ry,int sx,int sy,int tx,int ty,int p){
	if(lx<=sx&&tx<=rx&&ly<=sy&&ty<=ry){
		return d[p];
	}
	if(b[p]) pushdown(sx,sy,tx,ty,p);
	int midx=(sx+tx)>>1,midy=(sy+ty)>>1;
	int ans=0;
	if(ly<=midy&&lx<=midx) ans+=getans(lx,ly,rx,ty,sx,sy,midx,midy,(p<<2)-2);
	if(ly>midy&&lx<=midx) ans+=getans(lx,ly,rx,ty,sx,midy+1,midx,ty,(p<<2)-1);
	if(ly<=midy&&lx>midx) ans+=getans(lx,ly,rx,ty,midx+1,sy,tx,midy,p<<2);
	if(ly>midy&&lx>midx) ans+=getans(lx,ly,rx,ty,midx+1,midy+1,tx,ty,(p<<2)|1);
	return ans;
}
int main(){
	char opt[15];
	std::cin>>what;
	qread(n);qread(m);
	while(~scanf("%s",opt)){
		int x1=0,y1=0,x2=0,y2=0,del=0;
		qread(x1);qread(y1);qread(x2);qread(y2);
		if(opt[0]=='L'){
			qread(del);
			update(x1,y1,x2,y2,del,1,1,n,m,1);
		}
		if(opt[0]=='k') printf("%lld",getans(x1,y1,x2,y2,1,1,n,m,1));
	}
	return 0;
}
以前被说过线段树风格太毒瘤,希望大家多多谅解(
麻烦大家啦!

回复

8 条回复,欢迎继续交流。

正在加载回复...