自动搬运

查看原文

来自洛谷，原作者为

	墨舞灵纯 Belief triggers the power to do.♡

搬运于2025-08-24 21:50:21，当前版本为作者最后更新于2020-04-15 21:47:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

第一感觉就是毒瘤计算几何，然后看了看题解，发现要转换坐标系，把给定的向量看成方向向量，作为基底解方程。

$$a_i(x_1,y_1)+b_i(x_2,y_2)=(x_i,y_i)$$ $$a_i=\frac{x_iy_2-x_2y_i}{x_1y_2-x_2y_1},b_i=\frac{x_1y_i-x_iy_1}{x_1y_2-x_2y_1} $$

然后发现分母没啥影响，所以我们可以转化为求一个二维的第$K$大。

带修主席树吼啊！ $\rightarrow$ 卡内存！

树套树吼啊！$\rightarrow$ 卡常数！（当然据说线段树套平衡树可以过，可惜我人丑常数大。。）

于是又看了看题解，发现可以整体二分。

$solve(L,R,l,r)$表示$l,r$范围内被照亮的时间为$L,R$，二分递归下去解决。关键问题是求一盏灯什么时候被点亮。这个的关键在于求它左下角有多少灯。这是一个经典的二维数点的问题，第一维排序第二维树状数组统计即可，左下角$\gt k_i$或者编号$\gt mid$ 就归到左区间去，反之去右区间。

哦对，还有一个问题就是光线可能是一条直线，所以我们要把向量稍微偏移一个角度。

复杂度$O(nlog^2n)$

upd：没过审……补充一点代码实现的细节吧。

首先是处理角度，这个判断一下是否为直线然后处理偏移就好。

然后就是转换坐标系并离散化坐标，也不必多说。

接下来就是整体二分。思路就是考虑编号$\le mid$的点和左下角$\le k_i$的点都归为左区间，然后把这个点加到树状数组里去，否则就把这个点的$k_i$减去它左下角有的点。

然后就是递归求解，但要注意判断边界。

#include<stdio.h>
#include<algorithm>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
struct ky{
	int x,y,id,k;
}a[N];
int ans[N],n,X1,Y1,X2,Y2,tr[N];
typedef long long ll;
ll x[N],y[N],tmp[N];
il bool cmp(const ky p,const ky q){return p.x^q.x?p.x<q.x:p.y<q.y;}
template <class I>
il void sp(I &p,I &q){I x=p;p=q,q=x;}
il void add(it x,ct num){while(x<N) tr[x]+=num,x+=(x&-x);}
il void que(it x,int &num){num=0;while(x) num+=tr[x],x-=(x&-x);}
il void solve(ct u,ct v,ct l,ct r){
	if(u==v){
		for(it i=l;i<=r;++i) ans[a[i].id]=u;
		return;
	}
	ct Mid=u+v>>1;it mid=l-1;
	std::sort(a+l,a+r+1,cmp);
	for(it i=l,now;i<=r;++i)
		que(a[i].y,now),(a[i].id<=Mid||now>=a[i].k)?add(a[i].y,1),++mid,sp(a[mid],a[i]),0:a[i].k-=now;//按照上文的思路写
	for(it i=l;i<=mid;++i) add(a[i].y,-1);
	if(l<=mid) solve(u,Mid,l,mid);
	if(mid<r) solve(Mid+1,v,mid+1,r);
}
template <class I>
il I Max(I p,I q){return p>q?p:q;}
template <class I>
il I A(I p){return p<0?-p:p;}
il void cgd(int &x,int &y){
	ct mx=Max(A(x),A(y)),d=((ll)2e9+mx-1)/mx;
	x*=d,y*=d,++x;
}
int main(){ 
	scanf("%d%d%d%d%d",&n,&X1,&Y1,&X2,&Y2);it i,xx,yy;
	if((0ll+X1)*Y2==(0ll+X2)*Y1) cgd(X1,Y1);//一条直线 改变角度 偏移一下
	if((0ll+X1)*Y2<(0ll+X2)*Y1) sp(X1,X2),sp(Y1,Y2);//调整方向
	for(i=1;i<=n;++i)
		scanf("%d%d",&xx,&yy),a[i].id=i,x[i]=(0ll+xx)*Y2-(0ll+X2)*yy,y[i]=(0ll+X1)*yy-(0ll+xx)*Y1;
	for(i=1;i<=n;++i) scanf("%d",&a[i].k);
	for(i=1;i<=n;++i) tmp[i]=x[i];
	std::sort(tmp+1,tmp+1+n),tmp[0]=std::unique(tmp+1,tmp+1+n)-tmp-1;
	for(i=1;i<=n;++i) a[i].x=std::lower_bound(tmp+1,tmp+1+tmp[0],x[i])-tmp;
	for(i=1;i<=n;++i) tmp[i]=y[i];
	std::sort(tmp+1,tmp+1+n),tmp[0]=std::unique(tmp+1,tmp+1+n)-tmp-1;
	for(i=1;i<=n;++i) a[i].y=std::lower_bound(tmp+1,tmp+1+tmp[0],y[i])-tmp; 
    //离散化坐标
	solve(1,n,1,n);//整体二分
	for(i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0; 
}