ECNU 2018 10月月赛 E 盖房子 （bitset + 倍增）

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b)	for (int i(a); i <= (b); ++i)
#define	dec(i,b)	for (int i(a); i >= (b); --i)
#define	fi		first
#define	se		second
#define	MP		make_pair

typedef long long LL;

const int N = 1e3 + 10;

bitset <102> f[N][N][10],g[N][N][10],ff[N][N][10],gg[N][N][10];
int n,m,q;
int T;
int lg[N + 10];

inline int check(int x,int y){
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main(){

	lg[1] = 0;
	rep(i,2,1001) lg[i] = lg[i >> 1] + 1;
	scanf("%d%d",&n,&m);


	rep(i,1,n){
		rep(j,m){
			int x;
			scanf("%d",&x);
			f[i][j][0].set(x);
			g[i][j][0].set(x);
			ff[i][j][0].set(x);
			gg[i][j][0].set(x);
		}
	}


	rep(k,9){
		rep(i,n){
			rep(j,m){
				int xx,yy,zz = 1 << (k - 1);
				f[i][j][k] |= f[i][j][k - 1];
				xx = i - zz;
				yy = j;

				if (check(xx,yy)) f[i][j][k] |= f[xx][yy][k - 1];

				xx = i;
				yy = j + zz;
				if (check(xx,yy)) f[i][j][k] |= f[xx][yy][k - 1];

				xx = i - zz;
				yy = j + zz;
				if (check(xx,yy)) f[i][j][k] |= f[xx][yy][k - 1];


				ff[i][j][k] |= ff[i][j][k - 1];


				xx = i + zz;
				yy = j;
				if (check(xx,yy)) ff[i][j][k] |= ff[xx][yy][k - 1];
                        

				xx = i;
				yy = j + zz;
				if (check(xx,yy)) ff[i][j][k] |= ff[xx][yy][k - 1];
				
				
				xx = i + zz;
				yy = j + zz;
				if (check(xx,yy)) ff[i][j][k] |= ff[xx][yy][k - 1];
                
			}
		}
	}
	
	rep(k,zz = 1 << (k - 1);
				g[i][j][k] |= f[i][j][k - 1];
				xx = i - zz;
				yy = j;
				if (check(xx,yy)) g[i][j][k] |= g[xx][yy][k - 1];
				
				xx = i;
				yy = j + zz;
				if (check(xx,yy)) g[i][j][k] |= g[xx][yy][k - 1];
				
				gg[i][j][k] |= ff[i][j][k - 1];
				xx = i + zz;
				yy = j;
				if (check(xx,yy)) gg[i][j][k] |= gg[xx][yy][k - 1];
				
				xx = i;
				yy = j + zz;
				if (check(xx,yy)) gg[i][j][k] |= gg[xx][yy][k - 1];
				
			}
		}
	}

	scanf("%d",&q);
	while (q--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);

		if (z == 1){
			puts("1");
			continue;
		}

		int c = lg[z];

		bitset <102> ret;

		int xx,zz = 1 << c;

		xx = x - z + zz;
		yy = y;

		ret |= g[xx][yy][c];
		
		xx = x;
		yy = y + z - zz;

		ret |= g[xx][yy][c];

		int t = (z) >> 1;

		int l = lg[t],ll = 1 << l;

		ret |= f[x][y][l];

		xx = x - t + ll;
		yy = y;
		ret |= f[xx][yy][l];

		xx = x;
		yy = y + t - ll;
		ret |= f[xx][yy][l];

		xx = x - t + ll;
		yy = y + t - ll;
		ret |= f[xx][yy][l];

		xx = x + z - zz;
		yy = y;
		ret |= gg[xx][yy][c];

		xx = x;
		yy = y + z - zz;
		ret |= gg[xx][yy][c];

		ret |= ff[x][y][l];
		xx = x + t - ll;
		yy = y;
		ret |= ff[xx][yy][l];

		xx = x;
		yy = y + t - ll;
		ret |= ff[xx][yy][l];

		xx = x + t - ll;
		yy = y + t - ll;
		ret |= ff[xx][yy][l];

		printf("%dn",(int)ret.count());
	}

	return 0;

}