BZOJ 1513 [POI2006]Tet-Tetris 3D

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1513

题意：矩形求 max，矩形赋值。

二维线段树即可，本质上就是树套树，内外层线段树分别维护行列。

需要注意的是外层线段树没法 pushup 和 pushdown，复杂度无法接受。所以标记永久化即可。好多题解内层也标记永久化了，其实没有必要。

标记永久化即在修改时路径更新上传标记，找到区间后更新下传标记。

查询时路径上带上下传标记查询，找到区间后用上传标记更新即可。

此题卡空间，需要动态开点，可能是我写的挫，内外层都动态开点了... 跑的很慢...

有些题解直接不动态开点开的三倍空间，实际上是萎的好像？我记得线段树编号最大会到 4n-3 好像？

啊我随便口胡的 T.T

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
#define ll long long
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int Mx(int a,int b)
{return a>b?a:b;}
int n,m,q;
struct ins_seg
{
	int tag[N<<1],mx[N<<1];
	int ch[N<<1][2],tot;

	void cov(int x,int v)
	{
		tag[x]=Mx(tag[x],v);
		mx[x]=Mx(mx[x],v);
	}

	void pushdown(int x)
	{
		if(tag[x])
		{
			if(!ch[x][0])ch[x][0]=++tot;
			if(!ch[x][1])ch[x][1]=++tot;
			cov(ch[x][0],tag[x]),cov(ch[x][1],tag[x]);
			tag[x]=0;
		}
	}

	void pushup(int x)
	{
		mx[x]=Mx(mx[ch[x][0]],mx[ch[x][1]]);
	}

	void update(int &x,int l,int r,int L,int R,int v)
	{
		if(!x)x=++tot;
		if(l>=L&&r<=R)
		{
			cov(x,v);
			return ;
		}
		pushdown(x);
		int mid=(l+r)>>1;
		if(L<=mid) update(ch[x][0],l,mid,L,R,v);
		if(R>mid)  update(ch[x][1],mid+1,r,L,R,v);
		pushup(x);
	}

	int ask(int x,int l,int r,int L,int R)
	{
		if(!x)return 0;
		if(l>=L&&r<=R)return mx[x];
		pushdown(x);
		int mid=(l+r)>>1,ret=0;
		if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R));
		if(R>mid)  ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R));
		return ret;
	}
};
struct out_seg
{
	ins_seg tag[N<<1],mx[N<<1];
	int r_tag[N<<1],r_mx[N<<1];
	int ch[N<<1][2],tot;

	void modify(int &x,int l,int r,int L,int R,int c,int d,int e)
	{
		if(!x)x=++tot;
		mx[x].update(r_mx[x],1,m,c,d,e);
		if(l>=L&&r<=R)
		{
			tag[x].update(r_tag[x],1,m,c,d,e);
			return ;
		}
		int mid=(l+r)>>1;
		if(L<=mid) modify(ch[x][0],l,mid,L,R,c,d,e);
		if(R>mid)  modify(ch[x][1],mid+1,r,L,R,c,d,e);
	}

	int ask(int x,int l,int r,int L,int R,int c,int d)
	{
		int ret=tag[x].ask(r_tag[x],1,m,c,d);
		if(l>=L&&r<=R) return Mx(ret,mx[x].ask(r_mx[x],1,m,c,d));
		int mid=(l+r)>>1;
		if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R,c,d));
		if(R>mid)  ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R,c,d));
		return ret;
	}
}T;
int rt;
int main()
{
    n=read(),m=read(),q=read();
	while(q--)
	{
		int c=read(),d=read(),e=read(),a=read(),b=read();
		T.modify(rt,1,n,a+1,a+c,b+1,b+d,T.ask(1,1,n,a+1,a+c,b+1,b+d)+e);
	}
	printf("%d\n",T.ask(1,1,n,1,n,1,m));
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1010

#define ll long long

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

inline int Mx(int a,int b)

{return a>b?a:b;}

int n,m,q;

struct ins_seg

{

int tag[N<<1],mx[N<<1];

int ch[N<<1][2],tot;

void cov(int x,int v)

{

tag[x]=Mx(tag[x],v);

mx[x]=Mx(mx[x],v);

}

void pushdown(int x)

{

if(tag[x])

{

if(!ch[x][0])ch[x][0]=++tot;

if(!ch[x][1])ch[x][1]=++tot;

cov(ch[x][0],tag[x]),cov(ch[x][1],tag[x]);

tag[x]=0;

}

void pushup(int x)

{

mx[x]=Mx(mx[ch[x][0]],mx[ch[x][1]]);

}

void update(int &x,int l,int r,int L,int R,int v)

{

if(!x)x=++tot;

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

{

cov(x,v);

return ;

}

pushdown(x);

int mid=(l+r)>>1;

if(L<=mid) update(ch[x][0],l,mid,L,R,v);

if(R>mid) update(ch[x][1],mid+1,r,L,R,v);

pushup(x);

}

int ask(int x,int l,int r,int L,int R)

{

if(!x)return 0;

if(l>=L&&r<=R)return mx[x];

pushdown(x);

int mid=(l+r)>>1,ret=0;

if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R));

if(R>mid) ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R));

return ret;

}

};

struct out_seg

{

ins_seg tag[N<<1],mx[N<<1];

int r_tag[N<<1],r_mx[N<<1];

int ch[N<<1][2],tot;

void modify(int &x,int l,int r,int L,int R,int c,int d,int e)

{

if(!x)x=++tot;

mx[x].update(r_mx[x],1,m,c,d,e);

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

{

tag[x].update(r_tag[x],1,m,c,d,e);

return ;

}

int mid=(l+r)>>1;

if(L<=mid) modify(ch[x][0],l,mid,L,R,c,d,e);

if(R>mid) modify(ch[x][1],mid+1,r,L,R,c,d,e);

}

int ask(int x,int l,int r,int L,int R,int c,int d)

{

int ret=tag[x].ask(r_tag[x],1,m,c,d);

if(l>=L&&r<=R) return Mx(ret,mx[x].ask(r_mx[x],1,m,c,d));

int mid=(l+r)>>1;

if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R,c,d));

if(R>mid) ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R,c,d));

return ret;

}

}T;

int rt;

int main()

{

n=read(),m=read(),q=read();

while(q--)

{

int c=read(),d=read(),e=read(),a=read(),b=read();

T.modify(rt,1,n,a+1,a+c,b+1,b+d,T.ask(1,1,n,a+1,a+c,b+1,b+d)+e);

}

printf("%d\n",T.ask(1,1,n,1,n,1,m));

}

zgz233

BZOJ 1513 [POI2006]Tet-Tetris 3D

BZOJ 4942 [Noi2017] 整数

BZOJ 4785 [Zjoi2017] 树状数组

l1ll5

Comments | 2 条评论

yycc 博主

l1ll5 博主

zgz233