紧急通知！发现一颗优秀的线段树能卡过的题！！

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而变回去）

还有一点，常规的线段树的题，无非就是求和及最值，在本题中对于不同的问题时函数的写法都有表现了。