题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 610;
int l[N][N*4],r[N][N*4],mx[N][N*4];
int n,m;
int x[N],y[N],s[N];
int a[N][N];
struct node{
int l,r;
int mx,v;
};
node tr[N][4*N];
void pushup(int x,int u){
if(tr[x][u<<1].mx>=tr[x][u<<1|1].mx){
tr[x][u]=tr[x][u<<1];
}
else tr[x][u]=tr[x][u<<1|1];
//tr[x][u].mx=max(tr[x][u<<1].mx,tr[x][u<<1|1].mx);
}
void build(int x,int u,int l,int r){
tr[x][u]={l,r,0};
if(l==r){
//tr[x][u].mx=a[x][l];
return ;
}
else{
int mid=l+r>>1;
build(x,u<<1,l,mid);
build(x,u<<1|1,mid+1,r);
// pushup(x,u);
}
}
void modify(int x,int u,int l,int r,int y)
{
if(tr[x][u].l==y&&tr[x][u].r==y)
{
tr[x][u].mx=a[x][y];
tr[x][u].v=y;
return ;
}
else{
int mid=l+r>>1;
if(y<=mid) modify(x,u<<1,l,mid,y);
else modify(x,u<<1|1,mid+1,r,y);
pushup(x,u);
}
}
node query(int x,int u,int L,int R,int l,int r)
{
if(l<=tr[x][u].l&&tr[x][u].r<=r)
{
return tr[x][u];
}
int mid=tr[x][u].l+tr[x][u].r>>1;
node res={0,0,0,0};
if(l<=mid) res=query(x,u<<1,L,mid,l,r);
if(r>mid)
{
auto t=query(x,u<<1|1,mid+1,R,l,r);
if(t.mx>res.mx)
{
res=t;
}
}
return res;
}
int main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i]>>s[i];
a[x[i]][y[i]]=max(a[x[i]][y[i]],s[i]);
}
for(int i=0;i<=500;i++)
{
build(i,1,0,500);
}
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++)
{
modify(i,1,0,500,j);
}
}
//cout<<query(2,1,0,500,1,2).mx<<endl;
while(m--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
node res={0,0,0};
for(int i=x1;i<=x2;i++)
{
auto t=query(i,1,0,500,y1,y2);
if(t.mx>res.mx){
res.mx=t.mx;
res.l=i,res.r=t.l;
res.v=t.v;
}
}
if(res.mx==0)
{
cout<<"-1\n";
}
else cout<<res.l<<" "<<res.v<<" "<<res.mx<<"\n";
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla