【模拟赛题解】在太阳西斜的这个世界里

珂朵莉是世界上最幸福的女孩，不接受反驳！

$\color{gray}\scriptsize\text{世界一、幸せな女の子だ}$

赛时只有两个同学 AC，另一个同学奇怪地得了 $99$ 分，Subtask#1没过......比较奇怪。

好吧，让我们一点一点切掉这道题吧QwQ。

$\text{Subtask\#1}$：骗分大法

题中说了：为样例1。

所以，输出样例1的答案就行了。

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"26"<<endl;
    cout<<"4 10"<<endl;
    cout<<"33"<<endl;
    return 0;
}

得 $1$ 分。

$\text{Subtask\#2}$：正片开始

题目大意就是给定一个矩阵，让我们求子矩阵的和/最大值/最小值。

由于 $\text{Subtask\#2}$ 说了不查询最大最小值，因此不用考虑。

一眼看过去：线段树套线段树

对于每次操作：

• 如果是修改，那么直接遍历一遍修改区间，遇到一个数就修改一个。
• 如果是查询，那么 int ans=0;，然后遍历查询区间，遇到一个数就把 ans 加上这个数。

注意：查询和的时候，虽然说矩阵中的数不会大于 $2\times10^5$，也不会小于 $2\times10^5$，似乎开int就存下了。

然而，我们查询的可是多个数的和啊！

比如说，我们查询了 $100000$ 个数的和（由于矩阵最大有 $1000\times1000=1000000$ 个数，所以完全可以查询 $100000$ 个数），那么这些数的和最大将会是：

$2\times10^5\times100000=20000000000$

int 直接炸掉。

所以，果断开 long long！

能过 $\text{Subtask\#2}$ 的代码：

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],n,m,q;        //数组开大点保险
int main(){
    cin>>n>>m;  //输入 n 和 m，表示一个 n 列，m 行的矩阵。
    for(int i=1;i<=n;i++){      //i 表示列数
        for(int j=1;j<=m;j++){  //j 表示行数
            cin>>a[i][j];       //一个一个元素地输入这个矩阵。
        }
    }
    cin>>q;     //输入查询次数
    for(int i=1;i<=q;i++){      //一共有 q 次查询
        int opt,l1,r1,l2,r2,k;
        //opt 表示操作编号
        //l1,r1,l2,r2,k 如题意。
        cin>>opt;   //输入操作编号，即判断是几号操作。
        if(opt==1){ //如果是操作 1 号：
            cin>>l1>>r1>>l2>>r2>>k;         //输入要修改的区间与要修改的值
            //接下来遍历修改区间
            for(int i=l1;i<=l2;i++){        //列数
                for(int j=r1;j<=r2;j++){    //行数
                    a[i][j]+=k;             //遇到一个数，就修改一个。
                }
            }
        }
        else if(opt==2){        //如果是操作 2 号：
            cin>>l1>>r1>>l2>>r2;
            long long ans=0;    //一定要开 long long！
            for(int i=l1;i<=l2;i++){        //列数
                for(int j=r1;j<=r2;j++){    //行数
                    ans+=(long long)a[i][j];//遇到一个数，就把 ans 加上这个数的值。
                    //这里在a[i][j]前面加上一个 (long long) 的意思是：强制把a[i][j]变成 long long 类型的，不然两个不同的数加在一起可能会出错。
                }
            }
            cout<<ans<<endl;    //输出 ans。
        }
    }

    return 0;
}

此代码得到了 $\text{Subtask\#1}$ 和 $\text{Subtask\#2}$ 的分数，$20$ 分。

$\text{Subtask\#3}$：稍加思考

好，接下来我们看看查询最大最小值的操作。

简化版

先来道简化版：如何求一个数组内所有数的最大最小值？

int a[15]={5,1,2,4,6,7,8,9,3,0};
int maxn=-1,minn=2333333;
for(int i=0;i<10;i++){
    maxn=max(maxn,a[i]);
    minn=min(minn,a[i]);
}
cout<<maxn<<" "<<minn<<endl;

我们来一行一行地解释一下这个代码。

• 第一行：定义一个数组。
• 第二行：定义 maxn 与 minn，表示这个数组中的最大最小值。
• 第三行：遍历整个数组。
• 第四行&第五行：重点操作。

注：这里的 max 和 min 分别是C++内置的取最大值和最小值的函数。例如：max(2,4)的值为 $4$，min(233,114514)的值为 $233$。

我们手动模拟一番：

第一重循环：

此时 maxn=-1,minn=15,i=0,a[i]=5。
给 maxn 和 minn 赋值一下：

maxn=max(-1,5)=5;
minn=min(15,5)=5;

第二重循环：

此时 maxn=5,minn=5,i=1,a[i]=1。
给 maxn 和 minn 赋值一下：

maxn=max(5,1)=5;
minn=min(5,1)=1;

第三重循环：

此时 maxn=5,minn=1,i=2,a[i]=2。
给 maxn 和 minn 赋值一下：

maxn=max(5,2)=5;
minn=min(1,2)=1;

第四重循环：

此时 maxn=5,minn=1,i=3,a[i]=4。
给 maxn 和 minn 赋值一下：

maxn=max(5,4)=5;
minn=min(1,4)=1;

第五重循环：

此时 maxn=5,minn=1,i=4,a[i]=6。
给 maxn 和 minn 赋值一下：

maxn=max(5,6)=6;
minn=min(1,6)=6;

第六重循环：

此时 maxn=6,minn=1,i=5,a[i]=7。
给 maxn 和 minn 赋值一下：

maxn=max(6,7)=7;
minn=min(1,7)=1;

第七重循环：

此时 maxn=7,minn=1,i=6,a[i]=8。
给 maxn 和 minn 赋值一下：

maxn=max(7,8)=8;
minn=min(1,8)=1;

第八重循环：

此时 maxn=8,minn=1,i=7,a[i]=9。
给 maxn 和 minn 赋值一下：

maxn=max(8,9)=9;
minn=min(1,9)=1;

第九重循环：

此时 maxn=9,minn=1,i=8,a[i]=3。
给 maxn 和 minn 赋值一下：

maxn=max(9,3)=9;
minn=min(1,3)=1;

第十重循环：

此时 maxn=9,minn=1,i=9,a[i]=0。
给 maxn 和 minn 赋值一下：

maxn=max(9,0)=9;
minn=min(1,0)=0;

最后，$\mathsf{maxn=9,minn=0}$。

所以输出：9 0

所以，我们想要找一个区间内的最大值，只需要遍历这个区间，然后每次对答案取max或min即可。

一个小技巧是：把maxn设的尽可能小，minn设的尽可能大。

不然的话，如果maxn恰好大于区间中的所有数，那么会出现每次取max都会取到自己的尴尬情况，导致错误。

回到原题

类似地，求一个矩阵中的最大值：

cin>>l1>>r1>>l2>>r2;
int maxn=-2147483647,minn=2147483647;   //2147483647=2^31-1，是int能存下的最大数。-2147483647自然是最小数。
for(int i=l1;i<=l2;i++){                //行数
    for(int j=r1;j<=r2;j++){            //列数
        maxn=max(maxn,a[i][j]);
        minn=min(minn,a[i][j]);
//遇到一个数就取 max 和 min。
    }
}
cout<<maxn<<" "<<minn<<endl;

原理与上面类似。不再多说。

最后，完整代码：

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],n,m,q;
int main(){
    cin>>n>>m;  //输入 n 和 m，表示一个 n 列，m 行的矩阵。
    for(int i=1;i<=n;i++){      //i 表示列数
        for(int j=1;j<=m;j++){  //j 表示行数
            cin>>a[i][j];       //一个一个元素地输入这个矩阵。
        }
    }
    cin>>q;     //输入查询次数
    for(int i=1;i<=q;i++){      //一共有 q 次查询
        int opt,l1,r1,l2,r2,k;
        //opt 表示操作编号
        //l1,r1,l2,r2,k 如题意。
        cin>>opt;   //输入操作编号，即判断是几号操作。
        if(opt==1){ //如果是操作 1 号：
            cin>>l1>>r1>>l2>>r2>>k;         //输入要修改的区间与要修改的值
            //接下来遍历修改区间
            for(int i=l1;i<=l2;i++){        //列数
                for(int j=r1;j<=r2;j++){    //行数
                    a[i][j]+=k;             //遇到一个数，就修改一个。
                }
            }
        }
        else if(opt==2){        //如果是操作 2 号：
            cin>>l1>>r1>>l2>>r2;
            long long ans=0;    //一定要开 long long！
            for(int i=l1;i<=l2;i++){        //列数
                for(int j=r1;j<=r2;j++){    //行数
                    ans+=(long long)a[i][j];//遇到一个数，就把 ans 加上这个数的值。
                    //这里在a[i][j]前面加上一个 (long long) 的意思是：强制把a[i][j]变成 long long 类型的，不然两个不同的数加在一起可能会出错。
                }
            }
            cout<<ans<<endl;    //输出 ans。
        }
        else{
            cin>>l1>>r1>>l2>>r2;
            int maxn=-2147483647,minn=2147483647;   //2147483647=2^31-1，是int能存下的最大数。-2147483647自然是最小数。
            for(int i=l1;i<=l2;i++){                //行数
                for(int j=r1;j<=r2;j++){            //列数
                    maxn=max(maxn,a[i][j]);
                    minn=min(minn,a[i][j]);
                    //遇到一个数就取 max 和 min。
                }
            }
            cout<<minn<<" "<<maxn<<endl;
        }
    }

    return 0;
}