题解：P12459 [JOI2025 预选赛 R2] 亲密的厨师 / Intimate Chef

· · 题解

ST 表，简单思路代码做法。1.18K。

首先只求满意度，p 和 q 忽略即可。

枚举 a_i=\max(a_i,a_j)，贪心地从大到小取 b。

发现 k\le 4\times10^5，用 priority_queue 维护。具体地，对于每个 a_i，先放最大的 b，出堆后在放次大的 b，以此类推。

需要维护。显然先排序，试了一下发现按照 b 排序。

查找下一个 a_i>a_j，ST 表倍增即可。不会有人写朴素二分和查询吧

至于边再倍增一次即可。我用 map 偷懒，或者 vector 上 lower_bound()。如果不想 STL，建立链式前向星展开成树组序列后二分。

为了防止重 / 漏 a_i=a_j，考虑 ST 表记录权值 na_i+i 使得 a_i=a_j 只会算一次。（i 不一定是排序前的，任意 1 至 n 的排列均可）

:::success[code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=4e5+10;
struct D{
    ll a,b,i;
    bool operator<(const D &o)const
    {return b>o.b;}//<
}p[N]; ll s[19][N],w[N],n,m,z,u,v;
struct E{
    ll x,i,j;
    bool operator<(const E &o)const
    {return x<o.x;}
};priority_queue<E> q;
map<ll,map<ll,bool>> e;
void pt(ll x,ll y){
    for(ll j=18;j>=0;j--)
    if(y+(1<<j)-1<=n&&s[j][y]>=p[x].a*n+x)
    y+=1<<j; ll t=max(p[x].b,p[y].b);
    if(e[x][y]) pt(x,y+1);
    else if(y<=n) q.push({p[x].a+t,x,y});
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&z);
    for(ll i=1;i<=n;i++)
    scanf("%lld",&p[i].a),p[i].i=i;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&p[i].b);
    sort(p+1,p+n+1);
    for(ll i=1;i<=n;i++)
    s[0][i]=p[i].a*n+i,w[p[i].i]=i;
    while(m--){
        scanf("%lld%lld",&u,&v);
        e[w[u]][w[v]]=e[w[v]][w[u]]=1;
    }
    for(ll j=0;j<18;j++)
    for(ll i=1;i+(1<<j+1)-1<=n;i++)
    s[j+1][i]=min(s[j][i],s[j][i+(1<<j)]);
    for(ll i=1;i<=n;i++) pt(i,1);
    for(ll i=1;i<N&&!q.empty();i++){
        E t=q.top();//D`+1
        q.pop(),w[i]=t.x,pt(t.i,t.j+1);
    }
    while(z--){
        scanf("%lld",&u);
        printf("%lld\n",w[u]);
    }
    return 0;
}

::: :::info[排序 a 做法（口胡，有错请指出）] 剩下的 b 构成后缀。

考虑每一个后缀维护动态开点线段树，每次拿出来最大值后改成 -inf，对于没有修改的点，用 ST 表查询。