题面传送门 显然可以四分树。 就是在线段树上加两个维度即可。 注意边界值。 代码实现:
#include<cstdio> #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,sx,sy,sz,f[16000039],ans,tot,pus; short flag[16000039]; inline void push(int now){ flag[now<<2|1]=flag[now<<2|2]=flag[now<<2|3]=flag[(now<<2)+4]=1; f[now<<2|1]=f[now<<2|2]=f[now<<2|3]=f[(now<<2)+4]=f[now]; flag[now]=0; } inline void get(int l1,int l2,int r1,int r2,int now){ if(x<=l1&&l2<=sx&&y<=r1&&r2<=sy) {f[now]=z;flag[now]=1;return;} if(flag[now]) push(now); f[now]=max(z,f[now]); int ml=(l1+l2)>>1,mr=(r1+r2)>>1; if(x<=ml&&y<=mr) get(l1,ml,r1,mr,now<<2|1); if(sx>ml&&y<=mr&&ml!=l2) get(ml+1,l2,r1,mr,now<<2|2); if(x<=ml&&sy>mr&&mr!=r2) get(l1,ml,mr+1,r2,now<<2|3); if(sx>ml&&sy>mr&&ml!=l2&&mr!=r2) get(ml+1,l2,mr+1,r2,(now<<2)+4); } inline void find(int l1,int l2,int r1,int r2,int now){ if(f[now]<=ans)return; if(x<=l1&&l2<=sx&&y<=r1&&r2<=sy) {ans=f[now];return;} if(flag[now]) push(now); int ml=(l1+l2)>>1,mr=(r1+r2)>>1; if(x<=ml&&y<=mr) find(l1,ml,r1,mr,now<<2|1); if(sx>ml&&y<=mr&&ml!=l2) find(ml+1,l2,r1,mr,now<<2|2); if(x<=ml&&sy>mr&&mr!=r2) find(l1,ml,mr+1,r2,now<<2|3); if(sx>ml&&sy>mr&&ml!=l2&&mr!=r2) find(ml+1,l2,mr+1,r2,(now<<2)+4); } inline void read(int &x){ char s=getchar();x=0; while(s<'0'||s>'9') s=getchar(); while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar(); } int main(){ register int i; scanf("%d%d%d",&n,&m,&k); while(k--){ read(sx);read(sy);read(z);read(x);read(y); sx+=x;sy+=y; x++;y++; ans=0; //printf("%d %d %d %d %d %d\n\n",x,sx,y,sy,z,ans); find(1,n,1,m,0); //printf("\n"); z+=ans; get(1,n,1,m,0); //printf("\n"); } printf("%d\n",f[0]); }