#BZOJ4972

BZOJ4972 八月月赛 Problem B 小Q的方格纸 二维前缀和

  一个矩阵,一坨询问,问矩阵中一个特定方向的等腰直角三角形范围的sum。  一开始毫无头绪。  看完9题,一题也不会。  发现这题A的人多,于是我花了15分钟仔细思考。  发现可以了。  对于一个三角形区域,我们可以看下图:    我们把求右下黑色三角形区域转化成一个矩形和3个左上的三角形,然后就OK了。  矩形只要...