题解 P3578 【[POI2014]LAM-Solar lamps】

· · 题解

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

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; 
}