CF1849E

PikachuQAQ · 2025-08-26 08:28:36 · 题解

统计数对，可以考虑枚举右端点统计最短点，或分治统计，这里选择了枚举右端点。

令当前右端点为 i，考虑从 i 到 i+1 有什么变化。手玩样例，我们发现每个位置 0 和 1 贡献的变更是与其左边最近的最大或最小值影响的，分别令它们为 mx_i 和 mn_i。

具体地，由于给定的是排列，因此 mx_i 和 mn_i 必定有一个是 i-1。考虑到 mx_i 或 mn_i 为 i-1 时，对总的贡献没有任何影响，我们进行如下的分类讨论：

• 考虑到 mx_i 的定义，且因为给定了排列，a_{mx_{i+1}}\sim a_{i-1} 一定小于 a_i，那么这些就会作为新增的左端点，把这一段的贡献变成 1。

• 同理地，a_{mn_{i+1}}\sim a_{i-1} 一定大于 a_i，这些点一定不会成为新的左端点，把这一段的贡献变成 0。

上述这一过程可以使用线段树维护，mn 和 mx 可以使用单调栈维护，最后答案就是 1 的个数。

时间复杂度 O(n \log n)。

#include <bits/stdc++.h>
#define int long long
#define ls (p << 1)
#define rs ((p << 1) | 1)

using namespace std;

const int kN = 1e6 + 7;

int n, a[kN], stk[kN], top, mx[kN], mn[kN], ans;
int seg[kN << 2], tag[kN << 2];

void pushup(int p) {
  seg[p] = seg[ls] + seg[rs];
}

void addtag(int l, int r, int p, int d) {
  seg[p] = (r - l + 1) * d, tag[p] = d;
}

void pushdown(int l, int r, int p) {
  if (tag[p] == -1) return;
  int mid = (l + r) >> 1;
  addtag(l, mid, ls, tag[p]), addtag(mid + 1, r, rs, tag[p]);
  tag[p] = -1;
}

void Build(int l = 1, int r = n, int p = 1) {
  if (l == r) return (void)(tag[p] = -1);
  int mid = (l + r) >> 1;
  Build(l, mid, ls), Build(mid + 1, r, rs), pushup(p);
}

void Update(int s, int t, int d, int l = 1, int r = n, int p = 1) {
  if (s <= l && r <= t) return addtag(l, r, p, d);
  int mid = (l + r) >> 1;
  pushdown(l, r, p);
  if (s <= mid) Update(s, t, d, l, mid, ls);
  if (mid + 1 <= t) Update(s, t, d, mid + 1, r, rs);
  pushup(p);
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  Build();
  for (int i = 1; i <= n; i++) {
    while (top && a[stk[top]] < a[i]) top--;
    mx[i] = stk[top], stk[++top] = i;
  }
  top = 0;
  for (int i = 1; i <= n; i++) {
    while (top && a[stk[top]] > a[i]) top--;
    mn[i] = stk[top], stk[++top] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (mn[i] < i - 1) Update(mn[i] + 1, i - 1, 0);
    if (mx[i] < i - 1) Update(mx[i] + 1, i - 1, 1);
    ans += seg[1];
  }
  cout << ans;

  return 0;
}