TIOJ 1483 電腦檢查 [BIT]

4    75098    poao899    15712K    10230MS    G++     1.06K     2010-04-10 12:42:54                       .


第一次寫樹狀數組

然後就愛上他了˙////////˙




是說一開始陣列開太小一直RE

//*****************************************

#include<algorithm>
#define MOD 1000000007
#define lb(x) ((x)&(-x))
int bit[1010][1010], r, c, T, cnt;
int qry(int i, int j){
	int ret= 0;
	for(; i>0; i-=lb(i))
		for(int jj=j; jj>0; jj-=lb(jj)){
			ret+= bit[i][jj];
			ret%=MOD;
		}
	return ret;
}
void adj(int i, int j, int v){
	for(; i<=r; i+=lb(i))
		for(int jj=j; jj<=c; jj+=lb(jj)){
			bit[i][jj]+= v;
			bit[i][jj]%=MOD;
		}
}
struct com{
	int i,j,h;
	bool operator<(const com &b)const{
		return h<b.h|| ( h==b.h&& (i>b.i|| i==b.i&&j>b.j ) );
	}
	void get(int a, int b){
		scanf("%d", &h);
		i= a; j= b;
	}
}cc[1001000];
int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &r, &c);
		//Init
		cnt= 0;
		for(int i=1; i<=r; i++)
			for(int j=1; j<=c; j++)
				bit[i][j]= 0;
		for(int i=1; i<=r; i++)
			for(int j=1; j<=c; j++)
				cc[cnt++].get(i, j);
		std::sort(cc, cc+cnt);
		for(int i=0; i<cnt; i++){
			int ii=cc[i].i, jj=cc[i].j;
			adj(ii, jj, qry(ii, jj)+1);
		}
		printf("%d\n", qry(r, c));
	}
}