自动搬运

查看原文

来自洛谷，原作者为

	lzytag 我要前行 目光追逐黑夜 穿越寂寞的月

搬运于2025-08-24 23:06:37，当前版本为作者最后更新于2025-04-24 14:53:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来点高贵的 polylog 做法。

前言

本篇题解将提供一个该题的 $O(n \log^3n)$ 的 polylog 做法，不一定是最优复杂度，仅作抛砖引玉。

做法

首先证明此题中的单调性：设 $v_i$ 表示第一个序列中选 $(A1_i,B1_i)$ 对应的最优的第二个序列中的元素为 $(A2_{x_i},B2_{x_i})$，易证 $v_i$ 单调不升。同理 $(A2,B2)$ 对 $(A1,B1)$ 也有同样的单调性。

接下来考虑所有询问中 $l2 = r2$ 时怎么做。设 $l2 = X$，对第一个序列建一棵线段树，对线段树上匹配上的每个区间求出这个区间里的最大值。对于线段树上的每个节点，考虑维护 $(A2,B2)$ 中的每个元素对这个区间里的最优解，显然最优解相同的 $(A2_i,B2_i)$ 是一个区间，维护区间长度个断点，查询时在端点上二分即可。

对于一般情况，我们对 $(A2,B2)$ 再进行一个线段树分治，对于 $(A2,B2)$ 的线段树的一个节点 $[l,r]$，我们再用一颗线段树去维护 $(A2,B2)$ 中的区间对 $[l,r]$ 的最优解。考虑如何建这一棵树，我们用类似决策单调性分治的方式去做，建树到 $[L,R]$ 时维护对应的最优解可能存在的区间 $[ql,qr]$，将这个节点记为 $(L,R,ql,qr)$。接着分类讨论：

• 如果 $L = R$，直接遍历 $ql$ 到 $qr$，求出最优解。
• 如果 $L \neq R$，且 $ql\neq qr$，记 $mid = \lfloor \frac {L+R}{2}\rfloor$，遍历 $ql$ 到 $qr$ 求出 $mid$ 的最优匹配为记为 $qmid$，然后向左右儿子分治到 $(L,mid,qmid,qr)$，$(mid+1,R,ql,qmid)$
• 如果 $L\neq R$，且 $ql = qr$，在这棵节点上记录 $ql$ 代表整个区间的最优解，然后直接记录下此区间的最优解为 $ql$，同时求出 $[L,R]$ 对 $ql$ 的答案，当查询到此区间时，直接求出所查询的区间对 $ql$ 的答案。

易证这样建出的线段树一层最多只能有 $O(r-l)$ 个节点，线段树分治时所有的区间长度之和为 $O(n\log n)$，复杂度得以保证。

