代码2（二维树状数组）

#include
#include
#include
using namespace std;
//2*u+v<2*M+2*s+t
const int N=2e3+10,M=2*N,K=2*M+3*N;
int n,m,q,x,y,res[N][N];
char s[N][N];
struct BIT{int n,m,tr[N][K];void init(int _n,int _m){n=_n;m=_m;memset(tr,0,sizeof tr);}void add(int x,int y,int v){for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j){tr[i][j]+=v;}}}int sum(int x,int y){int ans=0; for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){ans+=tr[i][j];}}return ans;}
}tr;
int main(){scanf("%d%d",&n,&m);tr.init(n,2*m+3*n);for(int i=1;i<=n;++i){scanf("%s",s[i]+1);for(int j=1;j<=n;++j){if(s[i][j]=='O'){tr.add(j,2*m+2*i+j,1);}//printf("i:%d j:%d sum2:%d sum:%d\n",i,j,tr.sum(j,2*m+3*n),tr.sum(j,2*i+j));res[i][j]=tr.sum(j,2*m+3*n)-tr.sum(j,2*i+j);}}scanf("%d",&q);while(q--){scanf("%d%d",&x,&y);printf("%d\n",res[x][y]);}return 0;
}