线段树总结:
线段树的原理就是每一个区间都可以被分成若干个不相交连续区间(重要)
线段树维护的数据:
1.自身结构的数据(比如 左儿子 , 右儿子的编号)
2.懒惰标记 (整段区间都变成一个值,或者将要进行什么操作.根据每次操作的类型,把操作的区间分成若干个不连续的区间,然后把操作的标记赋值给相应的区间)
3.答案 (就是query的答案,比如区间的sum什么的)
#define lc idx<<1 // 左儿子
#define rc idx<<1|1 //右儿子
#define mid ((l+r)>>1) //中点
using namespace std;
const int MAXN=1e6+1; //最大区间
const int INF=1e9; //无限
class SGtree
{
private:
这里加上需要维护的数据
public:
void build(int idx,int l,int r) //建树
{
数据值的初始化
if(l!=r)
{
build(lc,l,mid);左边儿子递归建树
build(rc,mid+1,r);右边儿子递归建树
}
}
void maintain(int idx,int l,int r,这里加上需要传递给这个节点的数据) //维护数据的函数
{
根据上面传给这个函数的数据,重新计算这个节点idx的数据
}
void PushDown(int idx,int l,int r)
{
把idx节点的懒惰标记向下传
注意:
把标记向下传的时候要把idx的节点本身的标记清除
}
void PushUp(int idx,int l,int r)
{
根据idx的左右儿子来重新计算出节点idx的数据
注意:
懒惰标记不用向上更新;
需要更新的是答案的数据而已
}
void update(int idx,int l,int r,int x,int y,这个区间要改变的数据)
{
if(x<=l && r<=y) 当当前区间[l,r] 已经被[x,y]完全包含的时候执行
{
maintain(idx,l,r,这个区间要改变的数据);
这样就可以计算出来节点idx的最新值
注意:
我们在设计线段树维护的数据的时候,当加上一个标记,
我们应该可以利用本身节点的数据和这个标记快速更新
出答案.
如果不是这样,我们递归到叶子节点再向上更新的方法来改变
这个节点的值的话,懒惰标记是没有作用的.
}
else
{
PushDown(idx,l,r); 懒惰标记向下传递
if(x<=mid) update(lc,l,mid,x,y,v);
if(y>mid) update(rc,mid+1,r,x,y,v);
递归结束时左右儿子时,左右儿子的值肯定是最新的了,
我们用左右儿子的值来更新父亲节点的值,
这样就保证了整棵树全部的值都是正确的
PushUp(idx);
}
}
void query(int idx,int l,int r,int x,int y)
{
if(x<=l && r<=y)
{
计算答案
}
else
{
PushDown(idx,l,r); 懒惰节点付给左右儿子
if(x<=mid) query(lc,l,mid,x,y);
if(y>mid) query(rc,mid+1,r,x,y);
这里不用pushup是因为:
1.询问操作不会改变树上的数据
2.树上数据的改变是由于懒惰标记向下传,上面我们说了update的时候每一个已经有懒惰标记的节点的数据都是正确的,所以不用更新
}
}
};
SGtree tree;
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#define lc idx<<1
#define rc idx<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=1e6+1;
const int INF=1e9;
int _minn,_maxx,_sum;
class SGtree
{
private:
int minv[MAXN<<2],maxv[MAXN<<2],sum[MAXN<<2],add[MAXN<<2],setv[MAXN<<2];
//1.答案:最小值,最大值,和
//2.懒惰标记:加,区间设置为(setv)
public:
void build(int idx,int l,int r)
{
minv[idx]=maxv[idx]=sum[idx]=add[idx]=setv[idx]=0; //初始化全部清0
if(l!=r)
{
build(lc,l,mid);
build(rc,mid+1,r);
}
}
void maintain(int idx,int l,int r,int add_v,int set_v)
{
//这里的miantian,
//我们要注意下当同时有一个加的延迟和设置的延迟传递下来的时候
//我们应该先处理set_v这个设置操作
//因为一旦有setv的操作,这个节点的值完全取决与setv
//节点原来的add操作应该被清空
//这个要特别注意
if(set_v)
{
sum[idx]=(r-l+1)*set_v;
setv[idx]=minv[idx]=maxv[idx]=set_v;
add[idx]=0;//清空add标记
}
if(add_v)
{
sum[idx]+=(r-l+1)*add_v;
minv[idx]+=add_v;
maxv[idx]+=add_v;
add[idx]+=add_v;
}
}
void PushDown(int idx,int l,int r)
{
maintain(lc,l,mid,add[idx],setv[idx]);
maintain(rc,mid+1,r,add[idx],setv[idx]);
add[idx]=setv[idx]=0;//标记传下去后要清除
}
void PushUp(int idx)
{
minv[idx]=min(minv[lc],minv[rc]);
maxv[idx]=max(maxv[lc],maxv[rc]);
sum[idx]=sum[lc]+sum[rc];
}
void Gset(int idx,int l,int r,int x,int y,int v) //区间设置
{
if(x<=l && r <=y)
{
maintain(idx,l,r,0,v);
}
else
{
PushDown(idx,l,r);
if(x<=mid) Gset(lc,l,mid,x,y,v);
if(y>mid) Gset(rc,mid+1,r,x,y,v);
PushUp(idx);
}
}
void Gadd(int idx,int l,int r,int x,int y,int v) //区间加
{
if(x<=l && r<=y)
{
maintain(idx,l,r,v,0);
}
else
{
PushDown(idx,l,r);
if(x<=mid) Gadd(lc,l,mid,x,y,v);
if(y>mid) Gadd(rc,mid+1,r,x,y,v);
PushUp(idx);
}
}
void query(int idx,int l,int r,int x,int y) //询问
{
if(x<=l && r<=y)
{
_minn=min(_minn,minv[idx]); //把答案更新到全局变量
_maxx=max(_maxx,maxv[idx]);
_sum+=sum[idx];
}
else
{
PushDown(idx,l,r);
if(x<=mid) query(lc,l,mid,x,y);
if(y>mid) query(rc,mid+1,r,x,y);
}
}
};
SGtree tree[22]; //注意应该把这个开在外面,不让可能因为数组过大而暴stack
int main()
{
// freopen("in","r",stdin);
int r,c,m;
while(~scanf("%d%d%d",&r,&c,&m))
{
for(int i=1; i<=r; i++)
{
tree[i].build(1,1,c);
}
while(m--)
{
int x1,y1,x2,y2,v,p;
scanf("%d",&p);
if(p==1)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
for(int i=x1; i<=x2; i++)
tree[i].Gadd(1,1,c,y1,y2,v);
}
else if(p==2)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
for(int i=x1; i<=x2; i++)
tree[i].Gset(1,1,c,y1,y2,v);
}
else
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
_minn=INF;
_maxx=0;
_sum=0;//要先初始化全局变量不然会出错
for(int i=x1; i<=x2; i++)
tree[i].query(1,1,c,y1,y2);
printf("%d %d %d\n",_sum,_minn,_maxx);
}
}
}
return 0;
}