CF1849E

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

令当前右端点为

i

，考虑从

i

到

i+1

有什么变化。手玩样例，我们发现每个位置

0

和

1

贡献的变更是与其左边最近的最大或最小值影响的，分别令它们为

mx_i

和

mn_i

。

具体地，由于给定的是排列，因此

mx_i

和

mn_i

必定有一个是

i-1

。考虑到

mx_i

或

mn_i

为

i-1

时，对总的贡献没有任何影响，我们进行如下的分类讨论：

$mx_i<i-1$ 。

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

$mn_i<i-1$ 。

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

上述这一过程可以使用线段树维护，

mn

和

mx

可以使用单调栈维护，最后答案就是

1

的个数。

时间复杂度

O(n \log n)

。

CPP

#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;
}

文章操作

相关推荐

评论

CF1849E