codeforces628 E. Zbazi in Zeydabad 選擇枚舉對象+用順序減少重複計算+樹狀數組優化

問一個n*m的網格中有多少個z

基本想法應該是枚舉z，我想的是枚舉中間的z，但是好像複雜度太高了，題解的方法是枚舉右上角的z，然後預處理出每個點往左最多的和往左下最多的（nm時間）

枚舉每個xy，判斷以他為右上角的z有多少個，因為對角線可以變短一點，是以要枚舉每個對角線上的點，看右邊最長能不能到y

至此算法複雜度為o（nmm）

想辦法優化，枚舉每一個顯然不怎麼好優化……隻有計算對角線上有哪些能到這個y能想辦法優化，需要知道這條對角線上有多少點能到y，就是求有多少點加上往右的最大值之後能>y，找到重複計算的部分，同一個對角線上，y+最大值可能很大，但是每次都要算一次，浪費了很多時間，是以要從右邊最大的算起，每條對角線上的某個位置，如果以前可以，那麼更小的就也可以是以下次就不用再比較，可是這樣複雜度依然沒有變……需要一個快速求出全部和的方法

就是用樹狀數組（或者線段樹）每次算剛好能到j列的那些，每個對角線儲存一個樹狀數組，就可以利用前面的性質依次計算

好難啊……自己想不出來？

下面是AC代碼，初始化的部分有點麻煩了……不過居然AC也是不容易

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int zl[3001][3001];
int zr[3001][3001];
int zd[3001][3001];
int bit[6005][3005];
int n,m;
int gra[3001][3001];
struct node{
	int x;
	int y;
    node(int a,int b):x(a),y(b){};
};
vector<node> value[3005];//加了之後為j的 

int sum(int k,int i){
	int s = 0;
	while(i > 0){
		s += bit[k][i];
		i -= i & -i;
	}
	return s;
}
    
void add(int j,int i,int x){
	while(i <= m){
		bit[j][i] += x;
		i += i & -i;
	}
}


void init()
{
	for(int i = 1; i <= n; i++){//直接加後面一個就行了，我這樣寫煩了 
		int tem = 0;
	    for(int j = m; j >= 1; j--){
	    	if (gra[i][j] == 'z'){
	    		tem++;
	    		zr[i][j] = tem;
			}
			else tem = 0;
		}
    }
    for(int i = 1; i <= n; i++){
    	int tem = 0;
    	for(int j = 1; j <= m; j++){
    		if (gra[i][j] == 'z'){
    			tem++;
    			zl[i][j] = tem;
			}
			else tem = 0;
		}
	}
	for(int i = 1; i <= n; i++){
		int tem = 0;
		for(int k = 0; i - k >= 1 && 1 + k <= m; k++){
			if (gra[i - k][1 + k] == 'z'){
				tem++;
				zd[i - k][1 + k] = tem;
			} 
			else tem = 0;
		}
	}
	for(int j = 2; j <= m; j++){
		int tem = 0;
		for(int k = 0; (n - k) >= 1 && j + k <= m; k++){
			if (gra[n - k][j + k] == 'z'){
				tem++;
				zd[n - k][j + k] = tem;
			}
			else tem = 0;
		}
	}
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++)
	  value[j + zr[i][j] - 1].push_back(node(i,j));
}

int main()
{
	long long ans = 0;
	memset(bit ,0,sizeof(bit));//清空 
	scanf("%d %d",&n,&m);
	getchar();
	//輸入 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++)
		    scanf("%c",&gra[i][j]);
		getchar(); 
	}
	init();
	for(int j = m; j >= 1; j--){
	    for(int i = 0; i < value[j].size();i++)
	        add(value[j][i].x + value[j][i].y,value[j][i].y,1);// 
	for(int i = 1; i <= n; i++){
	   int len = min(zl[i][j],zd[i][j]); 
	ans += (sum(i + j,j) - sum(i + j,j - len));
    }
}
	printf("%I64d\n",ans);
	return 0;
	}