【XSY3479】子区间（扫描线）

区间（扫描线）"/>

【XSY3479】子区间（扫描线）

题意：转化后变为：平面上给定 n n n 个关键点， q q q 次询问一个点与其左上的每个关键点形成的矩形面积的最大值。

题解：

挺玄妙的一题。

这里假设这 n n n 个关键点都是 x x x 单调不降且 y y y 单调不降的（因为若点 A A A 在点 B B B 左上方则点 B B B 肯定无用），注意这是个壳，但不一定是凸的。

由于不一定是凸的，你发现它们与询问点之间的矩形面积不是单峰的，所以不能直接二分。

先考虑只有两个关键点的情况，考虑两个关键点各自的控制范围，解出来边界是一条经过两点连线中点，且与两点连线对称的直线，称其为这两个关键点的划分直线。两个关键点分居平面上被这条直线所划分出来的两个区域，询问点与和它在同一个区域的关键点所形成的矩形面积更大（虽然有点反直觉），即一个关键点控制了它所在区域的所有询问点。

现在有多个关键点时，将所有关键点按 x x x 坐标排序，考虑每相邻两个关键点所形成的划分直线，如果这些直线不交，此时关键点们与询问点之间的矩形面积就是单峰的，可以直接二分。

发现若两条相邻直线相交（注意最先相交的一定是某两条相邻的直线），假设它们分别是 A , B A,B A,B 和 B , C B,C B,C 的划分直线，那么对于横坐标比交点大的询问点，点 B B B 对于它都是没有贡献的，即点 B B B 的控制范围不会在交点之后，可以参照下图理解：

也就是说在交点坐标之后，我们就可以把点 B B B 删掉了。

那么考虑扫描线，把所有点按 x x x 坐标从小到大排序，动态维护当前扫描线 x = X x=X x=X 上的控制区域划分，遇到划分直线的交点时就更新控制区域。

如图，每个点的控制区域已经被我们用颜色标明（无敌的 mathematica！），假设当前扫描线在 x = X x=X x=X，那么我们就要维护图中的三条蓝色直线，然后遇到询问时直接二分询问点被夹在哪两条直线之间、遇到交点时我们更新这些蓝色直线即可。

时间复杂度 O ( ( n + q ) log ⁡ n ) O((n+q)\log n) O((n+q)logn)。

原题需要对时间分治，时间复杂度为 O ( q log ⁡ 2 q ) O(q\log ^2q) O(qlog2q)。

#include<bits/stdc++.h>#define db double
#define N 400010
#define ll long longusing namespace std;inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^'0');ch=getchar();}return x*f;
}struct Point
{db x,y;Point(){};Point(db _x,db _y){x=_x,y=_y;}
}S[N],Q[N];Point operator - (Point a,Point b){return Point(a.x-b.x,a.y-b.y);}struct Line
{db k,b;Line(){};Line(db _k,db _b){k=_k,b=_b;}Line(Point p1,Point p2){k=(p1.y-p2.y)/(p1.x-p2.x);b=p1.y-k*p1.x;}db gety(db x){return k*x+b;}
};Point intersection(Line l1,Line l2)
{db x=(l1.b-l2.b)/(l2.k-l1.k);db y=l1.k*x+l1.b;return Point(x,y);
}int m,np,nq;
ll ans[N];namespace Solve
{db X;struct data{Point p;int id;data(){};data(Point a,int b){p=a,id=b;}}p[N<<1];int cnt;void getp(vector<int> &pid){sort(pid.begin(),pid.end(),[&](int a,int b){if(S[a].x==S[b].x) return S[a].y>S[b].y;return S[a].x<S[b].x; });int top=-1;for(auto i:pid){if(top!=-1&&S[i].y<=S[top].y) continue;p[++cnt]=data(S[i],-i),top=i;}}int pre[N<<1],nxt[N<<1],tail;Line getLine(int a,int b){return Line(Point(p[a].p.x,p[b].p.y),Point(p[b].p.x,p[a].p.y));}struct Div{Line l;int id;Div(){};Div(Line _l,int _id){l=_l,id=_id;}};struct cmp{bool operator () (Div a,Div b) const{return a.l.gety(X)<b.l.gety(X);}};set<Div,cmp>s;struct Inter{db x;int mid;Inter(){};Inter(db a,int b){x=a,mid=b;}};bool operator < (Inter a,Inter b){if(a.x==b.x) return a.mid<b.mid;return a.x<b.x;}set<Inter>heap;void update(int a,int b,int c,int opt){if(Line(p[b].p,p[c].p).k<=Line(p[a].p,p[b].p).k) return;Line l1=getLine(a,b),l2=getLine(b,c);db inter=intersection(l1,l2).x;if(opt==1) heap.insert(Inter(inter,b));else heap.erase(Inter(inter,b));}void check(db nx){while(!heap.empty()&&(*heap.begin()).x<=nx){Inter now=(*heap.begin());int b=now.mid,a=pre[b],c=nxt[b];if(pre[a]) update(pre[a],a,b,-1);update(a,b,c,-1);if(nxt[c]) update(b,c,nxt[c],-1);pre[c]=a,nxt[a]=c;if(pre[a]) update(pre[a],a,c,1);if(nxt[c]) update(a,c,nxt[c],1);s.erase(Div(getLine(a,b),a)),s.erase(Div(getLine(b,c),b));s.insert(Div(getLine(a,c),a));}}void push(int id){if(tail){pre[id]=tail,nxt[tail]=id;if(pre[tail]) update(pre[tail],tail,id,1);s.insert(Div(getLine(tail,id),tail));}tail=id;}int qid;ll getS(int id,int x,int y){if(!id) return -1;int xx=(int)p[id].p.x,yy=(int)p[id].p.y;if(yy-y<0) return -1;return 1ll*(x-xx)*(yy-y);}ll query(db Y){int x=(int)X,y=(int)Y;auto it=s.lower_bound(Div(Line(0,Y),114514));if(it==s.end()) return getS(tail,x,y);return getS((*it).id,x,y);}void work(int ql,int qr,vector<int> &pid){cnt=0;for(int i=ql;i<=qr;i++) p[++cnt]=data(Q[i],i);getp(pid);sort(p+1,p+cnt+1,[](data a,data b){if(a.p.x==b.p.x) return a.id<0;return a.p.x<b.p.x;});tail=0;for(int i=1;i<=cnt;i++) pre[i]=nxt[i]=0;s.clear(),heap.clear();X=0;for(int i=1;i<=cnt;i++){check(p[i].p.x);X=p[i].p.x;if(p[i].id<0) push(i);else qid=p[i].id,ans[p[i].id]=max(ans[p[i].id],query(p[i].p.y));}}
}namespace Seg
{vector<int>pid[N<<2];void update(int k,int l,int r,int ql,int qr,int x){if(ql<=l&&r<=qr){pid[k].push_back(x);return;}int mid=(l+r)>>1;if(ql<=mid) update(k<<1,l,mid,ql,qr,x);if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,x);}void solve(int k,int l,int r){Solve::work(l,r,pid[k]);if(l==r){printf("%lld\n",ans[l]);return;}int mid=(l+r)>>1;solve(k<<1,l,mid);solve(k<<1|1,mid+1,r);}
}int main()
{static int st[N],ed[N];
//	freopen("range3.in","r",stdin);
//	freopen("range3_my.out","w",stdout);memset(ed,-1,sizeof(ed));m=read();for(int i=1;i<=m;i++){int opt=read();if(opt==1){int l=read(),r=read();S[++np]=Point(l,r),st[np]=nq+1;}if(opt==2) ed[read()]=nq;if(opt==3){int l=read(),r=read();Q[++nq]=Point(l,r);}}for(int i=1;i<=np;i++){if(ed[i]==-1) ed[i]=nq;if(st[i]<=ed[i]) Seg::update(1,1,nq,st[i],ed[i],i);}memset(ans,-1,sizeof(ans));Seg::solve(1,1,nq);return 0;
}