【XSY3479】子区间（扫描线）

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

题解：

挺玄妙的一题。

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

#define db double
#define N 400010
#define ll long long

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