本文共 2352 字，大约阅读时间需要 7 分钟。

【题目】

【题解】

法一：

树状数组（单点更新区间查询）板子题，就是1≤n×m≤10^6这个数据范围让我懵了下，用vector容器就好了。

如果大于等于d就等于单点更新1，看做是二维区间查询和即可。

法二：

啧啧，不好意思给我写麻烦了，其实做两次前缀和即可。（比如a[2][2]里存的就是a[1][1]+a[1][2]+a[2][1]+a[2][2]的值。）

区间查询用到了容斥定理哦。

【法一】

#include
   
    #define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long ll;const int maxn=1e6+5;#define lowbit(x) x&(-x)vector 
    
      ve[maxn];vector 
     
       vec[maxn];ll n,m;void add(ll x,ll y,ll val){    while(x<=n)    {        for(ll i=y;i<=m;i+=lowbit(i))        {            vec[x][i]+=val;        }        x+=lowbit(x);    }}ll sum(ll x,ll y){    ll res=0;    while(x>0)    {        for(ll i=y;i>0;i-=lowbit(i))            res+=vec[x][i];        x-=lowbit(x);    }    return res;}ll query(ll x1,ll y1,ll x2,ll y2){    return sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1-1,y2);}int main(){    ll d; scanf("%lld%lld%lld",&n,&m,&d);    ll xx,q;    for(ll i=1;i<=n;i++)    {        ve[i].push_back(0),vec[i].push_back(0);        for(ll j=1;j<=m;j++)        {            scanf("%lld",&xx);            ve[i].push_back(xx);            vec[i].push_back(0);        }    }    for(ll i=1;i<=n;i++)        for(ll j=1;j<=m;j++)        {            //printf("%lld\n",ve[i][j]);            if(ve[i][j]>=d) add(i,j,1);        }    scanf("%lld\n",&q);    ll a,b,x,y;    while(q--)    {        scanf("%lld%lld%lld%lld",&a,&b,&x,&y);        printf("%lld\n",query(a,b,x,y));    }    return 0;}
     
    
   

【法二】

#include
   
    #define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long ll;const int maxn=1e6+5;vector 
    
      vec[maxn];ll n,m;ll query(ll x1,ll y1,ll x2,ll y2){    return vec[x2][y2]+vec[x1-1][y1-1]-vec[x2][y1-1]-vec[x1-1][y2];}int main(){    ll d; scanf("%lld%lld%lld",&n,&m,&d);    ll xx,q;    for(ll j=0;j<=m;j++) vec[0].push_back(0);    for(ll i=1;i<=n;i++)    {        vec[i].push_back(0);        for(ll j=1;j<=m;j++)        {            scanf("%lld",&xx);            if(xx>=d) xx=1;            else xx=0;            xx+=vec[i][j-1];            vec[i].push_back(xx);        }    }    for(ll i=2;i<=n;i++)        for(ll j=1;j<=m;j++)            vec[i][j]+=vec[i-1][j];    scanf("%lld\n",&q);    ll a,b,x,y;    while(q--)    {        scanf("%lld%lld%lld%lld",&a,&b,&x,&y);        printf("%lld\n",query(a,b,x,y));    }    return 0;}
    
   

转载地址：http://tfben.baihongyu.com/