codeforces611C

New Year and Domino

CodeForces - 611C

他们说：“每一年都像多米诺骨牌，一个接一个地倒下去”。但是，一年能够像多米诺骨牌那样放在网格中吗？我不这么认为。

Zydsg最近得到了一个有h行和w列的矩形网格。每个单元格是一个正方形，可以是空的（用'.'表示）或非空的（用“＃”表示）。行从上到下编号为1到h。列从左到右编号为1到w。

另外，Zydsg有一个多米诺骨牌。他想把它放在一个网格的某个地方。多米诺骨牌将占据两个相邻的单元格，位于一行或一列中。两个相邻的单元必须是空的，并且必须位于网格内。

Zydsg需要更多的乐趣，因此他会考虑一些问题。在每个查询中，他选择了网格上的一个矩形，有多少种方法可以在所选矩形内部放置一个多米诺骨牌？

Input

输入的第一行包含两个整数h和w（1≤h，w≤500） - 行数和列数。

接下来的h行描述一个网格。每行包含一个长度为w的字符串。每个字符都是“.”或“＃” - 分别表示一个空的或非空的单元格。

下一行包含一个整数q（1≤q≤100 000） - 查询的数量。

接下来q行包含四个整数r1i，c1i，r2i，c2i（1≤r1i≤r2i≤h，1≤c1i≤c2i≤w）代表第i个查询。数字r1i和c1i分别表示矩形的左上角单元格的行和列（分别）。数字r2i和c2i分别表示矩形的右下角单元格的行和列。

Output

打印q个整数，第i个应等于在第i个矩形内放置单个多米诺骨牌的方法的数量。

Example

Input

5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8

Output

Input

7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8

Output

Note

A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.

sol：这不是二维前缀和裸题（假）吗，但是写了一会发现这个东西非常操蛋，而且复杂度也是Q*n的（可能预处理还会更劣）
于是果断弃疗。对于每行每列分别维护前缀和，查询的时候统计每行每列的答案和，n³+Q*n的复杂度可以接受

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

int n,m,Q,Qzh_X[N][N],Qzh_Y[N][N];

char Map[N][N];

int main()

{

    int i,j,k;

    R(n); R(m);

    for(i=;i<=n;i++)

    {

        scanf("%s",Map[i]+);

    }

    for(i=;i<=n;i++)

    {

        Qzh_X[i][]=;

        for(j=;j<=m;j++)

        {

            Qzh_X[i][j]=Qzh_X[i][j-]+(Map[i][j]=='.'&&Map[i][j-]=='.');

        }

    }

    for(j=;j<=m;j++)

    {

        Qzh_Y[][j]=;

        for(i=;i<=n;i++)

        {

            Qzh_Y[i][j]=Qzh_Y[i-][j]+(Map[i][j]=='.'&&Map[i-][j]=='.');

        }

    }

    R(Q);

    while(Q--)

    {

        int x1=read(),y1=read(),x2=read(),y2=read(),Sum=;

        for(i=x1;i<=x2;i++) Sum+=Qzh_X[i][y2]-Qzh_X[i][y1];

        for(i=y1;i<=y2;i++) Sum+=Qzh_Y[x2][i]-Qzh_Y[x1][i];

        Wl(Sum);

    }

    return ;

}

/*

input

5 8

....#..#

.#......

##.#....

##..#.##

........

4

1 1 2 3

4 1 4 1

1 2 4 5

2 5 5 8

output

4

0

10

15

input

7 39

.......................................

.###..###..#..###.....###..###..#..###.

...#..#.#..#..#.........#..#.#..#..#...

.###..#.#..#..###.....###..#.#..#..###.

.#....#.#..#....#.....#....#.#..#..#.#.

.###..###..#..###.....###..###..#..###.

.......................................

6

1 1 3 20

2 10 6 30

2 10 7 30

2 2 7 7

1 7 7 7

1 8 7 8

output

53

89

120

23

0

2

*/

巴特西

codeforces611C

New Year and Domino

最新文章

热门文章