然后就做完了，复杂度理论上是 $O(n \log^3n)$，洛谷上取得了次优解，跑的还是挺快的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc c<<1
#define rc c<<1|1
#define mid (l+r>>1)
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int N = 1e5+5;
ll A1[N],B1[N],A2[N],B2[N];
int n,m;
vector< pii >tr1[N<<2];
vector< int >tr2[N<<2];
ll F(ll x,ll y){return (A1[x] + A2[y])*(B1[x] + B2[y]);}
ll ans[N],tr3[N<<2],ty[N<<2];
int l1[N],r1[N],l2[N],r2[N];
void build1(int c,int l,int r)
{
    //cerr<<c<<" "<<l<<" "<<r<<"\n";
    for(int i = l;i <= r;i++)
    {
        while(!tr1[c].empty())
        {
            pii p = tr1[c].back();//cerr<<F(4,1)<<" "<<F(4,2)<<" "<<p.fir<<" "<<p.sec<<"\n";
            if(F(-p.fir,i) > F(-p.fir,p.sec)) tr1[c].pop_back();
            else break;
        }
        if(tr1[c].empty()) tr1[c].pb(mkp(-n,i));
        else if(F(1,i) > F(1,tr1[c].back().sec))
        {
            pii p = tr1[c].back();
            int L = 1,R = -p.fir-1;
            //cerr<<"!"<<L<<" "<<R<<"\n";
            while(L < R)
            {
                int Mid = (L+R>>1);
                if(F(Mid+1,p.sec) < F(Mid+1,i)) L = Mid+1;//找到最后一个i > p的地方
                else R = Mid;
            }
            //cerr<<F(L,1)<<" "<<F(L,2)<<"\n";
            tr1[c].pb(mkp(-L,i));
        }
    }
    //for(auto p:tr1[c]) cerr<<p.fir<<" "<<p.sec<<"\n";
    //cerr<<c<<" "<<l<<" "<<r<<"\n";
    if(l == r) return ;
    build1(lc,l,mid),build1(rc,mid+1,r);
}
int Max(int x,int y,int z)
{
    if(x == 0 || y == 0) return x^y;
    return F(z,x) > F(z,y) ? x:y;
}
int Ask(int c,int l,int r,int ql,int qr,int x)
{
    //cerr<<c<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<x<<"\n";
    if(l >= ql && r <= qr)
    {
        auto pos = prev(upper_bound(tr1[c].begin(),tr1[c].end(),mkp(-x,m+1)));
        auto p = *pos;
        return p.sec;
    }
    int res = 0;
    if(ql <= mid) res = Max(res,Ask(lc,l,mid,ql,qr,x),x);
    if(qr > mid) res = Max(res,Ask(rc,mid+1,r,ql,qr,x),x);
    return res;
}
void Ins(int c,int l,int r,int ql,int qr,int id)
{
    if(l >= ql && r <= qr)
    {
        tr2[c].pb(id);
        return ;
    }
    if(ql <= mid) Ins(lc,l,mid,ql,qr,id);
    if(qr > mid) Ins(rc,mid+1,r,ql,qr,id);
}
void build3(int c,int l,int r,int ql,int qr)
{
    //cerr<<"build3 "<<c<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<"\n";
    ty[c] = 0;
    if(ql == qr)
    {
        ty[c] = ql;
        tr3[c] = F(ql,Ask(c,l,r,l,r,ql));//l,r这个区间全对应
        return ;
    }
    ll qmid = ql;
    for(int i = ql+1;i <= qr;i++) if(F(qmid,mid) < F(i,mid)) qmid = i;
    if(l == r)
    {
        tr3[c] = F(qmid,mid);
        //cerr<<"!!"<<tr3[c]<<" "<<qmid<<" "<<mid<<"\n";
        return ;
    }
    build3(lc,l,mid,qmid,qr),build3(rc,mid+1,r,ql,qmid);
    tr3[c] = max(tr3[lc],tr3[rc]);
}
ll Qry(int c,int l,int r,int ql,int qr)
{
    if(ql <= l && qr >= r) return tr3[c];
    if(ty[c])//如果全部相同，也就是ql~qr对应最大值都是ty[c]
    {
        //cerr<<"!!!"<<c<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<Ask(c,l,r,ql,qr,ty[c])<<"\n";
        return F(ty[c],Ask(c,l,r,ql,qr,ty[c]));
    }
    ll res = 0;
    if(ql <= mid) res = max(res,Qry(lc,l,mid,ql,qr));
    if(qr > mid) res = max(res,Qry(rc,mid+1,r,ql,qr));
    return res;
}
void build2(int c,int l,int r)
{
    //cerr<<c<<" "<<l<<" "<<r<<"\n";
    if(!tr2[c].empty())
    {
        build3(1,1,m,l,r);
        for(auto id:tr2[c])
        {
            ans[id] = max(ans[id],Qry(1,1,m,l2[id],r2[id]));//,cerr<<"!!!"<<id<<" "<<Qry(1,1,n,l2[id],r2[id])<<"\n";
            //cerr<<id<<" "<<Qry(1,1,m,l2[id],r2[id])<<"\n";
        }
    }
    //cerr<<c<<" "<<l<<" "<<r<<"\n";
    if(l == r) return ;
    build2(lc,l,mid),build2(rc,mid+1,r);
}
vector<long long> build_teams(vector<int> a1, vector<int> b1, vector<int> a2, vector<int> b2, vector<int> L1, vector<int> R1, vector<int> L2, vector<int> R2)
{
	//cerr<<"!!!\n";
	n = a1.size(),m = a2.size();
	for(int i = 1;i <= n;i++) A1[i] = a1[i-1],B1[i] = b1[i-1];
	for(int i = 1;i <= m;i++) A2[i] = a2[i-1],B2[i] = b2[i-1];
	//cerr<<"!!!\n";
    build1(1,1,m);
	int Q = L1.size();
    for(int i = 1;i <= Q;i++)
    {
		l1[i] = L1[i-1]+1;
		r1[i] = R1[i-1]+1;
		l2[i] = L2[i-1]+1;
		r2[i] = R2[i-1]+1;
        Ins(1,1,n,l1[i],r1[i],i);
        //cout<<Qry(l1,r1,l2,r2)<<"\n";
    }
	//cerr<<"!!!\n";
    build2(1,1,n);
	vector<ll>res;
    for(int i = 1;i <= Q;i++) res.pb(ans[i]);
	return res;
}
/*
過ぎ去った季節を待って
思い出せなくて嫌になって
離ればなれから飛び立って
鳥も鳴いてたろ 鳴いてたろ
いつだって僕らを待ってる
疲れた痛みや傷だって
変わらないままの夜だって
歌い続けるよ 続けるよ
*/