BZOJ3833 : [Poi2014]Solar lamps
2023-09-11 14:15:04 时间
首先旋转坐标系，将范围表示成矩形或者射线
如果范围是一条线，则将灯按y坐标排序，y坐标相同的按x坐标排序，
对于y相同的灯，f[i]=min(i,它前面灯发光时刻的第k[i]小值)，
线段树维护，$O(n\log n)$
如果范围是一个矩形，则将灯按x坐标排序，x坐标相同的按y坐标排序，
从左往右、从下到上依次扫描，f[i]=min(i,它左下角灯发光时刻的第k[i]小值)，
权值线段树套SBT维护，$O(n\log^2n)$
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010,M=524289;
int n,x1,y1,x2,y2,sig=1,i,j,x,y,f[N],q[N],cnt,flag;
struct P{ll x,y;int id,k;}a[N];
inline void up(int&x,int y){if(x>y)x=y;}
inline void read(int&a){
char c;bool f=0;a=0;
while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));
if(c!='-')a=c-'0';else f=1;
while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
if(f)a=-a;
}
namespace Mistake{
int v[M];
inline bool cmp(P a,P b){return a.y==b.y?a.x<b.x:a.y<b.y;}
void clear(int x,int a,int b){
if(!v[x])return;
v[x]=0;
if(a==b)return;
int mid=(a+b)>>1;
clear(x<<1,a,mid),clear(x<<1|1,mid+1,b);
}
void add(int x,int a,int b,int c){
v[x]++;
if(a==b)return;
int mid=(a+b)>>1;
if(c<=mid)add(x<<1,a,mid,c);else add(x<<1|1,mid+1,b,c);
}
inline int kth(int k){
if(v[1]<k)return n;
int x=1,a=1,b=n,mid,t;
while(a<b){
mid=(a+b)>>1,t=v[x<<=1];
if(k<=t)b=mid;else k-=t,a=mid+1,x++;
}
return a;
}
void work(){
sort(a+1,a+n+1,cmp),a[0].y=a[1].y-1;
for(i=1;i<=n;i++){
if(a[i].y!=a[i-1].y)clear(1,1,n);
up(f[a[i].id],kth(a[i].k)),add(1,1,n,f[a[i].id]);
}
}
}
namespace Normal{
ll b[N];int X,Y,K,lim,t;
inline bool cmp(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline int lower(ll x){
int l=1,r=n,t,mid;
while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
struct node{
int val,sum;node*l,*r;
node(){val=sum=0;l=r=NULL;}
inline void up(){sum=l->sum+r->sum+1;}
}*blank=new(node),*T[M],pool[4000000],*cur;
inline void Rotatel(node*&x){node*y=x->r;x->r=y->l;x->up();y->l=x;y->up();x=y;}
inline void Rotater(node*&x){node*y=x->l;x->l=y->r;x->up();y->r=x;y->up();x=y;}
void Maintain(node*&x,bool f){
if(x==blank)return;
if(!f){
if(x->l->l->sum>x->r->sum)Rotater(x);
else if(x->l->r->sum>x->r->sum)Rotatel(x->l),Rotater(x);
else return;
}else{
if(x->r->r->sum>x->l->sum)Rotatel(x);
else if(x->r->l->sum>x->l->sum)Rotater(x->r),Rotatel(x);
else return;
}
Maintain(x->l,0),Maintain(x->r,1),Maintain(x,0),Maintain(x,1);
}
void Ins(node*&x){
if(x==blank){x=cur++;x->val=Y;x->l=x->r=blank;x->sum=1;return;}
x->sum++;
if(Y<x->val)Ins(x->l);else Ins(x->r);
Maintain(x,Y>=x->val);
}
inline void Ask(node*x){
t=0;
while(x!=blank)if(X<x->val)x=x->l;else{t+=x->l->sum+1;if(t>=K)return;x=x->r;}
}
inline void add(){
int a=1,b=n,mid,f=1,x=1;
while(a<b){
if(f)Ins(T[x]);
mid=(a+b)>>1;x<<=1;
if(f=X<=mid)b=mid;else a=mid+1,x|=1;
}
Ins(T[x]);
}
inline int kth(){
if(Ask(T[1]),t<K)return n;
int x=1,a=1,b=n,mid;
while(a<b){
mid=(a+b)>>1;x<<=1;
if(lim<=mid)t=n;else Ask(T[x]);
if(K<=t)b=mid;else{K-=t,a=mid+1,x|=1;if(a>=Y)return n;}
}
return a;
}
void work(){
cur=pool;
blank->l=blank->r=blank;
for(i=1;i<M;i++)T[i]=blank;
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)b[i]=a[i].y;
sort(b+1,b+n+1);
for(i=1;i<=n;i++){
X=lower(a[i].y),Y=a[i].id,K=a[i].k;
if(lim<=1&&(Ask(T[1]),t)>=a[i].k)f[a[i].id]=1;else up(f[a[i].id],kth());
Y=X,X=f[a[i].id],add();
if(X>lim)lim=X;
}
}
}
int main(){
read(n),read(x1),read(y1),read(x2),read(y2);
if((ll)x1*y2==(ll)x2*y1)x2=-y1,y2=x1,flag=1;
if((ll)x1*y2<(ll)x2*y1)sig=-1;
for(i=1;i<=n;i++){
read(x),read(y);
a[i].x=((ll)y2*x-(ll)x2*y)*sig;
a[i].y=((ll)x1*y-(ll)y1*x)*sig;
a[i].id=f[i]=i;
}
for(i=1;i<=n;i++)read(a[i].k);
if(flag)Mistake::work();else Normal::work();
for(i=1;i<n;i++)printf("%d ",f[i]);printf("%d",f[n]);
return 0;
}