luogu 4169[Violet]エンジェルドール/SJY振り駒
14420 ワード
タイトルの説明
問題:
cdqで1つの点の左下の最も近い点の距離を分治して、それから座標系が回転します.
コード:
転載先:https://www.cnblogs.com/LiGuanlin1124/p/10192249.html
問題:
cdqで1つの点の左下の最も近い点の距離を分治して、それから座標系が回転します.
コード:
#include
#include
#include
using namespace std;
#define N 300050
const int inf = 0x7fffffff;
inline int rd()
{
int f=1,c=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}
return f*c;
}
int n,m,ans[N],cnt,maxx,maxy;
struct pnt
{
int x,y,tm,wt,id;
}p[2*N],tmp[2*N];
struct Pair
{
int x,id;
}px[2*N],py[2*N];
int tx[2*N],ty[2*N];
bool cmp(Pair a,Pair b)
{
return a.x<b.x;
}
bool cmpt(pnt a,pnt b)
{
if(a.tm!=b.tm)return a.tm<b.tm;
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
void rev_x()
{
for(int i=1;i<=n;i++)
p[i].x = maxx-p[i].x;
sort(p+1,p+1+n,cmpt);
for(int i=1;i)
{
if(maxx-i>i)
swap(tx[i],tx[maxx-i]);
tx[i]=-tx[i];
}
}
void rev_y()
{
for(int i=1;i<=n;i++)
p[i].y = maxy-p[i].y;
sort(p+1,p+1+n,cmpt);
for(int i=1;i)
{
if(maxy-i>i)
swap(ty[i],ty[maxy-i]);
ty[i]=-ty[i];
}
}
struct BIT
{
int f[2*N];
void init(){for(int i=1;i<=maxy;i++)f[i]=-inf;}
void up(int x,int d){while(x<2*N)f[x]=max(f[x],d),x+=(x&-x);}
int down(int x)
{
int ret = -inf;
while(x)ret=max(ret,f[x]),x-=(x&-x);
return ret;
}
void clear(int x){while(x<2*N&&f[x]!=-inf)f[x]=-inf,x+=(x&-x);}
}tr;
void Sort(int l,int r)
{
int mid = (l+r)>>1;
int i = l,j = mid+1,k = l;
while(i<=mid&&j<=r)
{
while(i<=mid&&p[i].x<=p[j].x)
{
tmp[k] = p[i];
i++,k++;
}
while(j<=r&&p[i].x>p[j].x)
{
tmp[k] = p[j];
j++,k++;
}
}
while(i<=mid)
{
tmp[k] = p[i];
i++,k++;
}
while(j<=r)
{
tmp[k] = p[j];
j++,k++;
}
for(i=l;i<=r;i++)p[i]=tmp[i];
}
void cdq(int l,int r)
{
if(l==r)return ;
int mid = (l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
Sort(l,mid),Sort(mid+1,r);
int i = l,j = mid+1;
while(j<=r)
{
while(i<=mid&&p[j].x>=p[i].x)
{
if(p[i].wt)tr.up(p[i].y,tx[p[i].x]+ty[p[i].y]);
i++;
}
if(p[j].id)
{
int now = tr.down(p[j].y);
if(now!=-inf)ans[p[j].id] = min(ans[p[j].id],tx[p[j].x]+ty[p[j].y]-now);
}
j++;
}
for(i=i-1;i>=l;i--)
if(p[i].wt)tr.clear(p[i].y);
}
int main()
{
n = rd(),m = rd();
for(int i=1;i<=n;i++)
{
px[i].x = rd(),px[i].id = i;
py[i].x = rd(),py[i].id = i;
p[i].tm = 0,p[i].wt = 1,p[i].id = 0;
}
for(int opt,x,y,i=1;i<=m;i++)
{
opt = rd(),x = rd(),y = rd();
n++;
px[n].x = x,px[n].id = n;
py[n].x = y,py[n].id = n;
if(opt==1)
{
p[n].tm = i,p[n].wt = 1,p[n].id = 0;
}else
{
cnt++;
p[n].tm = i,p[n].wt = 0,p[n].id = cnt;
}
}
memset(ans,0x3f,sizeof(ans));
sort(px+1,px+1+n,cmp);
sort(py+1,py+1+n,cmp);
for(int las=-1,i=1;i<=n;i++)
{
if(las!=px[i].x)las=px[i].x,maxx++,tx[maxx]=las;
p[px[i].id].x = maxx;
}
for(int las=-1,i=1;i<=n;i++)
{
if(las!=py[i].x)las=py[i].x,maxy++,ty[maxy]=las;
p[py[i].id].y = maxy;
}
maxx++,maxy++;
tr.init();
sort(p+1,p+1+n,cmpt);
cdq(1,n);
rev_x();
cdq(1,n);
rev_y();
cdq(1,n);
rev_x();
cdq(1,n);
for(int i=1;i<=cnt;i++)
printf("%d
",ans[i]);
return 0;
}
転載先:https://www.cnblogs.com/LiGuanlin1124/p/10192249.html