This is チラ裏 itself.

しがない大学生

AOJ 0560

JOI 2011 本選 1番「惑星探索」

二次元累積和の問題らしい。

左上の頂点の座標が(1,1)、右下の頂点の座標が(x,y)である長方形内に含まれる要素の数をnum[x][y][3]とすると、(num[x][y][0]は"J"の数、num[x][y][1]は"O"の数、num[x][y][2]は"I"の数)

左上の頂点の座標を(a,b)、右下の頂点の座標を(c,d)の長方形に含まれる要素数は、

num[c][d][a]-num[c][b-1][a]-num[a-1][d][a]+num[a-1][b-1][a]

(0<=a<3)

で計算される。

以下、ソースコード

#include <cstdio>
int exist[1001][1001][3]={};
char field[1001][1001];
int m,n,Q;
int main(){
 scanf("%d %d %d",&m,&n,&Q);
 for(int i=0;i<m;i++){
  scanf("%s",field[i]);
 }
 for(int i=0;i<m;i++){
  for(int j=i;j<m;j++){
   if(field[i][0]=='J'){
    exist[j][0][0]++;
   }else if(field[i][0]=='O'){
    exist[j][0][1]++;
   }else{
    exist[j][0][2]++;
   }
 }
}
for(int i=0;i<n;i++){
 for(int j=i;j<n;j++){
  if(field[0][i]=='J'){
    exist[0][j][0]++;
  }else if(field[0][i]=='O'){
    exist[0][j][1]++;
  }else{
    exist[0][j][2]++;
  }
 }
}
if(field[0][0]=='J'){
 exist[0][0][0]=1;
}else if(field[0][0]=='O'){
 exist[0][0][1]=1;
}else{
 exist[0][0][2]=1;
}
for(int i=1;i<m;i++){
 for(int j=1;j<n;j++){
  for(int k=0;k<3;k++){
   exist[i][j][k]=exist[i][j-1][k];
  }
  for(int k=0;k<=i;k++){
   if(field[k][j]=='J'){
    exist[i][j][0]++;
   }else if(field[k][j]=='O'){
    exist[i][j][1]++;
   }else{
    exist[i][j][2]++;
   }
  }
 }
}
for(int i=0;i<Q;i++){
 int a,b,c,d;
 scanf("%d %d %d %d",&a,&b,&c,&d);
 if(a>=2 && b>=2){
  printf("%d %d %d\n",exist[c-1][d-1][0]-exist[c-1][b-2][0]-exist[a-2][d-1]   [0]+exist[a-2][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1]-exist[a-2][d-1][1]+exist[a-2][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]-exist[a-2][d-1][2]+exist[a-2][b-2][2]);
 }else if(a<2){
  printf("%d %d %d\n",exist[c-1][d-1][0]-exist[c-1][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]);
 }else{
  printf("%d %d %d\n",exist[c-1][d-1][0]-exist[a-2][d-1][0],exist[c-1][d-1][1]-exist[a-2][d-1][1],exist[c-1][d-1][2]-exist[a-2][d-1][2]);
 }
}
return 0;
}
後半が滅茶苦茶になってしまった><