题解：「TFXOI R1」创世纪

gesic · 2025-02-18 20:51:45 · 个人记录

验题人题解。

恶心程度堪比 P8868 [NOIP2022] 比赛。

绘图工具：krita-5.2.2。

题意

维护单峰子区间个数，支持区间加、乘、覆盖，序列元素为浮点数。

sol

类型定义

为了后面比较时方便，先定义浮点类型并重载必要的运算符（~~闲着没事找事~~）。

经实测，使用 double 能通过，record。

struct LD{
    double val;
    inline LD(){}
    inline LD(const double &x){val=x;}
    inline LD(const LD &x){val=x;}
    inline operator double&(){return val;}
    inline operator const double&()const{return val;}
    inline LD& operator=(const LD &x){val=x.val;return *this;}
    inline LD& operator*=(const LD &x){val*=x.val;return *this;}
    inline LD& operator+=(const LD &x){val+=x.val;return *this;}
};
const LD zero=0,mxinf=1e9,mninf=-1e9;
const double eps=1e-5;
inline LD operator+(const LD &a,const LD &b){return a.val+b.val;}
inline LD operator*(const LD &a,const LD &b){return a.val*b.val;}
inline bool operator==(const LD &p,const LD &q){return fabs(p.val-q.val)<=eps;}
inline bool operator<(const LD &p,const LD &q){return p.val+eps<q.val;}
inline bool operator>(const LD &p,const LD &q){return p.val-eps>q.val;}

比赛名称明示，使用线段树，考虑节点和标记信息。直接放代码，变量意义详见注释。

// 节点
struct node{
    int len;    // 长度
    LD val_l,val_r,mx,mn;   // 左/右 端点值，最大/最小 值
    int l_up,l_down,r_up,r_down;    // 左/右 最长单调 上升/下降 序列长度
    itn l_ud,l_du,r_ud,r_du;    // 见下文图示
    ll res_u,res_d; // 「峰/谷」数量
    // 构造函数
    inline node(){}
    inline node(
        const int &l,
        const LD &vl,const LD &vr,const LD &x,const LD &n,
        const int &lu,const int &ld,const int &ru,const int &rd,
        const int &lud,const int &ldu,const int &rud,const int &rdu,
        const ll &su,const ll &sd
    ){
        len=l;
        val_l=vl,val_r=vr,mx=x,mn=n;
        l_up=lu,l_down=ld,r_up=ru,r_down=rd;
        l_ud=lud,l_du=ldu,r_ud=rud,r_du=rdu;
        res_u=su,res_d=sd;
    }
    inline node(const LD val){
        len=1;
        val_l=val,val_r=val,mx=val,mn=val;
        l_up=1,l_down=1,r_up=1,r_down=1;
        l_ud=0,l_du=0,r_ud=0,r_du=0;
        res_u=res_d=0;
    }
};

// 标记
struct tag{
    LD add,mul,cov; // 加/乘/覆盖 标记
    int is_cov; // 是否覆盖
};
const tag NO_TAG{0,1,0,0};  // 无标记
#define ADD_TAG(x) tag{x,1,0,0} // 区间 +x
#define MUL_TAG(x) tag{0,x,0,0} // 区间 *x
#define COV_TAG(x) tag{0,1,x,1} // 区间覆盖为 x

l_ud 和 r_du：

l_du 和 r_ud 同理。

若区间单调，则 l\_ud = l\_du = r\_ud = r\_du = 0 。

合并

区间合并

接下来是最恶心的区间合并，更新信息要分 8 种情况讨论，以下称待合并左区间为 a 右区间为 b 。

case 1： a_{l\_up} = a_{len}

根据 a_{val\_r} 和 b_{val\_l} 的大小关系更新 a_{l\_up} 或 a_{l\_ud} 。

case 2： a_{l\_down} = a_{len}

类似 case 1，不再赘述。

case 3： a_{l\_ud} = a_{len}

只有在 a_{val\_r} > b_{val\_l} 时更新 a_{l\_ud} 。

case 4： a_{l\_du} = a_{len}

类似 case 3，不再赘述。

case 5~8 就是用 b 更新，各位大佬应该都能自己推出来。

别急，还有更新答案，即 a 和 b 合并时对答案的贡献，分 2 种情况讨论。

case 1： a_{val\_r} > b_{val\_l}

c_{res\_u} \gets c_{res\_u} + (a_{r\_up}-1) b_{l\_down} + a_{r\_ud} b_{l\_down}

c_{res\_d} \gets c_{res\_d} + a_{r\_down} (b_{l\_up} - 1) + a_{r\_down} b_{l\_du}

