cf 611 A||codeforces goodbye 2015 C. New Year and Domino
http://codeforces.com/contest/611/problem/C 题意：给出一个n*m的地图，.表示可以空，#表示墙。一个东西需要占两个相邻的格子，问给定一个矩形，放一个东西的方案数。 思路：q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下，每次标记到后一个点。然后二维的前缀和。然后每次询问的时候，去掉最上边和最左边两条边界上对应的多加的点。
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10
11using namespace std;
12
13const int N=5E2+7;
14char maze[N][N];
15int n,m;
16int q;
17int a[N][N],b[N][N];
18int sum[N][N];
19int sum2[N][N];
20
21int main()
22{
23 cin>>n>>m;
24 memset(a,0,sizeof(a));
25 memset(b,0,sizeof(b));
26 for ( int i = 0 ; i< n ;i++ ) scanf("%s",maze[i]);
27 for ( int i = 1 ; i < n ; i++)
28 {
29 for (int j = 0 ; j< m ;j++)
30 {
31 if (maze[i][j]=='.'&&maze[i-1][j]=='.')
32 a[i+1][j+1]++;
33 }
34 }
35
36 for ( int i = 0 ; i < n ; i++)
37 {
38 for ( int j = 1 ; j < m ; j++)
39 {
40 if (maze[i][j]=='.'&&maze[i][j-1]=='.')
41 b[i+1][j+1]++;
42 }
43 }
44 sum[0][0] = 0;
45 sum2[0][0] = 0;
46 for ( int i = 1 ; i <= n ; i++)
47 {
48 for ( int j = 1 ; j<= m ; j++)
49 {
50 sum[i][j] =sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
51 sum2[i][j] = sum2[i-1][j]+sum2[i][j-1]-sum2[i-1][j-1] + b[i][j];
52 }
53 }
54 cin>>q;
55
56 while (q--)
57 {
58 int n1,n2,m1,m2;
59 scanf("%d %d %d %d",&n1,&m1,&n2,&m2);
60 int ans = 0 ;
61 ans+=sum[n2][m2]-sum[n1-1][m2]-sum[n2][m1-1]+sum[n1-1][m1-1];
62 ans+=sum2[n2][m2]-sum2[n1-1][m2]-sum2[n2][m1-1]+sum2[n1-1][m1-1];
63 for ( int j = m1 ; j <= m2 ;j++)
64 {
65 if (a[n1][j]==1) ans--;
66 }
67 for ( int i = n1 ; i <= n2 ; i++)
68 {
69 if (b[i][m1]==1) ans--;
70 }
71
72 printf("%d\n",ans);
73 }
74
75 return 0;
76}