题意

一个平面上有$n$个点，$m$次操作，每次新增一个点，或者是询问离某个点最近的点的距离。这里的距离是曼哈顿距离。

$n,m\le3*10^5$

sol

写一发$CDQ$。

只考虑询问点在其他点的右上方的情况，假设询问点是$A$，那么所求的距离就是$(X_A-X_i)+(Y_A-Y_i)=(X_A+Y_A)-(X_i+Y_i)$。

所以我们只需要找出满足$X_i \le X_A,Y_i \le Y_A$中$X_i+Y_i$的最大值就好了。

$CDQ$前先按时间戳排序，向上归并时按$X$排序。考虑左边对右边的贡献时，按$Y$值为下标插入树状数组，然后查询前缀最大值。

对于不在右上方的情况，只要把坐标轴翻转四次就可以了。

然而。
这题卡常。
以下是一些卡常技巧。
>清空树状数组的时候，如果当前位已经是$0$就直接$return$。
预先记录按照时间戳的排序，每次$CDQ$完后直接复制一遍，不需要排序。
删除不必要的点（不会被任何询问考虑到的点）

常数巨大无比。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 1e6+5;

struct node{

	int tim,opt,x,y;

	bool operator < (const node &b) const

		{

			if (x!=b.x) return x<b.x;

			if (y!=b.y) return y<b.y;

			return opt<b.opt;

		}

}a[N],p[N],q[N];

int n,m,X,Y,c[N],ans[N];

inline void modify(int k,int v){while(k<=Y)c[k]=max(c[k],v),k+=k&-k;}

inline int query(int k){int s=0;while(k)s=max(s,c[k]),k-=k&-k;return s;}

inline void clear(int k){while(k<=Y)if(c[k])c[k]=0,k+=k&-k;else return;}

void CDQ(int l,int r)

{

	if (l==r) return;

	int mid=l+r>>1;CDQ(l,mid);CDQ(mid+1,r);

	int L=l,R=mid+1;

	for (int i=l;i<=r;++i)

		if (L<=mid&&(R>r||p[L]<p[R]))

		{

			q[i]=p[L++];

			if (q[i].opt==1) modify(q[i].y,q[i].x+q[i].y);

		}

		else

		{

			q[i]=p[R++];

			if (q[i].opt==2)

			{

				int tmp=query(q[i].y);

				if (tmp) ans[q[i].tim]=min(ans[q[i].tim],q[i].x+q[i].y-tmp);

			}

		}

	for (int i=l;i<=r;++i) p[i]=q[i],clear(p[i].y);

}

void Delete()

{

	int xx=0,yy=0;m=0;

	for (int i=1;i<=n;++i)

		if (p[i].opt==2)

			xx=max(xx,p[i].x),yy=max(yy,p[i].y);

	for (int i=1;i<=n;++i)

		if (p[i].x<=xx&&p[i].y<=yy)

			q[++m]=p[i];

	for (int i=1;i<=m;++i) p[i]=q[i];

}

int main()

{

	n=gi();m=gi();memset(ans,63,sizeof(ans));

	for (int i=1;i<=n;++i)

	{

		a[i]=(node){0,1,gi()+1,gi()+1};

		X=max(X,a[i].x);Y=max(Y,a[i].y);

	}

	for (int i=1;i<=m;++i)

	{

		a[++n]=(node){i,gi(),gi()+1,gi()+1};

		X=max(X,a[n].x);Y=max(Y,a[n].y);

	}

	++X;++Y;

	for (int i=1;i<=n;++i) p[i]=a[i];

	Delete();CDQ(1,m);

	for (int i=1;i<=n;++i) p[i]=a[i],p[i].x=X-p[i].x;

	Delete();CDQ(1,m);

	for (int i=1;i<=n;++i) p[i]=a[i],p[i].y=Y-p[i].y;

	Delete();CDQ(1,m);

	for (int i=1;i<=n;++i) p[i]=a[i],p[i].x=X-p[i].x,p[i].y=Y-p[i].y;

	Delete();CDQ(1,m);

	for (int i=1;i<=n;++i) if (a[i].opt==2) printf("%d\n",ans[a[i].tim]);

	return 0;

}

巴特西

[Luogu4169][Violet]天使玩偶/SJY摆棋子

题意

sol

code

最新文章

热门文章