题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 510,M=3e5+10;
typedef pair<int, int> PII;
int a[N][N];
int len;
PII res[M];
map<int,PII> mp;
int get(int x){
return len/x;
}
struct node{
int x,y,xx,yy,id;
bool operator<(node& b)
{
return x/len==b.x/len?(y/len==b.y/len?(xx/len==b.xx/len?yy<b.yy:xx<b.xx):y<b.y):x<b.x; //B为分块大小
}
}q[M];
int resx,resy,resmx;
void add(int val,int i,int j){
}
int main()
{
cin>>n>>m;
len=(int)sqrt(500);
for(int i=1;i<=n;i++){
int x,y,c;
cin>>x>>y>>c;
g[x][y]=max(g[x][y],c);
}
//l1,l2,r1,r2
//x1 x2 y1 y2
for(int i=1;i<=m;i++){
cin>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2;
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int x=1,y=1,xx=0,yy=0;
for(int i=1;i<=m;i++)
{
while (x>q[i].x)
{
--x;
for (j=y;j<=yy;++j)
{
add(a[x][j],x,j);
}
}
while (xx<q[i].xx)
{
++xx;
for (j=y;j<=yy;++j)
{
add(a[xx][j]);
}
}
while (y>q[i].y)
{
--y;
for (j=x;j<=xx;++j)
{
add(a[j][y]);
}
}
while (yy<q[i].yy)
{
++yy;
for (j=x;j<=xx;++j)
{
add(a[j][yy]);
}
}
while (x<q[i].x)
{
for (j=y;j<=yy;++j)
{
del(a[x][j]);
}
++x;
}
while (xx>q[i].xx)
{
for (j=y;j<=yy;++j)
{
del(a[xx][j]);
}
--xx;
}
while (y<q[i].y)
{
for (j=x;j<=xx;++j)
{
del(a[j][y]);
}
++y;
}
while (yy>q[i].yy)
{
for (j=x;j<=xx;++j)
{
del(a[j][yy]);
}
--yy;
}
out[q[i].id]=ans;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla