最大矩阵解题报告

1、最大和子矩阵【问题描述】对于一个矩阵A，它的每一个非空子矩阵中都有一个所有数的和，我们把其中最大的和称为矩阵A的F值。有一个N*M的矩阵，一开始每个位置都有一个整数值，而后我们对其进行操作和询问。操作：把一个子矩阵中的数都加上或者乘以一个整数；询问:问一个子矩阵的F值。数据保证不存在四个被询问的矩阵A，B，C，D，使得A与B相交、B与C相交、C与D相交、D与A相交.【输入格式】输入文件matrix.in的第一行包含两个正整数N，M；接下来N行，每行包含M个整数，表示矩阵中每个数的初值。接下来若干行，每行为操作或询问，以一行“DONE”结尾；如果是操作，那么在该行中显示“ADD P Q A B

2、C”或“MUL P Q A B C”，表示将以（P，Q）为左上角，(P+A-1,Q+B-1)为右下角的子矩阵中的每个数加上C或者乘以C；如果是询问，则显示“QUERY P Q D E”，表示询问以（P，Q）为左上角，(P+D-1,Q+E-1)为右下角的子矩阵G中的最大和子矩阵H中所有数的和，即G的一个子矩阵H（至少是1*1的，不能为空），满足对于G中任一个子矩阵I，都有：H中所有数的和不小于I中所有数的和。【输出格式】输出文件matrix.out对于每个询问，输出一行一个整数，即对应矩阵的最大子矩阵和。保证矩阵中的数和答案均在长整型范围内。【样例输入】4 4-5 0 9 90 -4 0 25

3、5 -3 -5-9 3 -5 3QUERY 1 1 4 4QUERY 2 2 2 2ADD 3 3 2 2 3QUERY 1 1 4 4ADD 1 1 3 4 4QUERY 2 1 3 4MUL 3 1 2 2 -1QUERY 1 1 4 4DONE【样例输出】205263846【数据规模】30%的数据满足，N,M,T=200，Q=20000；另外30%的数据满足，N=1，M,T,Q=100000；剩余40%的数据满足，N=6，M,T,Q=20000.【解题报告】本题是一道颇为容易的题。首先我们看看，对于一个A*B的矩阵，怎么求它的最大和子矩阵，我们可以枚举上下边界，然后算出上下边界之间每一列

4、中数的和，然后用经典的序列最大连续和做，时间复杂度为O(A*A*B).如果对于操作，我们就直接做，对于询问，我们则用上述的方法，那么总的时间复杂度就是O(TNM+sigma(A*A*B)，实际上sigma(A*A*B) =N*sigma(S=A*B)，那么，总的询问面积是多少呢?用题给条件：数据保证不存在四个被询问的矩阵A，B，C，D，使得A与B相交、B与C相交、C与D相交、D与A相交.如果有一个方格同时属于四个不同询问矩阵，显然就与这个条件矛盾了，所以每个方格最多属于三个不同的询问矩阵，即总的询问面积=3NM，这样复杂度控制在O(T+N)NM)，完全可以通过30%的数据。对于剩下的数据，只需用一个简单的线段树即可。由于N较小，所以我们当然枚举上下边界，对于操作矩阵，我们对每一行在相应的线段树里操作，时间复杂度为O(TNlogM)；对于询问矩阵，我们首先把每个元素都用线段树算出来，时间复杂度为O(ABlogM)，然后再枚举上下边界，复杂度为O(A*A*B)，总的时间复杂度为(TNlogM+(N+logM)NM)，可以通过数据。试想，如果没有题目中那个强大的条件，前30%的数据怎么做呢？笔者没有想到；但是对于70%的数据，我却在同学的提