case 2： a_{val\_r} < b_{val\_l}

同理。

还有不理解的可以看代码。

// 区间合并（重载运算符）
inline node operator+(const node &a,const node &b){
    node c(
        a.len+b.len,
        a.val_l,b.val_r,max(a.mx,b.mx),min(a.mn,b.mn),
        a.l_up,a.l_down,b.r_up,b.r_down,
        a.l_ud,a.l_du,b.r_ud,b.r_du,
        a.res_u+b.res_u,a.res_d+b.res_d
    );  // 先复制信息
    if(a.l_up==a.len){
        if(a.val_r<b.val_l) c.l_up+=b.l_up,c.l_ud=max(b.l_ud,b.l_down-1);
        if(a.l_up>1&&a.val_r>b.val_l) c.l_ud=b.l_down;
    }
    if(a.l_down==a.len){
        if(a.val_r>b.val_l) c.l_down+=b.l_down,c.l_du=max(b.l_du,b.l_up-1);
        if(a.l_down>1&&a.val_r<b.val_l) c.l_du=b.l_up;
    }
    if(a.l_ud&&a.l_up+a.l_ud==a.len){
        if(a.val_r>b.val_l) c.l_ud+=b.l_down;
    }
    if(a.l_du&&a.l_down+a.l_du==a.len){
        if(a.val_r<b.val_l) c.l_du+=b.l_up;
    }
    if(b.r_up==b.len){
        if(a.val_r<b.val_l) c.r_up+=a.r_up,c.r_du=max(a.r_du,a.r_down-1);
        if(b.r_up>1&&a.val_r>b.val_l) c.r_du=a.r_down;
    }
    if(b.l_down==b.len){
        if(a.val_r>b.val_l) c.r_down+=a.r_down,c.r_ud=max(a.r_ud,a.r_up-1);
        if(b.r_down>1&&a.val_r<b.val_l) c.r_ud=a.r_up;
    }
    if(b.r_ud&&b.r_ud+b.r_down==b.len){
        if(a.val_r<b.val_l) c.r_ud+=a.r_up;
    }
    if(b.r_du&&b.r_du+b.r_up==b.len){
        if(a.val_r>b.val_l) c.r_du+=a.r_down;
    }
    if(a.val_r>b.val_l){
        c.res_u+=1ll*(a.r_up-1)*b.l_down+1ll*a.r_ud*b.l_down;
        c.res_d+=1ll*a.r_down*(b.l_up-1)+1ll*b.l_du*a.r_down;
    }
    if(a.val_r<b.val_l){
        c.res_u+=1ll*a.r_up*(b.l_down-1)+1ll*b.l_ud*a.r_up;
        c.res_d+=1ll*(a.r_down-1)*b.l_up+1ll*a.r_du*b.l_up;
    }
    return c;
}

标记合并

这个相信都会，直接放代码。

inline tag& operator+=(tag &a,const tag &b){
    if(b.is_cov){   // b覆盖a
        a.add=0,a.mul=1,a.is_cov=1,a.cov=b.cov;
    }else{
        if(a.is_cov){
            a.cov=a.cov*b.mul+b.add;
        }else{
            a.mul*=b.mul,a.add*=b.mul;
            a.add+=b.add;
        }
    }
    return a;
}

标记合并进区间（？）

这个也不难。

如果乘法标记很小，不要当作 0 处理。

inline node& operator+=(node &a,const tag &b){
    if(b.is_cov){   //覆盖
        a.val_l=a.val_r=a.mx=a.mn=b.cov;
        a.l_up=a.l_down=a.r_up=a.r_down=1;
        a.l_ud=a.l_du=a.r_ud=a.r_du=0;
        a.res_u=a.res_d=0;
    }else{
        // 不能当作0处理
        // if(b.mul==zero){
        //     a.val_l=a.val_r=a.mx=a.mn=b.add;
        //     a.l_up=a.l_down=a.r_up=a.r_down=1;
        //     a.l_ud=a.l_du=a.r_ud=a.r_du=0;
        //     a.res_u=a.res_d=0;
        // }else{
        a.val_l=a.val_l*b.mul+b.add;
        a.val_r=a.val_r*b.mul+b.add;
        a.mx=a.mx*b.mul+b.add;
        a.mn=a.mn*b.mul+b.add;
        if(b.mul.val<0){    // 翻转正负
            swap(a.mx,a.mn);
            swap(a.l_up,a.l_down);
            swap(a.r_up,a.r_down);
            swap(a.l_ud,a.l_du);
            swap(a.r_ud,a.r_du);
            swap(a.res_u,a.res_d);
        }
        // }
    }
    return a;
}