Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include <bits/stdc++.h>
- #include <stdio.h>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #define PI 3.14159265
- #define N 300+5
- #define ll long long
- #define INF 2147483647
- using namespace std;
- int st[N][N][9];//2^9>300
- int g[N][N],n,x1,Y1,x2,y2,m,level,nq,maxi,from,to;
- void RMQ2d(int x1,int Y1,int x2,int y2){
- if(x1>x2) swap(x1,x2);
- from=min(Y1,y2);
- to=max(Y1,y2);
- level=log2(to-from+1);
- maxi=-9999;
- for(int i=x1;i<=x2;i++) maxi=max(maxi,max(st[i][from][level],st[i][to+1-(1<<level)][level]));//這裡不能從from加 要用to減是因為要分割的數組塊長度可能為奇數 且st[][]只記錄前標及長度 所以會出錯 例如分割1234567 錯的:1234 5678 對的:1234 4567
- }
- void build(){
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++) st[i][j][0]=g[i][j];
- for(int level=1;level<=log2(m);level++)
- for(int from=0;from+(1<<(level-1))-1<m;from++){//因為數組長最短=1 所以前標最大為from+(1<<(level-1))-1
- st[i][from][level]=max(st[i][from][level-1],st[i][from+(1<<(level-1))][level-1]);
- }
- }
- }
- int main(){
- while(scanf("%d%d",&n,&m)!=EOF){
- for(int i=0;i<n;i++)
- for(int j=0;j<m;j++) scanf("%d",&g[i][j]);
- build();
- scanf("%d",&nq);
- while(nq--){
- scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
- x1--; Y1--; x2--; y2--;
- RMQ2d(x1,Y1,x2,y2);
- if(g[x1][Y1]==maxi||g[x1][y2]==maxi||g[x2][Y1]==maxi||g[x2][y2]==maxi)
- printf("%d yes\n",maxi);
- else printf("%d no\n",maxi);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement