uva 11992区間は線分樹を修正します.
データ範囲は広いですが、行ごとに線分樹を作って、線形にします.
setの優先度はaddより高い.
pusshdownはaddとsettの中で一つの区間を「賦」するのと同じです.だからsum、min 1、max 1を変える部分を加えます.
三つの問い合わせは一緒にしてもいいです.
setの優先度はaddより高い.
pusshdownはaddとsettの中で一つの区間を「賦」するのと同じです.だからsum、min 1、max 1を変える部分を加えます.
三つの問い合わせは一緒にしてもいいです.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAXN 4000000
//#define INF 1000000000
// ， ，
int ll,rr,r,c,m,ans1,ans2,ans3,op,x1,y1,x2,y2,v;
struct point{
int l,r,sum,max1,min1;
}tree[MAXN];
int addv[MAXN],setv[MAXN];//lazy_tag
void build(int p,int l,int r)
{
tree[p].l=l;
tree[p].r=r;
tree[p].sum=0;
tree[p].min1=0;
tree[p].max1=0;
if (l==r)
return ;
int mid=(l+r) >> 1;
build(p<<1,l,mid);
build(p<<1^1,mid+1,r);
return ;
}
// set>add（ set>=0 add>0 ）
void pushdown(int p)
{
if (setv[p]>=0)
{
setv[p<<1]=setv[p<<1^1]=setv[p];
addv[p<<1]=addv[p<<1^1]=0;
tree[p<<1].sum=(tree[p<<1].r-tree[p<<1].l+1)*setv[p];
tree[p<<1^1].sum=(tree[p<<1^1].r-tree[p<<1^1].l+1)*setv[p];
tree[p<<1].min1=tree[p<<1^1].min1=setv[p];
tree[p<<1].max1=tree[p<<1^1].max1=setv[p];
setv[p]=-1;// ！！
}
if (addv[p]>0)
{
addv[p<<1]+=addv[p];
addv[p<<1^1]+=addv[p];
tree[p<<1].sum+=(tree[p<<1].r-tree[p<<1].l+1)*addv[p];
tree[p<<1^1].sum+=(tree[p<<1^1].r-tree[p<<1^1].l+1)*addv[p];
tree[p<<1].min1+=addv[p];
tree[p<<1].max1+=addv[p];
tree[p<<1^1].min1+=addv[p];
tree[p<<1^1].max1+=addv[p];
addv[p]=0;
}
}
void updata(int p)
{
tree[p].min1=min(tree[p<<1].min1,tree[p<<1^1].min1);
tree[p].max1=max(tree[p<<1].max1,tree[p<<1^1].max1);
tree[p].sum=tree[p<<1].sum+tree[p<<1^1].sum;
}
void add(int p,int l,int r,int v)
{
if (tree[p].l==l && tree[p].r==r)
{
addv[p]+=v;
tree[p].sum+=(r-l+1)*v;//if
tree[p].min1+=v;
tree[p].max1+=v;
return ;
}
pushdown(p);//pushdown ， if
//
int mid=(tree[p].l+tree[p].r) >> 1;
if (r<=mid) add(p<<1,l,r,v);
if (l>mid) add(p<<1^1,l,r,v);
if (l<=mid && r>mid)
{
add(p<<1,l,mid,v);
add(p<<1^1,mid+1,r,v);
}
updata(p);
}
void sett(int p,int l,int r,int v)
{
if (tree[p].l==l && tree[p].r==r)
{
setv[p]=v;
addv[p]=0;//
tree[p].sum=(r-l+1)*v;
tree[p].min1=v;
tree[p].max1=v;
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r) >> 1;
if (r<=mid) sett(p<<1,l,r,v);
if (l>mid) sett(p<<1^1,l,r,v);
if (l<=mid && r>mid)
{
sett(p<<1,l,mid,v);
sett(p<<1^1,mid+1,r,v);
}
updata(p);
}
void query(int p,int l,int r)
{
if (tree[p].l==l && tree[p].r==r)
{
ans1+=tree[p].sum;
ans2=min(ans2,tree[p].min1);
ans3=max(ans3,tree[p].max1);
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r) >> 1;
if (r<=mid) query(p<<1,l,r);
if (l>mid) query(p<<1^1,l,r);
if (l<=mid && r>mid)
{
query(p<<1,l,mid);
query(p<<1^1,mid+1,r);
}
updata(p);
}
int main()
{
while (cin>>r>>c>>m)
{
memset(addv,0,sizeof(addv));
memset(setv,-1,sizeof(setv));// set 0
build(1,1,r*c);
for (int i=1;i<=m;i++)
{
cin>>op>>x1>>y1>>x2>>y2;
if (op==1)
{
cin>>v;
for (int j=x1;j<=x2;j++)
{
add(1,(j-1)*c+y1,(j-1)*c+y2,v);
}
}
if (op==2)
{
cin>>v;
for (int j=x1;j<=x2;j++)
{
sett(1,(j-1)*c+y1,(j-1)*c+y2,v);
}
}
if (op==3)
{
ans2=1000000000;
ans1=ans3=0;
for (int j=x1;j<=x2;j++)
{
ll=(j-1)*c+y1;
rr=(j-1)*c+y2;
query(1,ll,rr);
}
cout<<ans1<<' '<<ans2<<' '<<ans3<<endl;
}
}
}
return 0;
}