题解：P11348 [KTSC 2023 R2] 团队建设

· · 题解

来点高贵的 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)。接着分类讨论：

易证这样建出的线段树一层最多只能有 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;
}
/*
過ぎ去った季節を待って
思い出せなくて嫌になって
離ればなれから飛び立って
鳥も鳴いてたろ 鳴いてたろ
いつだって僕らを待ってる
疲れた痛みや傷だって
変わらないままの夜だって
歌い続けるよ 続けるよ
*/