간단 한 중위 2 점.

단순 한 중위 수
주어진 n×m 의 행렬 과 q 번 의 질문 은 매번 4 개의 값 을 포함 하여 각각 a, b, c, d 는 왼쪽 상단 이 (a, b) 오른쪽 아래 가 (c, d) 인 서브 행렬 을 대표 합 니 다. 이 서브 행렬 의 중위 수 는 얼마 입 니까? 만약 에 행렬 의 개수 가 짝수 라면 중간 이 작은 수 를 취하 십시오.행렬 의 수가 1, 2, 3, 4 인 경우 정 답 은 2 입 니 다.
입력 형식
한 줄 한 정수 TT (1 < T < 100) 대표 TT 그룹 데이터
두 번 째 줄 세 개의 정수 n, m, q (1 ≤ n, m ≤ 100, 1 ≤ q ≤ 100000) 는 행렬 의 행렬 과 문의 횟수 를 대표 한다.모든 데이터 n×m 의 총 계 는 3e5 를 초과 하지 않 고 qq 의 총 계 는 1e6 를 초과 하지 않 습 니 다.
다음 n 행 m 개 수 Aij 는 초기 행렬 의 요 소 를 대표 합 니 다 (1 ≤ Aij ≤ 500)
마지막 q 행, 각 행 4 개 정수 a, b, c, d, (1 ≤ a ≤ c ≤ n, 1 ≤ b ≤ d ≤ m)
출력 형식
각 그룹의 데이터 출력 q 줄 마다 답
출력 할 때 줄 끝의 빈 칸 은 답 의 정확성 에 영향 을 주지 않 습 니 다.
샘플 입력

1
5 5 2
5 4 3 2 1
10 11 12 13 25
9 8 7 6 14
15 16 17 18 19
24 23 22 21 20
5 1 5 5
2 1 5 5

샘플 출력

22
15

문 제 를 보고 나 서 야 2 점 을 썼 다 는 것 을 알 았 다.ch [ans] [i] [j] 는 중위 수가 ans 일 때의 접두사 와 a [i] < = ans 일 때 val = 1 - 1 그렇지 않 으 면 val = 1 이다.하지만 여러 값 이 중복 되면 어떻게 해 야 할 지 잘 모 르 겠 어 요.예 를 들 어 a 1, a 2, a 3,..., a i,..., a m i d,... a j,..., a n a1, a_2, a_3, \dots ,a_i, \dots ,a_{mid}, \dots a_j, \dots, a_a1, a2, a3,..., ai,..., amid,... aj,..., an, 그리고 a i = a i + 1 = = a m i d =... a j ai=a_{i+1}= \dots =a_{mid}=\dots a_j ai = ai + 1 = amid =.............................................................................

#include
using namespace std;
const int inf=0x3f3f3f3f,mod=1e9+7,MAXN=102;
#define lowbit(x) ((x)&(-x))
#define Init(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
int a[MAXN][MAXN],ch[501][MAXN][MAXN],n,m,q;
bool vis[501];
void get(int k){//k     
    vis[k]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]<=k)ch[k][i][j]=-1;
            else ch[k][i][j]=1;
            ch[k][i][j]+=ch[k][i-1][j]+ch[k][i][j-1]-ch[k][i-1][j-1];
        }
    }
}
int x,y,xx,yy;
int check(int ans){
    if(!vis[ans])get(ans);
    return ch[ans][xx][yy]-ch[ans][xx][y-1]-ch[ans][x-1][yy]+ch[ans][x-1][y-1];
}
int main() {
    int t=0;
    scanf("%d",&t);
    while(t--){
        Init(vis,0);
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                scanf("%d",&a[i][j]);
        while(q--){
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            int l=1,r=500,num=(xx-x+1)*(yy-y+1);
            if(num&1){
                while(l<r){
                    int mid=(l+r)>>1;
                    if(check(mid)>-1)l=mid+1;
                    else r=mid;
                }
            }else{
                while(l<r){
                    int mid=(l+r)>>1;
                    if(check(mid)>0)l=mid+1;
                    else r=mid;
                }
            }
            printf("%d
",r);
        }
    }
    return 0;
}