题解：P5012 水の数列

· · 题解

题目分析

给定一个长度为 N(N\le10^6)，值域为 [1, 10^6] 的整数数列 Num_1, Num_2, Num_3, \dots, Num_N。

定义区间数 \text{cnt}(x) 与分数 \text{score}(x)：

将 Num 中所有 \le x 的数标记后，连续标记的区间的数量（\text{cnt}(x)）与这些区间的长度的平方和（\text{score}(x)）。

下文称这样的区间为标记连续段。

有 T 次强制在线的询问，每次询问给出 [l, r](1\le l\le r\le n)，你需要选择 x，使得 \text{cnt}(x)\in[l,r]，同时最大化 \frac{\text{score}(x)}{x}，依次输出 \text{score}(x), x，如果无解输出 -1 -1。

解题思路

我们发现 \frac{\text{score}(x)}{x} 与 \text{cnt}(x) 无关，我们可以对所有 \text{cnt}(x)=i，初始化求出最优的 \text{score}(x), x，于是询问就变成了 RMQ 问题，但本题需要特殊处理无解的情况且内存限制较严，在后文会给出具体做法。

那么如何对所有 \text{cnt}(x)=i，求出最优的 \text{score}(x), x 呢？
显然考虑满足 \text{cnt}(x)=i 的 x 是困难的，我们不妨枚举可能的 x，然后去更新 \text{cnt}(x)=i 的最优解。

初始化

由于 N\le10^6, Num_i\le10^6，因此我们不能暴力 O(N\times Num_{max}) 初始化，注意到标记是单调变化的，随着 x 的增大，一个位置一定是从非标记到有标记之后不变的，因此枚举较大的 x 时可以复用较小的 x 的状态。

考虑当前从 x_1 递推到 x_2(x_1<x_2)，那么所有 Num_i\in (x_1, x_2] 都要被打上标记，其它部分不变，考虑如何更新 \text{cnt}(x), \text{score}(x)。
由于标记没有先后顺序之分，我们先考虑只给某个 Num_i 打标记，分以下情况讨论：

  2. + 原 $\text{score}(x)=\dots+S^2
    • 新 \text{score}(x)=\dots+(S+1)^2=\dots+S^2+(1+2\times S)
  3. + 原 $\text{score}(x)=\dots+{S_1}^2+{S_2}^2
    • 新 \text{score}(x)=\dots+(S_1+1+S_2)^2=\text{score}(x)=\dots+{S_1}^2+{S_2}^2+(1+2\times S_1+2\times (S_1+1)\times S_2)

不失一般性，我们可以将上述过程理解为以下等价步骤：

  1. 在 Num_i 处新建一个长度为 1 的标记连续段，\text{cnt}(x), \text{score}(x) 均增大 1。
  2. 将 Num_{i-1} 所在的标记连续段（如果存在）与 Num_i 所在的标记连续段合并。
  3. 将 Num_{i+1} 所在的标记连续段（如果存在）与 Num_i 所在的标记连续段合并。

每次合并两个长度分别为 S_1, S_2 的标记连续段时，\text{cnt}(x) 均减小 1，\text{score}(x) 增大 2\times S_1\times S_2，这实际上就是完全平方公式的应用。

上述算法需要快速查询某个位置所在标记连续段的大小，并合并两个标记连续端，这实际上就是一个加权并查集的操作，而且大小 S 只需要在根上维护即可。

