UVA - 11992
一道丧心病狂的题。
题意：给你一个二维矩阵，初始矩阵中数字全为0，保证数字个数少于1e6，现在有三种操作：1.把一个子矩阵中的数字全部增加v，2.把一个子矩阵中的数字全部变成v，3.查询子矩阵的和，最大值和最小值。
分析：本题的难点有两个。一，这是一个二维矩阵；二，涉及到一个增加操作和一个变换操作。对于第一个难点，因为它保证了数字个数少于1e6，所以我们可以把这个矩阵变成一个行向量，这样在查询的时候我们只需要分段查询即可（求和相加，最值做全局变量）。对于第二个难题，其实在HihoCoder - 1080已经遇到过。
#include<bits/stdc++.h>
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+100;
using namespace std;
struct node{
int add;
int ct;
int Sum;
int Max;
int Min;
int l,r;
}tree[maxn<<2];
int Min,Max;
void pushDown(int rt){
if(tree[rt].ct!=-1){ //②
tree[rt<<1].add=0;
tree[rt<<1].Sum=(tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].ct;
tree[rt<<1].Max=tree[rt].ct;
tree[rt<<1].Min=tree[rt].ct;
tree[rt<<1].ct=tree[rt].ct;
tree[rt<<1|1].add=0;
tree[rt<<1|1].Sum=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*tree[rt].ct;
tree[rt<<1|1].Max=tree[rt].ct;
tree[rt<<1|1].Min=tree[rt].ct;
tree[rt<<1|1].ct=tree[rt].ct;
tree[rt].ct=-1;
}
if(tree[rt].add){
tree[rt<<1].add+=tree[rt].add;
tree[rt<<1].Sum+=(tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].add;
tree[rt<<1].Max+=tree[rt].add;
tree[rt<<1].Min+=tree[rt].add;
tree[rt<<1|1].Sum+=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*tree[rt].add;
tree[rt<<1|1].Max+=tree[rt].add;
tree[rt<<1|1].Min+=tree[rt].add;
tree[rt<<1|1].add+=tree[rt].add;
tree[rt].add=0;
}
}
void pushUp(int rt){
tree[rt].Sum=tree[rt<<1].Sum+tree[rt<<1|1].Sum;
tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
}
void Updata(int rt,int l,int r,int v,int op){
if(tree[rt].l >= l && tree[rt].r <= r){
if(op==1){
tree[rt].add+=v;
tree[rt].Sum+=v*(tree[rt].r-tree[rt].l+1);
tree[rt].Min+=v;
tree[rt].Max+=v;
}else{
tree[rt].add=0; //①
tree[rt].ct=v;
tree[rt].Sum=v*(tree[rt].r-tree[rt].l+1);
tree[rt].Min=v;
tree[rt].Max=v;
}
return;
}
pushDown(rt);
if(tree[rt<<1].r>=l){
Updata(rt<<1,l,r,v,op);
}
if(tree[rt<<1|1].l<=r){
Updata(rt<<1|1,l,r,v,op);
}
pushUp(rt);
}
int Query(int rt,int l,int r)
{
if(tree[rt].l==l && tree[rt].r==r){
Min=min(Min,tree[rt].Min);
Max=max(Max,tree[rt].Max);
return tree[rt].Sum;
}
pushDown(rt);
if(tree[rt<<1|1].l<=l){
return Query(rt<<1|1,l,r);
}else if(tree[rt<<1].r>=r){
return Query(rt<<1,l,r);
}else{
return Query(rt<<1|1,tree[rt<<1|1].l,r)+Query(rt<<1,l,tree[rt<<1].r);
}
}
void Creat(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].add=0;
tree[rt].ct=-1;
tree[rt].Sum=0;
tree[rt].Max=0;
tree[rt].Min=0;
if(l==r){
return;
}
int mid=(l+r)>>1;
Creat(rt<<1,l,mid);
Creat(rt<<1|1,mid+1,r);
}
void Solve()
{
int r,c,m;
while(scanf("%d%d%d",&r,&c,&m)!=EOF){
Creat(1,1,r*c);
int op,x1,y1,x2,y2,v;
for(int i=0;i<m;i++){
scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
if(op==1){
scanf("%d",&v);
for(int i=x1;i<=x2;i++){
Updata(1,(i-1)*c+y1,(i-1)*c+y2,v,op);
}
}else if(op==2){
scanf("%d",&v);
for(int i=x1;i<=x2;i++){
Updata(1,(i-1)*c+y1,(i-1)*c+y2,v,op);
}
}else{
int Sum=0;
Min=INF, Max=0;
for(int i=x1;i<=x2;i++)
Sum+=Query(1,(i-1)*c+y1,(i-1)*c+y2);
printf("%d %d %d\n",Sum,Min,Max);
}
}
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
这是一颗优秀的线段树，只跑300ms的线段树！
在解决第一个问题之后，其实写法就是常规的线段树写法，跑300ms的原因是在Creat（）的时候我并没有调用pushUp（）。
写在最后的话主要是想说一下开始WA的几个点。
其实就是对于已经有add并且没有pushDown的点，在接受到了ct（change_to）之后怎么处理的问题。
注释1. 在接受了ct之后，应该把原来有的add消去。
注释2.这两个if语句顺序都不能换！（虽然不知道为什么，感觉换了也仍然会因为ct!=-1而变回去）
还有一点，常规的线段树的题，无非就是求和及最值，在本题中对于不同的问题时函数的写法都有表现了。
