【NEERC2011】【GYM100085F】Flights
题意
给定 \(n\) 个抛物线，保证开口向下且与 \(x\) 轴的两个交点都在 \(x\) 轴正半轴或原点。
\(m\) 次询问，每次询问给定四个数 \(L,R,x,y\)，你需要回答在只考虑抛物线 \([L,R]\) 和横坐标区间 \([x,y]\) 的情况下，这些抛物线取值的最大值。
\(1 \le n \le 5 \times 10^4; 1 \le m \le 2 \times 10^4; 1 \le x,y \le 5 \times 10^4\)，抛物线顶点纵坐标 \(\le 50\)。
题解
这个做法可能是全网首发。
本文中默认 \(n,m\) 和横坐标范围同阶。
考虑单个抛物线区间最值问题，最大值要么在区间端点取到，要么在顶点处取到。
也就是说，每个询问被转化为了三个子问题：坐标区间中顶点最大纵坐标，横坐标为 \(x\) 时最大的函数值，横坐标为 \(y\) 时最大的函数值。
对于第一个子问题，可以用莫队+线段树解决，具体的，用莫队维护抛物线的区间，用线段树维护横坐标区间，对于每个横坐标，开一个 multiset 记录在只考虑目前抛物线区间的情况下，这个横坐标上的顶点的纵坐标的集合，当 multiset 中的最大值发生改变时更新线段树即可，这一部分的复杂度是 \(O(n \sqrt{n} \log n)\)。
对于第二个子问题，考虑分块，如果我们能求出每一个块中的抛物线在每一个横坐标上的最大取值，问题就解决了。考虑计算一条抛物线在哪些横坐标上能成为块中的最优情况。
将每一个块中的线段依次插入，我们尝试求某条线段可能成为块中的最优情况的横坐标区间，然后用 lazy-segtree 维护。
遍历块内的之前已经插入的线段，记目前尝试插入的线段为抛物线 \(a\)，现在遍历到的是抛物线 \(b\)，求出交点，进行分类讨论：
- 有两个交点：记两个交点为 \(x_1,x_2(x_1<x_2)\)，如果 \(a\) 更陡峭（二次项系数较小），则只有在区间 \((x_1,x_2)\) 中可能成为最优，如果 \(a\) 更平缓（二次项系数较大），则在区间\((-\inf,x_1)\) 和 \((x_2,+\inf)\) 中可能成为最优。
- 有一个交点：记交点为 \(x_1\)，如果 \(a\) 在 \(b\) 的左边，则只有在区间 \((-\inf,x_1)\) 中可能成为最优，如果 \(a\) 在 \(b\) 的右边，则在区间\((x_2,+\inf)\) 中可能成为最优。
- 没有交点：直接比较两个抛物线的常数项，如果 \(a\) 的常数项较大，则 \(b\) 全部在 \(a\) 的下面，可以跳过，否则 \(a\) 全部在 \(b\) 的下面，\(a\) 不可能成为最优。
现在我们得到了一些部分，这些部分的交就是 \(a\) 可能在块中成为最大值的部分，如果某一部分只有一个区间，直接求区间的交即可，如果某一部分有两个区间，可以看做是挖去中间一部分，由于前面有 \(O(\sqrt{n})\) 个抛物线，即最多挖去 \(O(\sqrt{n})\) 个区间，一共要更新 \(O(\sqrt{n})\) 个横坐标区间上的最优抛物线，用线段树维护，对于单个抛物线会有 \(O(\sqrt{n} \log n)\) 的开销，所有抛物线产生的时间开销为 \(O(n \sqrt{n} \log n)\)，对于每一块，还要遍历线段树并下传懒标记，产生的时间开销为 \(O(n \sqrt{n})\)。
预处理的总复杂度是 \(O(n \sqrt{n} \log n)\)。
考虑询问：对于每个块和每一个散块中的元素暴力取 max 就行，回答询问的复杂度是 \(O(n \sqrt{n})\)。
至此，问题已经解决，总复杂度是 \(O(n \sqrt{n} \log n)\)，此题卡精度，而且要注意边界。
Sample Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,q,B;
long double La[50005],Lb[50005],Lc[50005];
int sp[50005],tx[50005],ty[50005],bl[50005];
int ans1[50005];
long double ans2[50005],ans3[50005];
struct Query
{
int L1,R1,L2,R2,id;
}qs[50005];
const int M=50000;
struct Segtree//用于莫队的线段树
{
multiset <int> S[50005];
int t[200015];
void update(int id,int l,int r,int x,int d)
{
if(l==r)
{
t[id]=d;
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(id<<1,l,mid,x,d);
else update(id<<1|1,mid+1,r,x,d);
t[id]=max(t[id<<1],t[id<<1|1]);
}
int query(int id,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return t[id];
int mid=(l+r)>>1,res=0;
if(x<=mid) res=max(res,query(id<<1,l,mid,x,y));
if(y>mid) res=max(res,query(id<<1|1,mid+1,r,x,y));
return res;
}
void ins(int x,int d)
{
S[x].insert(d);
assert(S[x].size());
auto it=prev(S[x].end());
update(1,0,M,x,*it);
}
void del(int x,int d)
{
int t1=S[x].count(d);
auto it=S[x].lower_bound(d);
assert(it!=S[x].end());
S[x].erase(it);
int t2=S[x].count(d);
if(!S[x].size()) update(1,0,M,x,0);
else
{
auto it=prev(S[x].end());
update(1,0,M,x,*it);
}
}
}st;
int maxx[305][50005];
struct LazySeg//用于分块预处理的线段树
{
int t[200015],lz[200015];
void init()
{
memset(t,0,sizeof(t));
memset(lz,0,sizeof(lz));
}
void pushdown(int id)
{
if(lz[id])
{
lz[id<<1]=lz[id<<1|1]=lz[id];
t[id<<1]=t[id<<1|1]=lz[id];
lz[id]=0;
}
}
void update(int id,int l,int r,int x,int y,int d)
{
if(x<=l&&r<=y)
{
t[id]=lz[id]=d;
return;
}
pushdown(id);
int mid=(l+r)>>1;
if(x<=mid) update(id<<1,l,mid,x,y,d);
if(y>mid) update(id<<1|1,mid+1,r,x,y,d);
}
void query(int id,int l,int r,int bid)
{
if(l==r)
{
maxx[bid][l]=t[id];
return;
}
int mid=(l+r)>>1;
pushdown(id);
query(id<<1,l,mid,bid),query(id<<1|1,mid+1,r,bid);
}
}st2;
bool cmp(Query A,Query B)
{
if(bl[A.L1]==bl[B.L1])
{
if(bl[A.L1]%2) return A.R1>B.R1;
else return A.R1<B.R1;
}
return A.L1<B.L1;
}
void get_abc(long double x1,long double x2,long double y2,long double &a,long double &b,long double &c)//求抛物线解析式
{
long double x3=x2+x2-x1;
long double p=x2*x3+x1*(x2-x3)-x2*x2;
assert(p!=0);
a=-y2/p,b=(x3*y2+x1*y2)/p,c=-(x1*x3*y2)/p;
}
const long double eps=1e-10;
pair <long double,long double> jiao(int x,int y)//求抛物线交点（无交点用-114514补位）
{
long double A=La[x]-La[y],B=Lb[x]-Lb[y],C=Lc[x]-Lc[y];
if(fabs(A)<eps)
{
if(fabs(B)<eps) return mp(-114514,-114514);
return mp(-C/B,-114514);
}
long double del=B*B-4*A*C;
if(fabs(del)<0) return mp(-B/(2*A),-114514);
if(del<0) return mp(-114514,-114514);
assert(del>=0);
del=sqrt(del);
return mp((-B-del)/(2*A),(-B+del)/(2*A));
}
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&sp[i],&tx[i],&ty[i]),get_abc((long double)(sp[i]),(long double)(tx[i]),(long double)(ty[i]),La[i],Lb[i],Lc[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++) scanf("%d%d%d%d",&qs[i].L1,&qs[i].R1,&qs[i].L2,&qs[i].R2),qs[i].id=i;
B=sqrt(n);
for(int i=1;i<=n;i++) bl[i]=1+(i-1)/B;
sort(qs+1,qs+1+q,cmp);
int nowl=1,nowr=0;
for(int i=1;i<=q;i++)//莫队
{
while(nowr<qs[i].R1) st.ins(tx[nowr+1],ty[nowr+1]),nowr++;
while(nowl>qs[i].L1) st.ins(tx[nowl-1],ty[nowl-1]),nowl--;
while(nowr>qs[i].R1) st.del(tx[nowr],ty[nowr]),nowr--;
while(nowl<qs[i].L1) st.del(tx[nowl],ty[nowl]),nowl++;
ans1[qs[i].id]=st.query(1,0,M,qs[i].L2,qs[i].R2);
}
for(int i=1,bid=1;i<=n;i+=B,bid++)//分块
{
st2.init();
int to=min(n,i+B-1);
for(int j=i;j<=to;j++)
{
int L=0,R=M;
vector <pii > vec,vec2;
vec.clear(),vec2.clear();
for(int l=i;l<j;l++)
{
pair <long double,long double> tmp=jiao(j,l);
if(tmp.fi==-114514) //无交点
{
if(Lc[j]>Lc[l]) continue;
L=M+1;
break;
}
if(tmp.se==-114514)//一个交点
{
if(tx[j]>tx[l]) L=max(L,(int)ceil(tmp.fi));
else R=min(R,(int)floor(tmp.fi));
continue;
}
if(tmp.fi>tmp.se) swap(tmp.fi,tmp.se);//两个交点
tmp.fi=max(tmp.fi,(long double)0.0),tmp.se=min(tmp.se,(long double)(M));
int nL=ceil(tmp.fi),nR=floor(tmp.se);
if(La[j]>La[l])
{
if(nL<=nR) vec.pb(mp(nL,nR));
}
else L=max(L,(int)ceil(tmp.fi)),R=min(R,(int)floor(tmp.se));
}
if(L>R) continue;
sort(vec.begin(),vec.end());
int idx=0;
while(idx<vec.size())//合并挖去的区间
{
int nowL=vec[idx].fi,nowR=vec[idx].se;
while(idx+1<vec.size()&&vec[idx+1].fi<=nowR+1) idx++,nowR=max(nowR,vec[idx].se);
vec2.pb(mp(nowL,nowR)),idx++;
}
vec2.pb(mp(M+1,M+1));
int nL=L;
for(int l=0;l<vec2.size();l++)//更新可能称为最大值的部分
{
int nR=vec2[l].fi-1;
nL=max(nL,L),nR=min(nR,R);
if(nL<=nR) st2.update(1,0,M,nL,nR,j);
nL=vec2[l].se+1;
}
}
st2.query(1,0,M,bid);
}
for(int i=1;i<=q;i++)//回答询问
{
int l=qs[i].L1,r=qs[i].R1;
long double x1=(long double)(qs[i].L2),x2=(long double)(qs[i].R2);
while(l<=r&&(l-1)%B) ans2[qs[i].id]=max(ans2[qs[i].id],max(La[l]*x1*x1+Lb[l]*x1+Lc[l],La[l]*x2*x2+Lb[l]*x2+Lc[l])),l++;
while(l<=r&&l+B-1<=r)
{
int opt=maxx[1+(l-1)/B][qs[i].L2];
ans2[qs[i].id]=max(ans2[qs[i].id],La[opt]*x1*x1+Lb[opt]*x1+Lc[opt]);
opt=maxx[1+(l-1)/B][qs[i].R2];
ans2[qs[i].id]=max(ans2[qs[i].id],La[opt]*x2*x2+Lb[opt]*x2+Lc[opt]);
l+=B;
}
while(l<=r) ans2[qs[i].id]=max(ans2[qs[i].id],max(La[l]*x1*x1+Lb[l]*x1+Lc[l],La[l]*x2*x2+Lb[l]*x2+Lc[l])),l++;
}
for(int i=1;i<=q;i++) cout<<fixed<<setprecision(6)<<max((long double)ans1[i],ans2[i])<<endl;
}
signed main()
{
freopen("flights.in","r",stdin);
freopen("flights.out","w",stdout);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}