@[TOC]Fast Matrix Operations UVA - 1199 涉及：区间修改赋值，区间求和，区间最大值最小值
#include<bits/stdc++.h> #define INF 0x7f7f7f7f #define lson pos<<1 #define rson pos<<1|1 using namespace std; const int maxn=1e5+7; struct Tree { int lchild,rchild; int ssum,mmax,mmin; int addv,setv; }tree[maxn<<2]; void pushup(int pos) { tree[pos].ssum=tree[lson].ssum+tree[rson].ssum; tree[pos].mmax=max(tree[lson].mmax,tree[rson].mmax); tree[pos].mmin=min(tree[lson].mmin,tree[rson].mmin); } void pushdown(int pos) { if(tree[pos].setv!=-1) { tree[lson].setv=tree[rson].setv=tree[pos].setv; tree[lson].addv=tree[rson].addv=0; tree[lson].mmax=tree[rson].mmax=tree[pos].setv; tree[lson].mmin=tree[rson].mmin=tree[pos].setv; tree[lson].ssum=(tree[lson].rchild-tree[lson].lchild+1)*tree[pos].setv; tree[rson].ssum=(tree[rson].rchild-tree[rson].lchild+1)*tree[pos].setv; tree[pos].setv=-1; } if(tree[pos].addv>0) { tree[lson].addv+=tree[pos].addv; tree[rson].addv+=tree[pos].addv; tree[lson].mmax+=tree[pos].addv; tree[rson].mmax+=tree[pos].addv; tree[lson].mmin+=tree[pos].addv; tree[rson].mmin+=tree[pos].addv; tree[lson].ssum+=tree[pos].addv*(tree[lson].rchild-tree[lson].lchild+1); tree[rson].ssum+=tree[pos].addv*(tree[rson].rchild-tree[rson].lchild+1); tree[pos].addv=0; } } void build(int l,int r,int pos) { tree[pos].lchild=l; tree[pos].rchild=r; tree[pos].ssum=0; tree[pos].mmax=0; tree[pos].mmin=0; tree[pos].addv=0; tree[pos].setv=-1; if(l==r) return; int mid=(l+r)>>1; build(l,mid,lson); build(mid+1,r,rson); pushup(pos); } void set_data(int l,int r,int pos,int val) { // printf("%d %d\n",l,r); if(tree[pos].lchild==l&&tree[pos].rchild==r) { tree[pos].ssum=val*(r-l+1); tree[pos].mmax=val; tree[pos].mmin=val; tree[pos].setv=val; tree[pos].addv; return ; } pushdown(pos); int mid=(tree[pos].lchild+tree[pos].rchild)>>1; if(r<=mid) set_data(l,r,lson,val); else if(l>mid) set_data(l,r,rson,val); else { set_data(l,mid,lson,val); set_data(mid+1,r,rson,val); } pushup(pos); } void add_data(int l,int r,int pos,int val) { // printf("%d %d\n",l,r); if(tree[pos].lchild==l&&tree[pos].rchild==r) { tree[pos].ssum+=val*(r-l+1); tree[pos].mmax+=val; tree[pos].mmin+=val; tree[pos].addv+=val; return ; } pushdown(pos); int mid=(tree[pos].lchild+tree[pos].rchild)>>1; if(r<=mid) add_data(l,r,lson,val); else if(l>mid) add_data(l,r,rson,val); else { add_data(l,mid,lson,val); add_data(mid+1,r,rson,val); } pushup(pos); } int Sum,Max,Min; void query(int l,int r,int pos) { // printf("%d %d\n",l,r); if(l==tree[pos].lchild&&tree[pos].rchild==r) { Sum+=tree[pos].ssum; Max=max(Max,tree[pos].mmax); Min=min(Min,tree[pos].mmin); return ; } pushdown(pos); int mid=(tree[pos].lchild+tree[pos].rchild)>>1; if(r<=mid) query(l,r,lson); else if(l>mid) query(l,r,rson); else { query(l,mid,lson); query(mid+1,r,rson); } pushup(pos); } int main() { int r,c,m; while(~scanf("%d%d%d",&r,&c,&m)) { build(1,r*c,1); int op,x1,x2,y1,y2,v; while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); for(int i=x1;i<=x2;i++) add_data((i-1)*c+y1,(i-1)*c+y2,1,v); } else if(op==2) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); for(int i=x1;i<=x2;i++) set_data((i-1)*c+y1,(i-1)*c+y2,1,v); } else { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); Sum=0; Max=-INF; Min=INF; for(int i=x1;i<=x2;i++) query((i-1)*c+y1,(i-1)*c+y2,1); printf("%d %d %d\n",Sum,Min,Max); } } } return 0; }