自动搬运

查看原文

来自洛谷，原作者为

	lzqy_ 生而绚烂，璀璨如花。

搬运于2025-08-24 22:19:41，当前版本为作者最后更新于2021-07-31 15:30:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种 $O(n^2)$ 的纯分块做法。暴力碾标算

思路

要维护一些奇怪的东西，首先想到分块。

先看操作一。插入操作对于分块来说是比较复杂的，考虑到最多插入 $n$ 个二元组，所以提前处理出长度为 $n$ 的分块，每个二元组都是 $(0,0)$，这样，就把插入变成了单点修改。

再看操作二。如果要求的东西和数值的大小关系有关时，一种很套路的做法就是将每个块进行排序，即按 $B$ 作为第一关键字、$A$ 作为第二关键字排序。

然后就可以具体对每个操作来处理了。

操作一：

设修改的是第 $x$ 个二元组，那么暴力扫描 $x$ 所在的块，找到 $x$ 进行修改，然后再对整个块重新排序。时间复杂度 $O(\sqrt n\,log\sqrt n)$。

操作二：

设询问的是第 $x$ 个二元组 $(A,B)$，那么对于每一个块，先二分出第一个 $B'$ 大于等于 $B$ 的元素的位置（首先满足第一关键字），然后在块的剩下部分暴力搜索找到第一个 $A'$ 大于等于 $A$ 的元素，那么这个元素便是当前块的答案。对每个块执行这个操作，总的极限时间复杂度 $O(n)$。

这样我们就拥有了一个常数极小的 $O(n^2)$ 算法。但是我们需要剪枝。

• 对于每一个块，如果其最左边元素的 $B$ 值（即最大的 $B$）小于要比较的 $B$ 值，那么直接跳过整个块。

• 可以发现，这个算法的瓶颈在于二分完遍历块的时间。所以可以适当缩短块长，牺牲二分的时间来减短遍历块的时间（使二分可以过滤掉更多没必要遍历的部分）。块长取 $222$ 时速度最快（比正常块长短一半）。

• 在遍历块找答案时，目前 $B$ 值必须小于已找出答案的 $B$ 值，否则这个块的剩余部分不会存在最终答案。

• 以及一些普遍的卡常小技巧。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
inline int read()
{
	register int x=0;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct node
{
	int A,B,id;
}a[maxn];
bool operator <(node a,node b)
{
	if(a.B==b.B) return a.A<b.A;
	return a.B<b.B;
}
int Y[maxn],L[maxn],R[maxn];
int n,m,qn;
void change(int x,int A,int B)
{
	register int k=Y[x];
	for(register int i=L[k];i<=R[k];i++)
		if(a[i].id==x)
		{
			a[i].A=A,a[i].B=B;
			break;//找到就跳出
		}
	sort(a+L[k],a+1+R[k]);//对块内元素进行排序
}
pair<int,int> getsum(int x)
{
	register int k=Y[x];
	for(register int i=L[k];i<=R[k];i++)
		if(a[i].id==x)
			return make_pair(a[i].A,a[i].B);
}
int getnum(int A,int B,int x)
{
	pair<int,int>Min;
	Min.first=INT_MAX,Min.second=INT_MAX;
	register int l,r,h=-1,mid,ll,rr,lll,rrr;
	for(register int i=1;i<=Y[n];i++)
	{
		if(a[R[i]].B<B) continue;//当前块没有答案,跳过
		l=L[i],r=R[i];
		while(r>l)
		{
			mid=l+r>>1;
			if(a[mid].B<B) l=mid+1;
			else r=mid;
		}
		for(register int j=l;j<=R[i]&&a[j].B<=Min.first;j++)
			if(a[j].A>=A&&a[j].id!=x)
				if(make_pair(a[j].B,a[j].A)<Min)
				{
					Min=make_pair(a[j].B,a[j].A),h=a[j].id;
					break;//取到当前块的答案就跳出
				}
					
	}
	return h;
}
int main()
{
	n=m=read(),qn=222;//手动定义块长
	for(register int i=1;i<=n;i++)
		Y[i]=(i-1)/qn+1,a[i].id=i;
	for(register int i=1;i<=Y[n];i++)
		L[i]=(i-1)*qn+1,R[i]=min(i*qn,n);
	register int x,y,ii=0;
	pair<int,int>t;
	register char c; 
	while(m--)
	{
		getchar(),c=getchar();//用getchar节省时间
		if(c=='D')
			x=read(),y=read(),change(++ii,x,y);
			//ii为下一个插入的元素的编号
		else
		{
			x=read(),t=getsum(x),y=getnum(t.first,t.second,x);
			if(y==-1) puts("NE");
			else printf("%d\n",y);
		}
			
	}
	return 0;
}

算是一种思维简单的方法吧，祝AC！