既已身披英雄之名，就应具备不容撼动的觉悟

FutaRimeWoawaSete · 2022-12-31 18:16:40 · 题解

sol of P8868

恕我直言，此题的难点在于构造双半群模型，如果只是讲解维护的信息，那么可以看懂此题，但是若在之后碰到类似的题目却还是只能瞎构造半天导致浪费大量时间，导致痛失其他题的分。

本篇题解想大致探索一下幺半群信息构造的方法，但并不是极其严谨与科学，你可以理解成民科吧！主要是市面上没有啥讲信息构造的，如果你做题不多其实很容易被坑。

一些极其一眼的思考：扫描线，然后转化成带历史和的 X_{i} \times Y_{i}，修改操作是二元信息区间覆盖，信息是求和，盲猜可做，于是难点来到如何设计双半群模型，构造信息。

从自己博客里搬点东西过来。

半群

给定一个集合 D 以及一个集合 D 上的二元运算 \times 满足 D \times D \rightarrow D。

对于该运算满足结合律：a,b,c \in D,(a \times b)\times c = a \times (b \times c)。

幺半群

给定一个集合 D 以及一个集合 D 上的二元运算 \times 满足 D \times D \rightarrow D。

对于该运算满足结合律：a,b,c \in D,(a \times b)\times c = a \times (b \times c)。

满足幺元存在使得：a,\epsilon \in D,a \times \epsilon = \epsilon \times a = a。

交换半群

给定一个集合 D 以及一个集合 D 上的二元运算 \times 满足 D \times D \rightarrow D。

对于该运算满足结合律：a,b,c \in D,(a \times b)\times c = a \times (b \times c)。

对于该运算满足交换律：a,b,c \in D,a \times b = b \times a。

范围

常见的范围有序列区间，树简单路径，二维平面矩形，高维正交范围，半平面范围，圆范围。

我们一般理解成对于进行修改和查询的信息的限制。

双半群模型

直接再次贺一下 lxl PPT 里的图。

还需要注意的是对于 D \times M \rightarrow D 的 \times 运算对于 (D,+) 运算具有分配律。

我们称这样的模型为双半群模型。

需要注意的是，采取线段树，维护的信息至少是半群信息，然而大多数时候也是交换半群信息。

那么我们需要做到的是设计 D,M 去满足上述的双半群模型，在大多数时候我们采取的下传标记信息都是维护 D 的增量，根据题意也应当适当添加其它下传标记信息像区间覆盖区间乘法等等，此题就是区间覆盖。

我们根据一些表象的信息，比如这里有区间覆盖，那我们知道我们的下传标记信息至少有一个 c_x,c_y 表示对于区间 x 元和 y 元的覆盖。

其次尝试构造 D。我们先来尝试一些区间覆盖的影响，假设一直修改 x 那么貌似我们可以加 \sum y 这样的东西。当然如果你要套路化，在观察到 X_i \times Y_i 这样的结构的时候就可以以此为最高次，构造一个多项式形式的 D 类信息，即维护扫描线时当前的 \sum X_i \times Y_i,\sum X_i,\sum Y_i 以及 s 表示区间历史和 len 表示区间长，形式化地记为 D = (s_{xy},s_x,s_y,s,len)。

对于下传标记的信息，通过尝试修改带来的影响，或者放弃思考，套路化地设成 M = (c_x,c_y,m_{xy},m_x,m_y,m)，表示区间覆盖 x/y，在该合并信息 M 中的覆盖标记未下传前，对于子树内 D 中 s 的贡献需要加上 m_{xy} \times D_{s_{xy}} + m_x \times D_{s_{x}} + m_y \times D_{s_y} + m \times D_{len}。

定义下传标记信息中对于贡献加法的优先级高于覆盖标记是有理由的，比如说纯区间覆盖，区间加，区间求和，一种实现方法就是下传信息时先让加标记下传，然后再下传区间覆盖标记，因为加标记的信息依赖于未被覆盖之前的区间信息，你让覆盖标记优先于加法标记下传就会让加标记无所依赖，难以维护。

在大多数时候，你要相信你通过常规的标记设计出来的 D,M 是满足 D 是交换半群和半群信息的，以防万一你可以验证一下。

所以只需要构造出来三类关系，D \times M \rightarrow D,D + D \rightarrow D,M \text * M \rightarrow M 的具体操作就好了。

构造难度基本和 D,M 的维护标记个数正相关。此题你发现 D + D \rightarrow D 就是最简单的！写成代码就是：

inline info merge(info x,info y){return info(x.s + y.s , x.sx + y.sx , x.sy + y.sy , x.sxy + y.sxy);}   

其次我们构造 D \times M \rightarrow D，直接放代码然后解释：

inline info merge(info x,tag y,int len)
{
    x.s += y.axy * x.sxy + y.ax * x.sx + y.ay * x.sy + y.c * len;
    if(y.cx && y.cy)
    {
        x.sxy = len * y.cx * y.cy;
        x.sx = len * y.cx;
        x.sy = len * y.cy;
    }
    else if(y.cx)
    {
        x.sxy = x.sy * y.cx;
        x.sx = len * y.cx;
    }
    else if(y.cy)
    {
        x.sxy = x.sx * y.cy;
        x.sy = len * y.cy;
    }
    return x;
}

即对于 s 我们根据定义先直接更新一遍；然后再根据是否有覆盖标记修改 s_{xy},s_x,s_y，这个比较简单就不多说了。

最后我们构造 M \text{*} M \rightarrow M。

还是贴代码解释：

inline tag merge(tag x,tag y)//x -> y
{ 
    if(y.cx && y.cy) y.c += x.axy * y.cx * y.cy + x.ax * y.cx + x.ay * y.cy + x.c;
    else if(y.cx) 
    {
        y.ay += x.axy * y.cx + x.ay;
        y.c += x.c + x.ax * y.cx;
    }
    else if(y.cy)
    {
        y.ax += x.axy * y.cy + x.ax;
        y.c += x.c + x.ay * y.cy;
    }
    else 
    {
        y.axy += x.axy;
        y.ax += x.ax;
        y.ay += x.ay;
        y.c += x.c;
    }
    if(x.cx) y.cx = x.cx;
    if(x.cy) y.cy = x.cy;
    return y;
}