第１０回日本情報オリンピック 本選 「惑星探査」

二次元累積和やるだけ。

#include <utility>
#include <sstream>
#include <cstdio>
#include <string>
#include <set>
#include <iostream>
using namespace std;
char s[1002][1002];
int dp[1002][1002][3];
int main(){
	
	int m,n,k;
	scanf("%d%d%d",&m,&n,&k);

	for(int i = 0;i < m;i++){
		scanf("%s",s[i]);
	}
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			for(int l = 0;l < 3;l++){
				dp[i][j][l] = dp[i-1][j][l] + dp[i][j-1][l] - dp[i-1][j-1][l];
			}
			switch(s[i-1][j-1]){
				case 'J':
					dp[i][j][0]++;
					break;
				case 'O':
					dp[i][j][1]++;
					break;
				case 'I':
					dp[i][j][2]++;
					break;
			}
		}
	}
	while(k--){
		int a,b,c,d;

		scanf("%d%d%d%d",&a,&b,&c,&d);
		int ans[3];
		for(int i = 0;i < 3;i++){
			ans[i] = dp[c][d][i] + dp[a-1][b-1][i] - dp[a-1][d][i] - dp[c][b-1][i];
		}
		printf("%d %d %d\n",ans[0],ans[1],ans[2]);

	}

	return 0;

}