Codeforces 611C New Year and Domino DP+容斥

"#"代表不能放骨牌的地方，"."是可以放 500*500的矩阵，q次询问

开两个dp数组，a,b,a统计横着放的方案数，b表示竖着放，然后询问时O(1)的，容斥一下，复杂度O（n^2+q)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstdlib>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

const int maxn=;

int a[maxn][maxn];

int b[maxn][maxn];

char s[maxn][maxn];

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

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

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

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

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

        {

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

            {

                int k=;

                if(s[i][j]=='.'&&s[i][j-]=='.')k=;

                a[i][j]+=a[i][j-]+a[i-][j]-a[i-][j-]+k;

                k=;

                if(s[i-][j]=='.'&&s[i][j]=='.')k=;

                b[i][j]+=b[i-][j]+b[i][j-]-b[i-][j-]+k;

            }

        }

        int q;

        scanf("%d",&q);

        while(q--)

        {

            int x,y,l,r;

            scanf("%d%d%d%d",&x,&y,&l,&r);

            int t1=a[l][r]-a[l][y]-a[x-][r]+a[x-][y];

            int t2=b[l][r]-b[l][y-]-b[x][r]+b[x][y-];

            printf("%d\n",t1+t2);

        }

    }

    return ;

}