cf 611 A||codeforces goodbye 2015 C. New Year and Domino

http://codeforces.com/contest/611/problem/C
题意:给出一个n*m的地图,.表示可以空,#表示墙。一个东西需要占两个相邻的格子,问给定一个矩形,放一个东西的方案数。
思路:q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下,每次标记到后一个点。然后二维的前缀和。然后每次询问的时候,去掉最上边和最左边两条边界上对应的多加的点。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz