P5012 水の数列

水の数列：一道难题是如何生长出来的

问题

P5012 水の数列
选择阈值 $x$，标记所有 $a_i\le x$ 的位置。设连续标记段的长度平方和为 $val$、段数为 $cnt$，得分为 $val/x$。每次强制在线询问要求 $cnt\in[l,r]$，输出最优方案的 $val$ 和 $x$。

数据规模：$n\le10^6$，$T\le10^3$，$a_i\le10^6$。

这道题的题目背景很有意思，它展示了一道难题是如何得出的。每一次增加新的限制条件，都会让原本最直接的做法失效，然后逼迫我们寻找新的性质以及数据结构来解决它。

我们从 0 限制开始逐一破解这道题。

Q0 选定一个 $x$，使得得分最高

标记所有 $a_{i} \le x$ 的位置，然后计算所有连续段的长度平方和。我们发现，随着 $x$ 的增大，被标记的位置只会越来越多。那么显然直接取 $x$ 为最大值，此时所有位置连成长度为 $n$ 的整段，这就是能够得到的最大得分。

Q1 得分除以选择的数

如果得分变成 $\displaystyle \frac{val(x)}{x}$，这个时候就不能再简单地只考虑原始得分的单调性了。

我们研究随着 $x$ 逐渐增大时，标记状态是如何变化的。假设两个相邻的不同权值为 $v_{i} < v_{i+1}$，当 $v_{i} \le x < v_{i+1}$ 时，被标记的位置完全相同，因此 $val(x)$ 和 $cnt(x)$ 都不会发生变化，但分母越大，得分越小。

所以对于同一种标记状态，我们一定选择能产生该状态的最小阈值，只用考虑数组中实际出现的权值即可。

将所有位置按照 $a_{i}$ 从小到大排序，当处理到某个权值 $x$ 时，将所有满足 $a_{i} = x$ 的位置激活，然后在处理完这一组位置后，就得到了一组得分。

于是我们枚举所以可能的 $x$ 以及对应的得分 $\displaystyle \frac{val(x)}{x}$，取一个最大值即可。

但是，如果每次处理一个阈值，都重新扫描整个数组计算连续段数量和长度平方和，总复杂度会达到 $O(n^2)$，显然无法接受。

回到题目，我们发现一次激活只会改变当前位置与左右两个邻居之间的连通关系，所以可以采用并查集来完成维护。

激活一个新位置时，它会先独立形成一个长度为 $1$ 的连续段，因此 cnt ++, val ++。随后只需要检查已经激活的左右邻居，并将相邻的连续段合并。未激活的位置不能提前作为有效的并查集节点，否则它们也会错误地参与合并。

接着考虑合并两个连续段。设两个连续段的长度分别为 $s_1$ 和 $s_2$，合并前的贡献为 $s_{1}^{2} + s_{2}^{2}$，合并后的贡献为 $(s_{1} + s_{2})^{2}$，作差得到增量 $\delta = 2s_{1}s_{2}$。于是每次成功合并，都可以让连通块数量 cnt --，同时令 val += 2 * s1 * s2。

注：相同权值的所有位置必须全部激活后再保存状态。因为选择某个阈值 $x$ 时，所有满足 $a_i = x$ 的位置会同时被标记，不存在只激活其中一部分的合法状态。

Q2 区间限制

这次限制 $l \le cnt(x) \le r$，这就意味着每次询问允许的阈值集合不同，不能只保存一个全局最优方案。

发现询问关心的其实是该 $x$ 产生的连续段数量，而不是 $x$ 本身。于是我们定义 $best[k]$ 表示所有能够产生恰好 $k$ 个连续段的阈值中，得分最优的状态。

为了方便分数比较，每个状态记录 x, val 分别表示 阈值 和 原始平方和，实际得分就是 val / x。

那么问题就转化为了在 $best[l, \dots, r]$ 中寻找得分最大的状态。由于只有单次询问，我们直接枚举 $[l, r]$ 这一段上的 $best$ 求最值即可。

那么还有一个问题，如何准确的比较两个分数，我们可以采用交叉相乘来避免浮点误差：

$$\frac{A.val}{A.x} > \frac{B.val}{B.x} \iff A.val \cdot B.x > B.val \cdot A.x$$

乘积需要使用 __int128 防止溢出；如果两个得分相同，则按照题意选择更大的 $x$。

Q3 多次区间询问

既然我们已经有了 $best[l, \dots, r]$，现在需要多次求区间最值，就可以直接使用 ST 表来实现查询，这一层扩展在模型上比较直接。

虽然这里比较的不是普通最大值，但 better 给出了固定的全序关系，因此“取更优状态”仍然可以作为 ST 表的合并运算。为了节省空间，ST 表中只需要保存 best[] 的下标。

Q4 强制在线

很好，这一步锁死了对询问重新排序、离线处理的可能。

但是实际上我们发现，前面的 ST 表和 DSU 预处理都与询问顺序无关，因此只要按照输入顺序使用 ST 表查询即可。

所以这个扩展除了让回答询问时麻烦了一点以外，并没有改变前面的核心模型。

实现时需要注意，计算 $l,r$ 的乘积可能超过 long long，应先转成 __int128；输出的 lastans % n 是本次计算端点时使用的旧值；如果当前询问无解，则按照题意令 lastans = 1。

预处理排序与并查集操作复杂度为 $O(n\log n)$，建立 ST 表为 $O(n\log n)$，每次询问为 $O(1)$。

▶

P5012

struct DSU {
/* ======================================== */
int fa[maxn], siz[maxn];
void init( int N ) { for( int i = 1; i <= N; ++ i ) fa[i] = 0, siz[i] = 0; }
int find( int x ) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }
bool merge( int x, int y, ll &val ) {
    int rx = find( x ), ry = find( y );
    if( rx == ry ) return 0;
    val += 2ll * siz[rx] * siz[ry];
    if( siz[rx] > siz[ry] ) swap( rx, ry );
    fa[rx] = ry, siz[ry] += siz[rx];
    return 1;
}
void active( int x ) { fa[x] = x; siz[x] = 1; }
bool check( int x ) { return fa[x] != 0; }
/* ======================================== */
} dsu;

struct State {
    int x; ll val;
} best[maxcnt];

bool better( State A, State B ) {
    if( A.x == 0 ) return 0;
    if( B.x == 0 ) return 1;
    i128 lhs = (i128)A.val * B.x;
    i128 rhs = (i128)B.val * A.x;
    if( lhs != rhs ) return lhs > rhs;
    return A.x > B.x;
}

int id( int x, int y ) {
    return better( best[y], best[x] ) ? y : x;
}

struct ST {
/* ======================================== */
int st[maxcnt][maxlg], lg2[maxn];
void init_lg( int N ) {
    lg2[1] = 0;
    for( int i = 2; i <= N; ++ i ) lg2[i] = lg2[i >> 1] + 1;
}
void init( int N ) {
    init_lg( N );
    for( int i = 1; i <= N; ++ i ) st[i][0] = i;
    for( int j = 1; ( 1 << j ) <= N; ++ j ) {
        for( int i = 1; i + ( 1 << j ) - 1 <= N; ++ i ) {
            st[i][j] = id( st[i][j - 1], st[i + ( 1 << (j - 1) )][j - 1] );
        }
    }
}
int query( int l, int r ) {
    int k = lg2[r - l + 1];
    return id( st[l][k], st[r - (1 << k) + 1][k] );
}
/* ======================================== */
} st;

struct Node {
    int val, idx;
    bool operator < ( const Node &oth ) const { return val < oth.val; }
} b[maxn];

void solve( ) {
    int n = read( ), T = read( );

    for( int i = 1; i <= n; ++ i ) {
        int x = read( );
        b[i] = { x, i };
    }

    sort( b + 1, b + n + 1 );
    dsu.init( n );

    ll val = 0;
    int cnt = 0;
    int mx = 0;

    for( int l = 1; l <= n; ) {
        int x = b[l].val;
        int r = l;

        while( r <= n && b[r].val == x ) {
            int pos = b[r].idx;
            
            dsu.active( pos );
            cnt ++, val ++;

            if( pos - 1 >= 1 && dsu.check( pos - 1 ) ) {
                if( dsu.merge( pos, pos - 1, val ) ) cnt --;
            }

            if( pos + 1 <= n && dsu.check( pos + 1 ) ) {
                if( dsu.merge( pos, pos + 1, val ) ) cnt --;
            }
            ++ r;
        }

        State cur = { x, val };
        if( better( cur, best[cnt] ) ) {
            best[cnt] = cur;
        }
        mx = max( mx, cnt );
        l = r;
    }

    st.init( mx );
    ll lst = 0;

    while( T -- ) {
        ll a = read( ), b = read( ), x = read( ), y = read( );
        int l = ((i128)a * lst + x - 1) % n + 1;
        int r = ((i128)b * lst + y - 1) % n + 1;
        if( l > r ) swap( l, r );
        ll lstmod = lst % n;

        if( l > min( r, mx ) ) {
            cout << "-1" << " " << "-1" << '\n';
            cout << l << " " << r << " " << lstmod << '\n';
            lst = 1;
            continue;
        }

        int idx = st.query( l, min( r, mx ) );
        State ans = best[idx];

        if( ans.x == 0 ) {
            cout << "-1" << " " << "-1" << '\n';
            cout << l << " " << r << " " << lstmod << '\n';
            lst = 1;
        }
        else {
            cout << ans.val << " " << ans.x << '\n';
            cout << l << " " << r << " " << lstmod << '\n';
            lst = ans.val * ans.x;
        }
    }
}

记录

• 归属：[[并查集]] | [[ST 表]]

• 新增：把阈值变化转成按权值激活，用并查集同步维护连续段数量与平方和；再按段数压缩状态，用自定义全序的 ST 表回答区间最优方案。

• 分类：C