社区讨论
有没有帮忙看一下二维线段树的吖 哭哭
P4514上帝造题的七分钟参与者 4已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mi7x0c2w
- 此快照首次捕获于
- 2025/11/21 04:59 4 个月前
- 此快照最后确认于
- 2025/11/21 04:59 4 个月前
看过题解了,也知道二维线段树过不了,但是我发现我二维线段树神奇地打挂了。
因为水平有限,不是很会线段树套线段树,用的普通的那种,每个父节点有四个儿子那种。
目前已知的问题,但是还没有改的:
应该换成
因为是一些小问题,所以准备等代码框架弄对之后再说,现在还意识到好像的小矩阵需要特判,但是不知道具体该怎么办,或者或许也不需要特判嘛(我也不确定 希望高人指教
下面是代码
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 条回复,欢迎继续交流。
正在加载回复...