区间修改——前缀和，差分或线段树或树状数组

题意：有t组输入，有一个n * m的矩阵，每次只能在n * m的矩阵中取一个a * b大小的矩阵，将其全部减一，问经过若干次后，能否将n * m的矩阵，都变为0，若可以输出"^_^",否则输出"QAQ"
分析：
把区间减一这个操作翻过来看，就是 地毯 ， 地毯题解（二维前缀和，差分）
此题为固定区间修改
区间修改————前缀和，差分或线段树或树状数组

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int const N=1e3+7;
int n,m,a,b,f;
int mp[N][N];   //原数组
int c[N][N];   //差分数组
int main(){
  fio;
  int t;
  cin >> t;
  while(t--){
    f=0;
    memset(mp,0,sizeof(mp)); 
    memset(c,0,sizeof(c));
    cin >> n >> m >> a >> b;
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        cin >> mp[i][j];
        c[i][j]=mp[i][j]-(mp[i-1][j]+mp[i][j-1])+mp[i-1][j-1]; 
      }
    }
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        mp[i][j]=c[i][j]+(c[i-1][j]+c[i][j-1])-c[i-1][j-1];
        if(mp[i][j]<0){
          f=1;break;
        }
        if(i+a-1<=n&&j+b-1<=m){
          c[i][j]-=mp[i][j];
          c[i+a][j]+=mp[i][j];
          c[i][j+b]+=mp[i][j];
          c[a+i][b+j]-=mp[i][j];
        }
        else if(mp[i][j]!=0){
          f=1;break;
        }
      }
      if(f) break;
    }

    if(f) cout << "QAQ" << endl;
    else cout << "^_^" << endl;
  }
  return 0;
}