洛谷 P3437 [POI2006]TET-Tetris 3D

二维线段树区间更新啊

树套树的外层树，如果是线段树的话一般似乎不能打标记？（毕竟标记不好下传）

然而起码对于这题是可以的...对于外层线段树，每个节点放两个内层线段树dat和setv，分别是得到的值和修改操作留下的标记。

然后外层线段树要标记永久化...标记永久化之后，标记的定义不一样了。

这道题里用dat[i]表示i节点表示的整段区间都达到的值，setv[i]表示i节点表示的区间的最大值。

（这两个的名字似乎反了？）

这样进行修改操作的时候，更新所有经过的节点的setv（因为只要经过该点，那么该点表示的区间和目标区间一定有相交部分），更新被目标区间完全包含的区间所在节点的dat（自然整段都达到那个值了）

进行查询操作的时候，"所有经过节点的dat"和"所有被目标区间完全包含的区间所在节点的setv"的最大值就是答案。

二维都一样，只不过外层线段树的查询是对于内层线段树的给定区间查询/修改

标记不下传

（一眼看起来似乎不是很对？有些信息被遗漏了？然而的确是对的23333）

（似乎修改和查询完全是对称的...）

错误记录：71行少了分号后的两个语句导致WA一片

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define lc (num<<1)

 #define rc (num<<1|1)

 #define mid ((l+r)>>1)

 using namespace std;

 int n,m;

 namespace XXX

 {

     int L,R,x;

 struct Y

 {

     int dat[],setv[];

     //dat表示整段区间都达到的值，setv表示区间最大值

     void update(int l,int r,int num)

     {

         setv[num]=max(setv[num],x);

         if(L<=l&&r<=R)

         {

             dat[num]=max(dat[num],x);

             return;

         }

         if(L<=mid)    update(l,mid,lc);

         if(mid<R)    update(mid+,r,rc);

     }

     int query(int l,int r,int num)

     {

         if(L<=l&&r<=R)    return setv[num];

         int ans=dat[num];

         if(L<=mid)    ans=max(ans,query(l,mid,lc));

         if(mid<R)    ans=max(ans,query(mid+,r,rc));

         return ans;

     }

 };

 }

 int L,R,x;

 XXX::Y dat[],setv[];

 void update(int l,int r,int num)

 {

     XXX::x=x;

     setv[num].update(,m,);

     if(L<=l&&r<=R)

     {

         XXX::x=x;

         dat[num].update(,m,);

         return;

     }

     if(L<=mid)    update(l,mid,lc);

     if(mid<R)    update(mid+,r,rc);

 }

 int query(int l,int r,int num)

 {

     if(L<=l&&r<=R)    return setv[num].query(,m,);

     int ans=dat[num].query(,m,);

     if(L<=mid)    ans=max(ans,query(l,mid,lc));

     if(mid<R)    ans=max(ans,query(mid+,r,rc));

     return ans;

 }

 int main()

 {

     int Q,d,s,w,xx,yy;

     scanf("%d%d%d",&n,&m,&Q);

     while(Q--)

     {

         scanf("%d%d%d%d%d",&d,&s,&w,&xx,&yy);xx++;yy++;

         L=xx;R=xx+d-;XXX::L=yy;XXX::R=yy+s-;

         x=query(,n,)+w;//printf("%d\n",x);

         update(,n,);

     }

     L=;R=n;XXX::L=;XXX::R=m;

     printf("%d",query(,n,));

     return ;

 }

巴特西

洛谷 P3437 [POI2006]TET-Tetris 3D

最新文章

热门文章