QOJ #9604. Cyberangel 题解

Description

Bronya 想给《阿拉哈托·集训队互测》出个新的 DLC，但是想不到好的 idea。

她现在有 nn 个 idea，每个 idea 都有一个难度值 aia_i，满足 1≤ai≤m1 \le a_i \le m。

她现在打算在这些 idea 中抽取一个 idea 作为最终 idea，她的抽取方式如下：

随机在 n(n+1)2\dfrac{n(n+1)}{2} 个区间中，等概率抽取一个编号区间 [l,r][l,r]，然后再在 [1,m][1,m] 中等概率抽取一个整数作为难度上限 limlim，

然后 Bronya 会在所有满足 i∈[l,r],ai≤limi \in [l,r], a_i \le lim 的 ii 中选一个 aia_i 最大的 ii 作为 xx。

此时 axa_x 会作为最终的难度值，若这样的 xx 不存在，那最终的难度值为 00。

Bronya 想知道最终难度值的期望，请你帮帮可爱的她。

由于期望是高贵的 1010 级算法，小 Bronya 不会，所以请你输出期望乘以 n×(n+1)×m2\dfrac{n \times (n+1) \times m}{2} 的值。

n≤106,m≤109n\leq 10^6,m\leq 10^9。

Solution

首先显然可以先枚举 limlim，相当于单点激活，查询所有子区间的最大值的和。

这个东西是不太好直接做的，考虑分治，这样就只需要考虑每个经过分治中心的区间 [l,r][l,r] 的最大值就可以表示为 [l,mid][l,mid] 的最大值和 [mid+1,r][mid+1,r] 最大值的 max⁡\max。

然后对于每个位置，计算其对答案的贡献。

不妨设 bib_i 表示在当前 limlim 下每个位置的实际值，kk 为左区间的一点。

容易发现只有 bkb_k 是左区间的后缀最大值时才会有贡献，这个用单调栈能维护。

设 prekpre_k 表示 kk 左边第一个实际值大于 bkb_k 的位置，pkp_k 表示右区间第一个实际值大于 bkb_k 的位置，则 kk 的贡献为：bk⋅(k−prek)⋅(pk−mid)b_k\cdot(k-pre_k)\cdot(p_k-mid)。

对于右区间的 kk，设 nxtknxt_k 表示 kk 右边第一个实际值大于 bkb_k 的位置，pkp_k 为左区间第一个实际值大于等于 bkb_k 的位置，kk 的贡献为：bk⋅(nxtk−k)⋅(mid−pk)b_k\cdot(nxt_k-k)\cdot(mid-p_k)。

然后从小到大激活点，对每个点 ii 维护一个并查集表示 pk=ip_k=i 的 kk 的信息，即 ii 能管辖的集合。假设当前激活的是左区间的 xx，则先在左区间的单调栈里弹栈，被弹掉的位置就没有贡献了。

同时所有被弹掉的位置所管辖的集合都将并到 kk 里。最后对 kk 和弹完后栈顶的信息单独处理即可。

对于右区间同理。

时间复杂度：O(nlog⁡nα(n))/O(nlog⁡2n)O(n\log n\alpha(n))/O(n\log^2n)，常数较小。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <bits/stdc++.h>

#define int int64_t

using i128 = __int128_t;
using pii = std::pair<int, int>;

namespace FASTIO {
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
inline void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::write;

const int kMaxN = 1e6 + 5;

int n, m; i128 ans;
int a[kMaxN];
pii arr[kMaxN];

struct DSU {
  i128 val; int fa[kMaxN], coef[kMaxN], sum[kMaxN];
  void init(int l, int r) {
    val = 0;
    for (int i = l; i <= r; ++i)
      fa[i] = i, coef[i] = sum[i] = 0;
  }
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  void unionn(int x, int y) { // 将 x 合并到 y 里面去
    int fx = find(x), fy = find(y);
    if (fx != fy) {
      fa[fx] = fy;
      val += (i128)(coef[fy] - coef[fx]) * sum[fx];
      sum[fy] += sum[fx];
    }
  }
  void setcoef(int x, int v) {
    x = find(x);
    val += (i128)(v - coef[x]) * sum[x], coef[x] = v;
  }
  void update(int x, int v) {
    x = find(x);
    val += (i128)coef[x] * v, sum[x] += v;
  }
} dsu1, dsu2;

void solve(int l, int r) {
  if (l == r) {
    ans += (m - a[l] + 1) * a[l], arr[l] = {a[l], l};
    return;
  }
  static pii tmparr[kMaxN];
  static int p[kMaxN], pre[kMaxN], nxt[kMaxN];
  int mid = (l + r) >> 1;
  solve(l, mid), solve(mid + 1, r);
  for (int p = l, p1 = l, p2 = mid + 1; p1 <= mid || p2 <= r;) {
    if (p1 <= mid && (p2 > r || arr[p1] <= arr[p2])) tmparr[p++] = arr[p1++];
    else tmparr[p++] = arr[p2++];
  }
  for (int i = l; i <= r; ++i) arr[i] = tmparr[i];
  for (int i = l; i <= mid; ++i) {
    p[i] = r + 1, pre[i] = l - 1;
  }
  for (int i = mid + 1; i <= r; ++i) {
    p[i] = l - 1, nxt[i] = r + 1;
  }
  dsu1.init(l, r), dsu2.init(l, r);
  for (int i = l; i <= mid; ++i) dsu1.setcoef(i, mid - i), dsu2.setcoef(i, r - mid);
  for (int i = mid + 1; i <= r; ++i) dsu2.setcoef(i, i - mid - 1), dsu1.setcoef(i, mid - l + 1);
  //
  std::vector<int> stk1, stk2; // 分别表示左区间目前的后缀最大值和右区间目前的前缀最大值
  std::vector<int> vec1, vec2; // 分别表示左右区间分别目前没有找到 x 的位置
  int sum1 = 0, sum2 = 0; // 表示目前左右区间分别目前没有找到 x 的位置的 b[i] * ((i - pre[i]) / (nxt[i] - i)) 的贡献和
  std::function<void(int)> insl = [&] (int x) {
    assert(l <= x && x <= mid);
    for (; stk1.size() && stk1.back() < x; stk1.pop_back()) {
      int y = stk1.back();
      dsu1.unionn(y, x), dsu2.update(y, -a[y] * (y - pre[y]));
      // if (p[y] == r + 1) {
      //   sum1 -= a[y] * (y - pre[y]);
      // } else {
      //   dsu2.update(y, -a[y] * (y - pre[y]));
      // }
    }
    if (stk1.size()) {
      int y = stk1.back();
      dsu2.update(y, a[y] * (y - x) - a[y] * (y - pre[y]));
      // if (p[y] == r + 1) sum1 += a[y] * (y - x) - a[y] * (y - pre[y]);
      // else dsu2.update(y, a[y] * (y - x) - a[y] * (y - pre[y]));
      pre[y] = x;
    }
    stk1.emplace_back(x);
    //
    for (auto y : vec2) {
      // sum2 -= a[y] * (nxt[y] - y);
      // dsu1.update(y, a[y] * (nxt[y] - y)), dsu1.unionn(y, x);
      dsu1.unionn(y, x);
      p[y] = x;
    }
    std::vector<int>().swap(vec2);
    // assert(!sum2);
    //
    // sum1 += a[x] * (x - pre[x]);
    dsu2.update(x, a[x] * (x - pre[x]));
    vec1.emplace_back(x);
  };
  std::function<void(int)> insr = [&] (int x) {
    assert(mid + 1 <= x && x <= r);
    for (; stk2.size() && stk2.back() > x; stk2.pop_back()) {
      int y = stk2.back();
      dsu2.unionn(y, x), dsu1.update(y, -a[y] * (nxt[y] - y));
      // if (p[y] == l - 1) {
      //   sum2 -= a[y] * (nxt[y] - y);
      // } else {
      //   dsu1.update(y, -a[y] * (nxt[y] - y));
      // }
    }
    if (stk2.size()) {
      int y = stk2.back();
      // if (p[y] == l - 1) sum2 += a[y] * (x - y) - a[y] * (nxt[y] - y);
      // else dsu2.update(y, a[y] * (x - y) - a[y] * (nxt[y] - y));
      dsu1.update(y, a[y] * (x - y) - a[y] * (nxt[y] - y));
      nxt[y] = x;
    }
    stk2.emplace_back(x);
    //
    for (auto y : vec1) {
      // sum1 -= a[y] * (y - pre[y]);
      // dsu2.update(y, a[y] * (y - pre[y])), dsu2.unionn(y, x);
      dsu2.unionn(y, x);
      p[y] = x;
    }
    std::vector<int>().swap(vec1);
    //
    // sum2 += a[x] * (nxt[x] - x);
    dsu1.update(x, a[x] * (nxt[x] - x));
    vec2.emplace_back(x);
  };
  for (int i = l; i <= r; ++i) {
    if (arr[i].second <= mid) insl(arr[i].second);
    else insr(arr[i].second);
    // ans += ((i == r ? (m + 1) : arr[i + 1].first) - arr[i].first) * (dsu1.val + dsu2.val + sum1 * (r - mid) + sum2 * (mid - l + 1));
    ans += (i128)((i == r ? (m + 1) : arr[i + 1].first) - arr[i].first) * (dsu1.val + dsu2.val);
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  solve(1, n);
  write(ans, '\n');
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
QOJ #9604. Cyberangel 题解
https://sobaliuziao.github.io/2025/04/16/post/3932e2d8.html
作者
Egg_laying_master
发布于
2025年4月16日
许可协议