OI - 时代的眼泪tears(NOIP模拟赛)

变成了时代的眼泪 QwQ

# 题面

点击展开/折叠题面

在二维平面上，进行共 $n$ 次操作或询问（$1\le n\le 2\times10^5$）：

1 x y 在 $(x,y)$ 处出现了一个点；
2 i s1 s2 求平面上有多少个点 $(p,q)$ 满足 $p>x_i,q>y_i$ 且 $s_1\le (p-x_i)(q-y_i)\le s_2$。

# 解析

令 $p-x_i=\Delta x$，$q-y_i=\Delta y$。

一开始有一个朴素的想法，枚举 $\Delta x$，则 $\Delta y\le \tfrac{S}{\Delta x}$，而 $\lfloor\tfrac S{\Delta x}\rfloor$ 只有 $\sqrt S$ 种取值（数论分块），每种取值对应的是一个矩形的区域，如下图。

于是可以用离散化+树状数组(vector)或者线段树套线段树，这样复杂度 $O(n\sqrt S\log^2 n)$。

然后我们看看数论分块的本质，即 $\Delta x\le \sqrt S$ 时有 $\sqrt S$ 种取值，$\Delta y\le\sqrt S$ 时有 $\sqrt S$ 种取值。于是可以分块——直接分别枚举 $\Delta x\le \sqrt S$ 和 $\Delta y\le \sqrt S$ 的情况，对每行每列维护一个树状数组（求 $(x,y_0\sim y_1)$ 的点，或 $(x_0\sim x_1,y)$ 的点）即可回答询问：

复杂度 $O(n\sqrt S\log n)$。

# 源代码

/*Lucky_Glass*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<algorithm>
using namespace std;

const int N=2e5+10;
#define lowbit(x) ((x)&(-(x)))
#define rank(x,uni) ((int)(lower_bound(uni.begin(),uni.end(),x)-uni.begin()+1))
#define complete(uni) {sort(uni.begin(),uni.end()),uni.erase(unique(uni.begin(),uni.end()),uni.end());}

struct DATA{
	vector<int> idx,tre;
	int siz;
	void Insert(int id){idx.push_back(id);}
	void Complete(){
		complete(idx);
		tre.resize((siz=(int)idx.size())+1);
	}
	inline int Query(int pos){
		int ret=0;
		while(pos) ret+=tre[pos],pos-=lowbit(pos);
		return ret;
	}
	inline void Modify(int pos){
		pos=rank(pos,idx);
		while(pos<=siz)
			tre[pos]++,pos+=lowbit(pos);
	}
	int Count(int L,int R){
		int rig,lef;
		if(idx.back()<L) return 0;
		if(idx.back()<R) rig=siz;
		else{
			rig=rank(R,idx);
			if(idx[rig-1]>R) rig--;
		}
		lef=rank(L,idx);
		return Query(rig)-Query(lef-1);
	}
}Da[N<<1];

vector<int> firx,firy;
int cmd[N][4],pnt[N][2];
int n,m,rol,col,nrol[N],ncol[N];

template<class T>inline T Read(T &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
int QueryS(int x,int y,int S){
	int sqS=(int)sqrt(S),it=rank(x,firx)+1,ret=0;
	for(int i=1;i<=sqS && it<=rol;i++)
		if(firx[it-1]==i+x){
			ret+=Da[it].Count(y+1,y+S/i);
			it++;
		}
	it=rank(y,firy)+1;
	for(int i=1;i<=sqS && it<=col;i++)
		if(firy[it-1]==i+y){
			ret+=Da[it+rol].Count(x+sqS+1,x+S/i);
			it++;
		}
	return ret;
}
int main(){
	freopen("tears.in","r",stdin);
	freopen("tears.out","w",stdout);
	Read(n);
	for(int i=1;i<=n;i++)
		if(Read(cmd[i][0])==1){
			Read(cmd[i][1]),Read(cmd[i][2]);
			pnt[++m][0]=cmd[i][1],pnt[m][1]=cmd[i][2];
			firx.push_back(cmd[i][1]);
			firy.push_back(cmd[i][2]);
		}
		else Read(cmd[i][1]),Read(cmd[i][2]),Read(cmd[i][3]);
	complete(firx);complete(firy);
	rol=(int)firx.size(),col=(int)firy.size();
	for(int i=1;i<=m;i++){
		int x=rank(pnt[i][0],firx),y=rank(pnt[i][1],firy);
		Da[x].Insert(pnt[i][1]);
		Da[y+rol].Insert(pnt[i][0]);
	}
	for(int i=1;i<=rol+col;i++) Da[i].Complete();
	for(int i=1;i<=n;i++)
		if(cmd[i][0]==1){
			int x=rank(cmd[i][1],firx),y=rank(cmd[i][2],firy);
			Da[x].Modify(cmd[i][2]);
			Da[y+rol].Modify(cmd[i][1]);
		}
		else
			printf("%d\n",QueryS(pnt[cmd[i][1]][0],pnt[cmd[i][1]][1],cmd[i][3])-QueryS(pnt[cmd[i][1]][0],pnt[cmd[i][1]][1],cmd[i][2]-1));
	return 0;
}

THE END

Thanks for reading!

$\begin{split} “\ &我一意孤行\ 为固守祂深爱的封地\\ &我执笔\ —为了祈求祂再次莅临\\ &万物已不屑传阅的篇章\\ &便由我诵读至声嘶音哑\\ &在最后一垠纯净里蜗居\\ &待黑白分明\ 待黑白分明\ ”\\ ——&\text{《象牙塔少女》By 雨狸/洛天依} \end{split}$

> Linked 象牙塔少女 αrtist5-网易云