单调栈救爷爷。

UnyieldingTrilobite · 2024-06-29 23:46:24 · 个人记录

半夜发癫一则。

不难发现单调栈期望长度是 \log，但我们暴力跳过不去。

于是我们每 \sqrt{\log} 个位置打个断点，类似 BSGS 那样跳就可以了。

期望复杂度 O((n+m)\sqrt{\log{n}})。注意到后者差不多是个常数于是写法可以比较魔怔。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 9;
int n, m, s, a[N], lb[N], lb6[N];
unsigned long long ans;
namespace GenHelper {
unsigned z1, z2, z3, z4, b;
inline unsigned rand_() {
  b = ((z1 << 6) ^ z1) >> 13;
  z1 = ((z1 & 4294967294U) << 18) ^ b;
  b = ((z2 << 2) ^ z2) >> 27;
  z2 = ((z2 & 4294967288U) << 2) ^ b;
  b = ((z3 << 13) ^ z3) >> 21;
  z3 = ((z3 & 4294967280U) << 7) ^ b;
  b = ((z4 << 3) ^ z4) >> 12;
  z4 = ((z4 & 4294967168U) << 13) ^ b;
  return (z1 ^ z2 ^ z3 ^ z4);
}
}  // namespace GenHelper
inline void srand(unsigned x) {
  using namespace GenHelper;
  z1 = x;
  z2 = (~x) ^ 0x233333333U;
  z3 = x ^ 0x1234598766U;
  z4 = (~x) + 51;
}
inline int read() {
  using namespace GenHelper;
  int a = rand_() & 32767;
  int b = rand_() & 32767;
  return a * 32768 + b;
}
signed main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n >> m >> s, srand(s);
  for (int i = 1; i <= n; ++i) {
    int v = a[i] = read(), &j = lb[i] = i - 1;
    while (j && a[j] <= v) j = lb[j];
  }
  for (int i = 1; i <= n; ++i) lb6[i] = lb[lb[lb[lb[lb[lb[i]]]]]];
  for (int l, r; m; --m) {
    l = read() % n + 1, r = read() % n + 1;
    if (l > r) swap(l, r);
    while (lb6[r] >= l) r = lb6[r];
    while (lb[r] >= l) r = lb[r];
    ans += a[r];
  }
  return cout << ans << endl, 0;
}