本文主要是介绍前缀和--BZOJ-4972 小Q的方格纸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小Q的方格纸有n行m列，一共n*m个方格，从上到下依次标记为第1,2,...,n行，从左到右依次标记为第1,2,...,m列，方便起见，小Q称第i行第j列的方格为(i,j)。小Q在方格纸中填满了数字，每个格子中都恰好有一个整数a_{i,j}。
小Q一共会给出q个询问，每次给定一个方格(x,y)和一个整数k(1<=k<=min(x,y))，你需要回答由(x,y),(x-k+1,y),(x,y-k+1)三个格子构成的三角形边上以及内部的所有格子的a的和。
将三角形化为梯形和矩形的和，差。
先用前缀和计算梯形、矩形的和即可。
ps：计算时注意f[a,b] = f[b] - f[a - 1]
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 3000 + 5;
int mp[maxn][maxn];
int tra[maxn][maxn],rect[maxn][maxn];
int n,m,q;
unsigned A,B,C;
typedef long long
这篇关于前缀和--BZOJ-4972 小Q的方格纸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
