题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N =510,S=2e5+10,M=18;
struct node{
    int x,y,z;
};
node f[N][N][N];
int n,m;
int a[N][N];
node Max(node a,node b){
    int x1=a.x,y1=a.y,z1=a.z;
     int x2=b.x,y2=b.y,z2=b.z;
    if(z1>z2) return a;
    if(z2>z1) return b;
    if(x1<x2) return a;
    if(x2<x1) return b;
    if(x1==x2&&y1<=y2) return a;
}
void init(int x){
    for(int j=0;j<M;j++){
        for(int i=0;i+(1<<j)-1<=500;i++){
            if(!j) f[x][i][j]={x,i,a[x][i]};
            else f[x][i][j]=Max(f[x][i][j-1],f[x][i+(1<<j)-1][j-1]);
        }
    }
}
node query(int x,int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return Max(f[x][l][k],f[x][r-(1<<k)+1][k]);
}
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y,z;cin>>x>>y>>z;
        a[x][y]=max(a[x][y],z);
    }
    for(int i=0;i<=500;i++){
        init(i);
    }
    while(m--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        node res={x1,y1,a[x1][y1]};
        for(int i=x1;i<=x2;i++)
        {
            res=Max(res,query(i,y1,y2));
        }
        if(res.z==0) cout<<"-1\n";
        else
        cout<<res.x<<" "<<res.y<<" "<<res.z<<"\n";
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla