【bzoj 1513】Tet-Tetris 3D（线段树套线段树+标记永久化）

传送门biu~ 对于线段树套线段树，因为标记的update和pushdown操作过于繁琐，所以采用标记永久化，即在一个节点打上标记后，所有越过这个节点的查询均计算上标记。 Ac代码：

#include<bits/stdc++.h> using namespace std; const int N=3005; int D,S,n,ql,qr,qd,qu; struct NodeX{ int v[N],lazy[N]; void Modify(int num,int l,int r,int L,int R,int x){ v[num]=max(v[num],x); if(l==L && r==R) {lazy[num]=max(lazy[num],x);return;} int mid=l+r>>1; if(R<=mid) Modify(num<<1,l,mid,L,R,x); else if(L>mid) Modify(num<<1|1,mid+1,r,L,R,x); else Modify(num<<1,l,mid,L,mid,x),Modify(num<<1|1,mid+1,r,mid+1,R,x); } int Query(int num,int l,int r,int L,int R){ if(l==L && r==R) return v[num]; int mid=l+r>>1,re=lazy[num]; if(R<=mid) return max(re,Query(num<<1,l,mid,L,R)); else if(L>mid) return max(re,Query(num<<1|1,mid+1,r,L,R)); else return max(re,max(Query(num<<1,l,mid,L,mid),Query(num<<1|1,mid+1,r,mid+1,R))); } }; struct NodeY{ NodeX v[N],lazy[N]; void Modify(int num,int l,int r,int L,int R,int x){ v[num].Modify(1,1,S,qd,qu,x); if(l==L && r==R) {lazy[num].Modify(1,1,S,qd,qu,x);return;} int mid=l+r>>1; if(R<=mid) Modify(num<<1,l,mid,L,R,x); else if(L>mid) Modify(num<<1|1,mid+1,r,L,R,x); else Modify(num<<1,l,mid,L,mid,x),Modify(num<<1|1,mid+1,r,mid+1,R,x); } int Query(int num,int l,int r,int L,int R){ if(l==L && r==R) return v[num].Query(1,1,S,qd,qu); int mid=l+r>>1,re=lazy[num].Query(1,1,S,qd,qu); if(R<=mid) return max(re,Query(num<<1,l,mid,L,R)); else if(L>mid) return max(re,Query(num<<1|1,mid+1,r,L,R)); else return max(re,max(Query(num<<1,l,mid,L,mid),Query(num<<1|1,mid+1,r,mid+1,R))); } }tree; int main(){ scanf("%d%d%d",&D,&S,&n); while(n--){ int d,s,w,x,y; scanf("%d%d%d%d%d",&d,&s,&w,&x,&y); ql=x+1;qr=x+d;qd=y+1;qu=y+s; int tmp=tree.Query(1,1,D,ql,qr); tree.Modify(1,1,D,ql,qr,tmp+w); } qd=1,qu=S; printf("%d\n",tree.Query(1,1,D,1,D)); return 0; }

别想了亲测四分树过不了这道题的QAQ：

//注意非Ac代码 #include<bits/stdc++.h> using namespace std; struct Node{ Node *ch[4]; int v,mark; Node(){v=mark=0;for(int i=0;i<4;++i)ch[i]=NULL;} }*root; void Modify(Node *&o,int l,int r,int d,int u,int L,int R,int D,int U,int x){ if(!o) o=new Node; o->v=max(o->v,x); if(l==L && r==R && d==D && u==U) {o->mark=x;return;} int xm=l+r>>1,ym=d+u>>1; if(L<=xm && D<=ym) Modify(o->ch[0],l,xm,d,ym,L,min(R,xm),D,min(U,ym),x); if(L<=xm && U>ym) Modify(o->ch[1],l,xm,ym+1,u,L,min(R,xm),max(D,ym+1),U,x); if(R>xm && D<=ym) Modify(o->ch[2],xm+1,r,d,ym,max(L,xm+1),R,D,min(U,ym),x); if(R>xm && U>ym) Modify(o->ch[3],xm+1,r,ym+1,u,max(L,xm+1),R,max(D,ym+1),U,x); } int Query(Node *o,int l,int r,int d,int u,int L,int R,int D,int U){ if(!o) return 0; if(l==L && r==R && d==D && u==U) return o->v; int xm=l+r>>1,ym=d+u>>1; int re=o->mark; if(L<=xm && D<=ym) re=max(re,Query(o->ch[0],l,xm,d,ym,L,min(R,xm),D,min(U,ym))); if(L<=xm && U>ym) re=max(re,Query(o->ch[1],l,xm,ym+1,u,L,min(R,xm),max(D,ym+1),U)); if(R>xm && D<=ym) re=max(re,Query(o->ch[2],xm+1,r,d,ym,max(L,xm+1),R,D,min(U,ym))); if(R>xm && U>ym) re=max(re,Query(o->ch[3],xm+1,r,ym+1,u,max(L,xm+1),R,max(D,ym+1),U)); return re; } int main(){ int n,m,T; scanf("%d%d%d",&n,&m,&T); while(T--){ int d,s,w,x,y; scanf("%d%d%d%d%d",&d,&s,&w,&x,&y); int L=x+1,R=x+d,D=y+1,U=y+s; int tmp=Query(root,1,n,1,m,L,R,D,U); Modify(root,1,n,1,m,L,R,D,U,tmp+w); } printf("%d\n",root->v); return 0; }