[TIOJ] 1134. 1.蓋房子問題

題目連結:http://tioj.infor.org/problems/1134

---

想了想覺得把1換成-1, 0換成1之後會有好事情，然後似乎可以做類似最大子矩陣的方式，但是我不知道該怎麼用。
被雷了之後才發現其實我只要把兩個問題合在一起就好了，一個是最大子矩陣，一個是某種找有多少大於零的序列的問題。首先我們可以先對一維用前綴和之後枚舉頂跟底，接著就變成一維的問題了，變成一維的問題後就是要問說對於所有大於零的序列中，最長是多少，作法也是考慮枚舉前綴和，每次只要查小於當前前綴和的所有鍵值中最小的值是多少，接著就把當前前綴和當做鍵值，現在的位置當作值插到某種資料結構就好了。

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x), end(x)
const int N = 200 + 5;
const int INF = 1<<30;

class LiSan{
	private:
		vector<int> vv;
	public:
		inline void init(){vv.clear();}
		inline void insert(int x){vv.push_back(x);}
		inline void done(){
			sort(ALL(vv));
			vv.resize(distance(vv.begin(), unique(ALL(vv))));
		}
		inline int size(){return vv.size();}
		inline int get(int x){
			return distance(vv.begin(), lower_bound(ALL(vv), x));
		}
		inline int inv_get(int x){return vv[x];}
} lisan;

class BIT{
	private:
		vector<int> arr;
		int n;
		inline int lowbit(int x){return x&(-x);}
	public:
		void init(int n_){
			n = n_;
			arr.resize(n);
			fill(ALL(arr), INF);
		}
		int query(int x){
			int ret = INF;
			while(x){
				ret = min(ret, arr[x]);
				x -= lowbit(x);
			}
			return ret;
		}
		void modify(int p, int v){
			while(p < n){
				arr[p] = min(arr[p], v);
				p += lowbit(p);
			}
		}
} bit;

int arr[N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		int n, m, ans = 0; cin>>n>>m;
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
			cin >> arr[i][j];
			arr[i][j] = !arr[i][j];
			arr[i][j] = arr[i][j]*2 - 1;
			arr[i][j] += arr[i-1][j];
		}
		for(int i=1;i<=n;i++) for(int ii=0;ii<i;ii++){
			lisan.init();
			{
				int pre = 0;
				lisan.insert(0);
				for(int j=1;j<=m;j++){
					pre += arr[i][j] - arr[ii][j];
					lisan.insert(pre);
					lisan.insert(pre-1);
				}
			}
			lisan.done();
			bit.init(lisan.size()+1);
			bit.modify(lisan.get(0)+1, 0);
			int pre = 0;
			for(int j=1;j<=m;j++){
				pre += arr[i][j] - arr[ii][j];
				int wh = bit.query(lisan.get(pre-1)+1);
				if(wh!=INF) ans = max(ans, (j-wh)*(i-ii));
				bit.modify(lisan.get(pre)+1, j);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}