leetcode 第 446 场算法比赛 - 高级线段树

零、背景

发现最近一直没状态，赛后想一下，题目都不难。

A: 模拟
B: 单调栈
C: 简单DP
D: 高级线段树

排名：200+
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、执行指令后的得分

题意：给一个指令列表，按指令操作，求最终得分。

指令分为两个：
1）add，当前位置的值是得分。
2）move，当前位置的值是移动距离，向右移动，如果是负数则向左移动。

要求：每个位置只能到达一次，第二次到达或者移动到区间外则结束指令。

思路：模拟

按题意进行模拟，并记录曾经到达的位置。

二、非递减数组的最大长度

题意：给一个数组，每次可以选择一个子数组替换为一个数字，值为子数组中的最大值，问最终使得数组非递减的最大长度。

思路：单调栈

分析：子数组替换为最大值，又要求非递减，则对于最大值，后面的元素必然需要与最大值一起组成子数组，否则无法保证非递减。

基于这个分析递推推导，第一次把最大值后面的都替换为最大值，第二次把次大值到最大值之间的子数组替换为次大值，依次类推。

这个可以使用逆序单调栈来实现。
复杂度：O(n)

vector<int> st;
st.reserve(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
  while (!st.empty() && st.back() < nums[i]) {
    st.pop_back();
  }
  st.push_back(nums[i]);
}
return st.size();

三、求出数组的 X 值 I

题意：给一个数组和X，一次操作可以删除数组的前缀和后缀得到一个非空子数组，非空子数组各元素乘积模 k 的值为 x，问有多少个子数组满足这个条件。
数据范围：1<=k<=5

思路：简单DP

状态定义：dp[i][j]表示前 i 个元素中，以 i 位置为后缀的所有子数组中，乘积 模 k 的值为 j 的子数组的个数。
状态转移方程：

dp[i+1][(j * nums[i]) % k] += dp[i][j]

答案是所有 dp[i][x] 的和。
复杂度：O(n*k)

复杂思路：逆元前缀积

假设我们计算统计了所有前缀积的个数，需要找到一个当前位置为后缀的子数组，使得子数组的乘积模 k 的值为 x，则可以推导出下面的公式：

prefix * x % k = now

从而可以计算出 prefix = now * x^-1 % k，其中 x^-1 是 x 的逆元。

这个公式对于大部分 k 都成立，但是对于 k=4 不成立，原因是 x 为 2 时不存在逆元。
另外，对于所有 x 为 0 的情况，逆元也都不成立。

我的想法是，对于其他情况，使用逆元计算。
对于特殊计算，特殊计算即可。

特殊情况1： x=0, 子数组只要包含1个0 就满足条件，故枚举起始位置，计算最短子数组，之后的都满足情况。
0 处理后，可以对数组分割为若干个不包含0 的子数组，每个子数组单独处理。

特殊情况2： k=4 & x=0, 当两个2组合在一起时，也会变成0。
故需要单独统计这种情况下，有多少个子数组可以组合成0。

特殊情况3： k=4 & x=2, 当只有一个2，其他都是奇数时，答案是2。

四、求出数组的 X 值 II

题意：与第三题类似，不过子数组数组不再是任意删除前缀和后缀，而是删除固定前缀+任意后缀，问个数。
另外，还增加了修改操作，有多个询问。

思路：线段树

线段树需要储存两个值：
1）整个区间的乘积。
2）区间内所有前缀的乘积分布。

vector<int> allVal;
vector<vector<ll>> preVal;  // 记录最值的位置

有这两个值，左右子区间可以合并计算出父区间。

如下，整个区间直接相乘，前缀则分为两部分：左区间乘积分布继承不变，右区间前缀乘积分布乘以整个左区间，就是剩余的前缀乘积分布。

// 合并函数，按需进行合并
void PushUp(int rt, int l, int r) {
  allVal[rt] = (allVal[rt << 1] * allVal[rt << 1 | 1]) % k;
  for (int i = 0; i < k; i++) {
    preVal[rt][i] = preVal[rt << 1][i];
  }
  int leftAllVal = allVal[rt << 1];
  for (int i = 0; i < k; i++) {
    preVal[rt][(i * leftAllVal) % k] += preVal[rt << 1 | 1][i];
  }
}

变更操作与初始化类似，单点更新后，更新整个路径的值即可。

查询时，右区间的答案依赖于左区间的整个区间的乘积，即第三题提到的乘法逆元。

左区间无脑递归即可，递归的时候顺便计算下整个前缀的乘积，最后到具体位置时，通过乘法逆元来找到所有满足要求的位置。
逻辑比较复杂，属于高级线段树的用法，具体看代码会更容易理解。

ll QueryPre(int L, int R, int val, int& pre, int l = 1, int r = maxNM, int rt = 1) {
  if (L <= l && r <= R) {
    ll ans = 0;
    for (int i = 0; i < k; i++) {
      if (pre * i % k == val) { // 找到所有的前缀，满足模k等于 val
        ans += preVal[rt][i];
      }
    }
    pre = pre * allVal[rt] % k;
    return ans;
  }
  int m = (l + r) >> 1;
  ll ret = 0;
  if (L <= m) {
    ret += QueryPre(L, R, val, pre, lson);
  }
  if (m < R) {
    ret += QueryPre(L, R, val, pre, rson);
  }
  return ret;
}

四、最后

这次比赛第三题我想复杂了，乘法逆元存在反例，最终在写各种特殊判断去修复反例，浪费了很多时间。
最后一题则是稍微高级的线段树，查询右区间时依赖左区间的结果，理解难度稍微高一些。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号： tiankonguse
公众号 ID： tiankonguse-code