「题解」集训模拟赛的另一道题目的另类解法

Table of contents

• 题目
• 分析
• 代码

题目

给定一个长度为 $n$ 的序列 $a$, 求有多少个子区间满足区间最大值与区间和在模 $k$ 意义下相等。 $n \le 3 \times 10^5, k \le 3\times 10^6, 1 \le a_i \le 10^4$

分析

考虑到一个数作为区间内最大值的时候，区间的左右端点范围是一段连续的区间。

我们可以利用单调栈线性地求出 $a_x$ 左右两端第一个大于自己的数字的位置 $l, r$，从而求得左右端点的区间分别是 $[l +1, x-1]$、$[x+1, r-1]$。

枚举每个数令其成为最大值，我们扫一遍左区间，开一个桶 $b_i$ 记录到区间内到 $x - 1$ 的一段后缀和，在模 $k$ 意义下为 $i$ 的位置数量。然后枚举右端点时维护从 $x + 1$ 开始的模 $k$ 意义前缀和 $s$，每次在 $b$ 里面查一下 $b_{k - s}$ 加到答案中就可以了。

有其中一个端点在 $x$ 位置上的特殊情况在两个端点扫过去的过程中加上即可。

上述算法的具体复杂度是值域相关且  我不会分析  比较难以分析的。在 $a$ 严格单增的时候达到最劣复杂度 $O(n^2)$。但注意到 $a_i$ 远小于 $n$，这种情况在本题并不会出现。

代码

#include <bits/stdc++.h>
  
const int MAX = 3e6 + 5;
  
struct N { int a, b; };
typedef long long ll;

int n, k, top; ll ans;
int a[MAX], lm[MAX], rm[MAX], L[MAX];
N s[MAX];
  
int main()
{
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); }
  for (int i = 1; i <= n; ++i)
  {
    while (top and s[top].a < a[i]) { rm[s[top].b] = i; --top; }
    if (!top) { lm[i] = 0; } else { lm[i] = s[top].b; }
    s[++top] = {a[i], i};
  }
  while (top) { rm[s[top].b] = n + 1; --top; }
  for (int i = 1; i <= n; ++i) { a[i] %= k; }
  for (int i = 1; i <= n; ++i)
  {
    int sl = 0, sr = 0;
    for (int j = i - 1; j > lm[i]; --j)
    {
      sl += a[j]; sl = sl >= k ? sl - k : sl; ++L[sl]; if (!sl) { ++ans; }
    }
    for (int j = i + 1; j < rm[i]; ++j)
    { 
      sr += a[j]; sr = sr >= k ? sr - k : sr; if (!sr) { ++ans; }
      int tmp = k - sr; tmp = tmp >= k ? tmp - k : tmp;
      ans += L[tmp];
    }
    sl = 0;
    for (int j = i - 1; j > lm[i]; --j)
    {
      sl += a[j]; sl = sl >= k ? sl - k : sl; --L[sl];
        }
  }
  printf("%lld", ans);
}