根据题意可知，所有对答案有贡献的 x 必然出现在 Num 中，如若不然，设 x 在 Num 中的前驱为 x'，则 \text{score}(x')=\text{score}(x)，\frac{\text{score}(x')}{x'}>\frac{\text{score}(x)}{x}，因此我们直接按 Num 中的数从小到大递推即可。

当然，也需要快速知道 Num_i\in (x_1, x_2]，由于我们的递推顺序是按 Num 中的数从小到大，那么不存在 Num_i\in(x_1,x_2)，我们只需要知道 Num_i=x_2 即可。

定义二元组 (i, Num_i) 数组 B，然后按第二元素 Num_i 升序排序，递推时按排序后的 B 的第二元素 Num_i 顺序枚举 x，根据第一元素 i 得到 Num_i=x_2 的位置 i，然后用并查集更新 \text{cnt}(x), \text{score}(x)。
需要注意可能有多个 i 满足 Num_i=x_2，使用双指针来统一更新。

枚举到某个 x 时，将其与 \text{score}(x) 写入 \text{cnt}(x) 更新最优解，完成后我们对所有有解的 \text{cnt} 都得到了最优的 \text{score}(x), x。

处理询问

有多种方式可以处理本题的 RMQ 询问，这里以 ST 算法为例说明。

设上面的预处理得到了 A_0, A_1, A_2, \dots，其中 A[i] 表示区间长度为 i 时的最优解 \text{score}(x), x。
注意，一个长度为 N 的数列最多有 \lceil\frac{N}{2}\rceil 个连续段，因此只需要定义 A[0\sim500000]。

定义 dp[i][k] 表示 \text{cnt}(x)\in[i, i+2^k) 时的最优解，每次询问 [l, r] 时可以拆分为两个 dp[\ ][k]，取最优的那一个即可，这和标准 ST 算法没什么差别。

但是本题目空间限制较严，有以下方式可以减少空间使用：

  1. 极限化 dp 的长度。
    前面提到 A 的可能下标范围为 [0, 500000]，因此 dp 第一维长度只需要定义 500001。
    因为 2^{18}=262144, 2\times262144=524288>500000，因此第二维的可能下标为 [0, 18]，第二维长度只需要定义 19。
  2. 如果我们直接存 $\text{score}(x), x$，前者需要一个 $\text{int32}$，后者需要一个 $\text{int64}$，总计需要 $12B$ 的大小，但是我们可以只存最优解的**映射**，例如在 $A$ 中的下标（显然最优解必然存在于 $A$ 中），那么只需要 $4B$ 的大小即可。上面对 $B$ 排序也可以采用同样的方法优化。

注意询问区间可能越界，前面提到 1\le l\le r\le n，这意味着 r 可能超过 500000，因为不可能有大于 500000 个连续段，我们可以 r\leftarrow min(r,500000)，如果这样后发现有 l>r，意味着 l>500000，显然无解。

下面的代码维护了一个 max_set，表示可能的最多标记连续段数 S_{max}，查询时 r\leftarrow min(r,S_{max})

无解对应的状态应该严格小于任何有效解，一种方法是定义无解为 x>0, \text{score}=0，其有效性基于上面初始化时写入的 \text{score} 全为正数，这样输出答案时可以通过 [\text{score}=0] 判断是否无解。

比较问题

题目中说"如果有多解则输出选择的数最大的一组"，但是测试数据似乎并没有体现这一点，严谨起见我们考虑这一点，以下是关于这一点的 hack 数据：

输入

3 1
1 4 9
0 0 1 1

答案

4 4
1 1 0

比较的第一关键词为 \frac{\text{score}(x)}{x}，第二关键词为 x。

比较第一关键词时，有以下比较方法：

  1. 直接用浮点数存储分数结果，注意引入 \text{eps} 来正确判断浮点数相等。
  2. 将除法比较转换为乘法比较，例如 [\frac{\text{score}(x)}{x}<\frac{\text{score}(x')}{x'}]=[\text{score(x)}\times x'<\text{score}(x)\times x]。

注意运算过程中是否需要强制类型转换，例如计算浮点数除法结果时，需要先转为浮点数。
注意第一关键词相等时要比较第二关键词。

题目特色

我们已经完成了题目的主要问题，但是接下来的题目特色部分坑点较多，这里展开阐述。

l = (a * lastans + x - 1) % n + 1;
r = (b * lastans + y - 1) % n + 1;
if (l > r) swap(l, r);

其中 lastans 表示上一次询问的最大分数(原始得分)和得到这个最大的分数的 x 的乘积，即 lastans=\text{score}(x)\times x。

其中 \max\{\text{score}(x)\}=(10^6)^2=10^{12}，\max\{x\}=10^6，\max\{lastans\}=\max\{\text{score}(x)\}\times\max\{x\}=10^{12}\times10^6=10^{18}，接近 \text{int64} 的上限，上面的 a * lastans, b * lastans 可能超出 \text{int64} 的范围，下面给出三种解决方案：

  1. 用 \text{int128}（__int128）存储这一步的中间结果。
  2. 根据模运算的性质，计算时先对 lastans 取模 N。
  3. 在更新 lastans 时，直接对 lastans 取模 N，即 lastans=(\text{score}(x)\times x)\mod N，这样做在输出 lastans \mod N 时就可以直接输出 lastans。

代码

AC 记录

云剪贴板存档

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int64;
constexpr int MAX_N = 1000000;
constexpr int MAX_NUM = 1000000;
constexpr int MAX_STSIZE = 18;

int n, T, Num[MAX_N+1];

struct stu1{
    int x;
    int64 score;
    // 无解情况，即默认的 score/x 需要小于 1/MAX_NUM
    // 这里令 score 的默认值为 0 表示无解状态 
    inline stu1(int x_ = 1, int64 score_ = 0) : x(x_), score(score_){};
    inline friend bool operator<(const stu1& a, const stu1& b){
        int64 tmp1 = a.score*b.x, tmp2 = b.score*a.x;
        // 如果有多解则输出选择的数最大的一组
        return (tmp1==tmp2 && a.x<b.x) || tmp1<tmp2;
    };
    inline void update(const stu1& other){ if(*this<other) *this = other; };
    inline bool valid()const{ return score>0; };
} A[(MAX_N+1)/2+1];
int max_set;                         // 最多标记连续端数，用于对 r 剪枝 
int Log2[(MAX_N+1)/2];               // 用于 O(1) ST 查询 
int dp[(MAX_N+1)/2+1][MAX_STSIZE+1]; // ST 表，存对应的 A[] 下标

// 并查集，注意初始状态为 fa[x]=0，表示 x 暂未被标记，不属于任何一个标记连续段
int fa[MAX_N+1], size[MAX_N+1];
int find_set(int x){ return fa[x]==x?x:fa[x]=find_set(fa[x]); }
inline void merge(int x, int y, int& set_cnt, int64& score){ // 注意引用 & 
    x = find_set(x);
    y = find_set(y);
    --set_cnt;
    score += 2ll*size[x]*size[y];
    size[y] += size[x]; // 只需要更新根的 size 
    fa[x] = y;
}
// B[i] = (i, Num[i]) 只存储 i 
int Num_map[MAX_N];
inline bool cmp_Num_map(int a, int b){
    return Num[a]<Num[b];
}
void init(){
    for(int i=1; i<=n; ++i) Num_map[i-1] = i;
    sort(Num_map, Num_map+n, cmp_Num_map);

    max_set = 0;
    int set_cnt = 0; // 标记连续段数 cnt(x)
    int64 score = 0; // 分数 score(x)
    for(int i=0, j=0; i<n; i=j){
        int x = Num[Num_map[i]];
        while(j<n && Num[Num_map[j]]==x) ++j; // 用双指针维护，统一处理所有相等值 
        for(int k=i; k<j; ++k){
            int id = Num_map[k];
            // 以自己的编号为集合的编号创建新集合 
            fa[id] = id;
            size[id] = 1;
            ++set_cnt;
            ++score;
            // 与左边的连续段合并
            // id-1>=1 可省略，因为 fa[0] 始终为 0 
            if(id-1>=1 && fa[id-1]) merge(id, id-1, set_cnt, score);
            // 与右边的连续段合并
            // 如果 fa[] 开到 1000002 也可省略 id+1<=n
            if(id+1<=n && fa[id+1]) merge(id, id+1, set_cnt, score);
        }
        max_set = max(max_set, set_cnt);
        A[set_cnt].update(stu1(x, score));
    }

    // Log2[] 最多用到 max_set-1 
    Log2[0] = Log2[1] = 0;
    for(int i=2; i<max_set; ++i) Log2[i] = Log2[i>>1]+1;

    for(int i=1; i<=max_set; ++i) dp[i][0] = i;
    int maxk = Log2[max_set-1];
    for(int k=1; k<=maxk; ++k){
        int maxi = max_set-(1<<k)+1;
        for(int i=1; i<=maxi; ++i){
            int l = dp[i][k-1], r = dp[i+(1<<(k-1))][k-1];
            dp[i][k] = (A[l]<A[r] ? r : l);
        }
    }
}

const stu1& query(int l, int r){
    r = min(r, max_set); // 对 r 剪枝 
    if(l>r) return A[0]; // 说明 l>max_set，无解，A[0] 表示一个无解状态

    // ST 查询
    int k = Log2[r-l];
    int a = dp[l][k], b = dp[r-(1<<k)+1][k];
    return A[a]<A[b] ? A[b] : A[a]; 
}

int main(){
    scanf("%d%d", &n, &T);
    for(int i=1; i<=n; ++i) scanf("%d", Num+i);
    init();

    int lastans = 0; // 实际上是 lastans%n，正确性由模运算性质保证 
    while(T--){
        int a, b, x, y;
        scanf("%d %d %d %d", &a, &b, &x, &y);
        int l = ((int64)a*lastans+x-1)%n+1;
        int r = ((int64)b*lastans+y-1)%n+1;
        if(l>r) swap(l, r);

        const stu1& ans = query(l, r);
        if(ans.valid()){
            printf("%lld %d\n%d %d %d\n", ans.score, ans.x, l, r, lastans);
            lastans = ans.score*ans.x % n;
        }else{
            printf("-1 -1\n%d %d %d\n", l, r, lastans);
            lastans = 1;
        }
    }
    return 0;
}