题目链接:传送门
思路:
二维树状数组,
vector(first,last)函数中assign函数相当于将first中的函数清空,然后将last中的值赋值给first。
参考文章:传送门
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1e6+;
vector <vector <int> >vc;
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
int i,j;
for(i=x;i<=n;i+=lowbit(i))
for(j=y;j<=m;j+=lowbit(j))
vc[i][j]+=;
}
int query(int x,int y)
{
int i,j,ans=;
for(i=x;i>;i-=lowbit(i))
for(j=y;j>;j-=lowbit(j))
ans+=vc[i][j];
return ans;
}
int get_sum(int x,int y,int A,int B)
{
return query(A,B)+query(x-,y-)-query(x-,B)-query(A,y-);
}
int main(void)
{
int i,j,x,y,A,B,q,d;
while(~scanf("%d%d%d",&n,&m,&d)){
vc.assign(n+,vector <int>(m+,));
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
scanf("%d",&x);
if(x>=d) update(i,j);
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&x,&y,&A,&B);
printf("%d\n",get_sum(x,y,A,B));
}
}
return ;
}