F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2648 >> 直接查询曼哈顿距离 复杂度是错误的!
GXZlegend @ 2017-12-07 20:38:41
[ Quote ] [ Edit ] [ Delete ] 1#
RT,直接查询的话是斜正方形范围,与KDtree划分平面的横纵直线是交叉的,因此时间复杂度并不能保证。
数据生成器:
#include <bits/stdc++.h>
using namespace std;
int main()
{
/**/freopen("data.in" , "w" , stdout);
/**/int i;
/**/printf("99999 99999\n");
/**/for(i = 1 ; i < 50000 ; i ++ ) printf("%d %d\n" , i , 100001 - i);
/**/printf("50000 50000\n");
/**/for(i = 1 ; i < 50000 ; i ++ ) printf("%d %d\n" , 100001 - i , i);
/**/for(i = 1 ; i <= 99999 ; i ++ ) printf("2 1 1\n");
/**/return 0;
}
可以发现这个数据的数据范围只有10W,远没有达到题目中的50W,而多数题解的时间却出乎意料,达到了30多s,直接被卡到了O(n^2)。
因此个人认为本题正解是旋转坐标系,转化为切比雪夫距离后再查询。
GXZlegend @ 2017-12-07 20:47:05
[ Quote ] [ Edit ] [ Delete ] 2#
貌似下面的数据生成器效果更显著一些:
#include <bits/stdc++.h>
using namespace std;
int main()
{
/**/freopen("data.in" , "w" , stdout);
/**/int i;
/**/printf("99999 99999\n");
/**/for(i = 0 ; i < 49999 ; i ++ ) printf("%d %d\n" , 5 * i + 1 , 499984 - 5 * i);
/**/printf("249992 249992\n");
/**/for(i = 0 ; i < 49999 ; i ++ ) printf("%d %d\n" , 499984 - 5 * i , 5 * i + 1);
/**/for(i = 1 ; i <= 99999 ; i ++ ) printf("2 1 1\n");
/**/return 0;
}
GXZlegend @ 2017-12-07 20:58:17
[ Quote ] [ Edit ] [ Delete ] 3#
PS:没有插入操作,不卡不重构的写法
EdwardFrog @ 2017-12-19 18:03:40
[ Quote ] [ Edit ] [ Delete ] 4#
orz
iloi @ 2017-12-24 21:11:32
[ Quote ] [ Edit ] [ Delete ] 5#
(ಡωಡ)
kczno1 @ 2018-01-03 14:56:43
[ Quote ] [ Edit ] [ Delete ] 6#
然而我瞬间就跑出来了啊
kczno1 @ 2018-01-03 14:56:55
[ Quote ] [ Edit ] [ Delete ] 7#
#include<bits/stdc++.h>
using std::nth_element;
using std::min;

void chmin(int &x,int y)
{
if(x>y)x=y;
}
void chmax(int &x,int y)
{
if(x<y)x=y;
}

const int ch_top=4e7;
char ch[ch_top],*now_r=ch,*now_w=ch-1;
int read()
{
while(*now_r<'-')++now_r;
if(*now_r=='-')
{
int x=*++now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return -x;
}
int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
void write(int x)
{
static char st[20];static short top;
if(!x)*++now_w='0';
else
{
for(;x;x/=10)st[++top]='0'+x%10;
for(;top;--top)*++now_w=st[top];
}
*++now_w='\n';
}

const int N=500005,T=N*2,oo=1000000001;
struct point
{
int x,y,id;
}p[T];int pn;
int rt;
int dy[N];
int qx[N],qy[N];
bool type[N];//0=add 1=ask

bool x_xiao(const point &p1,const point &p2)
{
return p1.x<p2.x||p1.x==p2.x&&p1.y<p2.y;
}
bool y_xiao(const point &p1,const point &p2)
{
return p1.y<p2.y||p1.y==p2.y&&p1.x<p2.x;
}
int f[T],c[T][2];
int mx_x[T],mn_x[T],mx_y[T],mn_y[T];
struct state
{
int f1,f2,f3,f4;
void init(int x,int y)
{
f1=-x+y;f2=x+y;
f3=-x-y;f4=x-y;
}
friend void up(state &x,const state &y)
{
chmin(x.f1,y.f1);
chmin(x.f2,y.f2);
chmin(x.f3,y.f3);
chmin(x.f4,y.f4);
}
}s[T],now;
const state s0=(state){oo,oo,oo,oo};
void sc(int y,int x,bool d)
{
f[x]=y;c[y][d]=x;
up(s[y],s[x]);
chmax(mx_x[y],mx_x[x]);chmax(mx_y[y],mx_y[x]);
chmin(mn_x[y],mn_x[x]);chmin(mn_y[y],mn_y[x]);
}
int build(int l,int r,bool d)
{
int rt=l+r>>1;
if(!d) nth_element(p+l,p+rt,p+r+1,x_xiao);
else nth_element(p+l,p+rt,p+r+1,y_xiao);

if(p[rt].id==N) s[rt].init(mx_x[rt]=mn_x[rt]=p[rt].x,mx_y[rt]=mn_y[rt]=p[rt].y);
else
{
dy[p[rt].id]=rt;s[rt]=s0;mx_x[rt]=mx_y[rt]=-oo;mn_x[rt]=mn_y[rt]=oo;
}

if(rt!=l)sc(rt,build(l,rt-1,!d),0);
if(rt!=r)sc(rt,build(rt+1,r,!d),1);

return rt;
}

//int cnt;
int x,y,a1,a2,a3,a4,a;
int get_dis(int k)
{
if(!k)return oo;
int ans=0;
if(x>mx_x[k])ans+=x-mx_x[k]; else
if(x<mn_x[k])ans+=mn_x[k]-x;
if(y>mx_y[k])ans+=y-mx_y[k]; else
if(y<mn_y[k])ans+=mn_y[k]-y;
return ans;
}
void qiu(int k)
{
if(mx_y[k]<=y)//under
{
if(mx_x[k]<=x) {chmin(a,a3+s[k].f3);return ;}//left
if(mn_x[k]>=x) {chmin(a,a4+s[k].f4);return ;}//right
}
else
if(mn_y[k]>=y)//above
{
if(mx_x[k]<=x) {chmin(a,a1+s[k].f1);return ;}
if(mn_x[k]>=x) {chmin(a,a2+s[k].f2);return ;}
}
//++cnt;
if(p[k].id==N)chmin(a,abs(x-p[k].x)+abs(y-p[k].y));

int cl=c[k][0],cr=c[k][1];
int dl=get_dis(cl),dr=get_dis(cr);
if(dl<dr)
{
if(dl>=a)return ;qiu(cl);
if(dr>=a)return ;qiu(cr);
}
else
{
if(dr>=a)return ;qiu(cr);
if(dl>=a)return ;qiu(cl);
}
}

int up_to_f(int k)
{
p[k].id=N;
now.init(x=p[k].x,y=p[k].y);
for(;k;k=f[k])
{up(s[k],now);
chmax(mx_x[k],x);chmin(mn_x[k],x);
chmax(mx_y[k],y);chmin(mn_y[k],y);
}
}

int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
fread(ch,1,ch_top,stdin);
int n=read(),m=read(),i;
for(i=1;i<=n;++i) p[i]=(point){read(),read(),N};
pn=n;
for(i=1;i<=m;++i)
{
while(*now_r<'0')++now_r;
if(*now_r++=='1')
{
p[++pn]=(point){read(),read(),i};
}
else
{
type[i]=1;
qx[i]=read();qy[i]=read();
}
}
rt=build(1,pn,0);
for(i=1;i<=m;++i)
if(type[i])
{
//cnt=0;
x=qx[i];y=qy[i];a=oo;a1=x-y;a2=-x-y;a3=x+y;a4=y-x;
qiu(rt);
//write(cnt);
//if(clock()>3000)break;
//write(min(a,min(min(min(a1+x-y,a2-x-y),a3+x+y),a4+y-x)));
write(a);
}
else up_to_f(dy[i]);
fwrite(ch,1,now_w-ch+1,stdout);
}
[Top] [Previous Page] [Next Page]

HOME Back