题解：P9525 [JOISC2022] 团队竞技 题解

· · 题解

前方高能预警：我的做法过于魔怔，因为我刚刚做过 2024NOIPT4。

首先我们从小到大枚举能力的其中一维（可以称作时间值），并将其逐一增加到一棵 FHQ-Treap 中，这当中只记录第二维和第三维（称作关键值和记录值），以关键值为关键字维护记录值的区间最大值。想象关键值为横坐标记录值为纵坐标构建一个平面直角坐标系。

我们在枚举的时候需要同时找到关键值最大的和记录值最大的点并且这两个点显然不一致。（时间值枚举时就找到了。）这两个点一致当且仅当其在平面直角坐标系的右上角。因此我们维护一个横坐标（称作 x_{super}）使得 x_{super} 以右的所有点纵坐标随横坐标增大而增大。假设 x_{super} 得以维护，那么接下来直接平衡树查询即可。

考虑加入平衡树时如何维护 x_{super}。当我们加入一个新的节点满足纵坐标其大于 x_{super} 对应的最大纵坐标或其横坐标大于 x_{super} 则更新 x_{super} 即可。

实现见代码。

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=300005;
namespace Treap{
    struct node{int l,r,v,k,s,mx,v2;}t[N];
    int tot,root;
    int newnode(int v,int v2){
        t[++tot].v=v,t[tot].k=rand(),t[tot].s=1,t[tot].v2=v2;
        t[tot].mx=v2;
        return tot;
    }
    void pushup(int x){
        t[x].s=t[t[x].l].s+t[t[x].r].s+1;
        t[x].mx=max(t[x].v2,max(t[t[x].l].mx,t[t[x].r].mx));
    }
    void split(int p,int v,int &x,int &y){
        if(!p){x=y=0;return;}
        if(t[p].v<=v)x=p,split(t[p].r,v,t[p].r,y);
        else y=p,split(t[p].l,v,x,t[p].l);
        pushup(p);
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(t[x].k<t[y].k)return t[x].r=merge(t[x].r,y),pushup(x),x;
        return t[y].l=merge(x,t[y].l),pushup(y),y;
    }
    void insert(int v,int v2){
        int x,y,z;
        split(root,v,x,z),y=newnode(v,v2);
        root=merge(merge(x,y),z);
    }
    void del(int v){
        int x,y,z;
        split(root,v,x,z),split(x,v-1,x,y),y=merge(t[y].l,t[y].r);
        root=merge(merge(x,y),z);
    }
    int get_k(int p,int k){
        if(k==0)return 0;
        if(k<=t[t[p].l].s)return get_k(t[p].l,k);
        if(k==t[t[p].l].s+1)return p;
        return get_k(t[p].r,k-t[t[p].l].s-1);
    }
    int get_pre(int v){
        int x,y,ans;
        split(root,v-1,x,y),ans=t[get_k(x,t[x].s)].v,root=merge(x,y);
        return ans;
    }
    int get_nxt(int v){
        int x,y,ans;
        split(root,v,x,y),ans=t[get_k(y,1)].v,root=merge(x,y);
        return ans;
    }
    int get_rank(int v){
        int x,y,ans;
        split(root,v-1,x,y),ans=t[x].s+1,root=merge(x,y);
        return ans; 
    }
    int get_mx(int vl,int v){
        int x,y,z,ans;
        split(root,vl-1,x,y),split(y,v,y,z);
        ans=t[y].mx,root=merge(x,merge(y,z));
        return ans;
    }
} 
int n,rt;
struct stu{
    int x,y,z;
    bool operator<(stu b)const{
        return x<b.x;
    }
}a[N]; 
void solve(){
    int mx=-1;
    //逐次将点按照X为关键字
    for(int i=1;i<=n;i++){
        vector<stu>v;
        v.push_back(a[i]);
        while(i<n&&a[i].x==a[i+1].x)v.push_back(a[++i]);
        //Part1：进行查询
        if(Treap::root&&rt){
            //查询非顺序部分中Y最大的和Z最大的 
                int Ymax=rt,Zmax=Treap::get_mx(1,rt-1);
                for(int j=0;j<v.size();j++){
                    //如有任何一项不满足要求
                    if(Ymax<=v[j].y||Zmax<=v[j].z||Zmax==-1){
                        //舍去
                    }
                    //否则
                    else{
                        //记录最值
                        mx=max(mx,v[j].x+Ymax+Zmax);
                        break;
                    }
                }
        }
        //Part2：加入平衡树
        for(int j=0;j<v.size();j++){
            Treap::insert(v[j].y,v[j].z);
            //如在xsuper以右且形成逆序
            if(v[j].y>rt&&Treap::get_mx(1,v[j].y-1)>v[j].z){
            //修改xsuper部分        
                rt=v[j].y;
            }
            int tmp2=Treap::get_nxt(v[j].y);
            if(tmp2){
                using namespace Treap;
                int l=get_rank(tmp2),r=t[root].s;
                while(l<=r){
                    int m=(l+r)/2;
                    int tmp=t[get_k(root,m)].v;
                    if(get_mx(tmp2,tmp)<v[j].z){
                        rt=max(rt,tmp);
                        l=m+1;
                    }else{
                        r=m-1;
                    }
                }
            }
        }
    }
    cout<<mx;
}
signed main(){
    Treap::t[0].mx=-1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+1+n);
    solve();
    return 0;
}