CSES 1652 Forest Queries 参考代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

int n,q;

cin>>n>>q;

int s[n+1][n+1];

memset(s,0,sizeof(s));

for(int i=1;i<=n;i++){

string ts;

cin>>ts;

for(int j=1;j<=n;j++){

if(ts[j-1]=='*'){

s[i][j]=1;

}

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

}

}

while(q>0){

q--;

int y1,x1,y2,x2;

cin>>y1>>x1>>y2>>x2; 

cout<<s[y2][x2]-s[y1-1][x2]-s[y2][x1-1]+s[y1-1][x1-1]<<endl;

}

return 0;

}