noip模拟41-三题未改

  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

#include <bits/stdc++.h>
#define For(i, l, r) for (int_fast64_t i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int_fast64_t i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int_fast64_t maxn = 5000010;

namespace IO {
  const int_fast32_t MAXSIZE = 1 << 20;
  char buf[MAXSIZE], *p1, *p2;
#define gc()                                                            \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
   ? EOF                                                                \
   : *p1++)
  template<typename type>
  inline type read() {
    type x = 0, f = 1;
    char c = gc();
    while (!isdigit(c)) {
      if (c == '-') f = -1;
      c = gc();
    }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
    return x * f;
  }
  char pbuf[1 << 20], *pp = pbuf;
  inline void push(const char &c) {
    if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
    *pp++ = c;
  }
  inline void write(int_fast32_t x) {
    static int_fast32_t sta[35];
    int_fast32_t top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }
}  // namespace IO
using namespace IO;

int_fast32_t h[maxn], ch[maxn];
bool llgr[maxn], rlgr[maxn];
int_fast32_t stk[maxn];
int_fast32_t cnt[maxn];
int_fast32_t maxx, maxxp;
int_fast32_t n;

int main() {
  n = read<int_fast32_t>();
  For(i, 1, n) {
    h[i] = read<int_fast32_t>();
    if (h[i] > maxx) {
      maxx = h[i];
      maxxp = i;
    }
  }
  For(i, maxxp, n) {
    ch[++ch[0]] = h[i];
  }
  For(i, 1, maxxp - 1) {
    ch[++ch[0]] = h[i];
  } // 断环
  int_fast32_t maxx = 0;
  For(i, 2, n) {
    if (ch[i] >= maxx) {
      maxx = ch[i];
      llgr[i] = 1; // 从左向右这个数比之前的大
                   // 下面同理
    }
  }
  maxx = 0;
  Fordown(i, n, 1) {
    if (ch[i] >= maxx) {
      maxx = ch[i];
      rlgr[i] = 1;
    }
  }
  int_fast64_t ans = 0;
  int_fast32_t top = 0;

  stk[++top] = ch[1];
  cnt[top] = 1; // 统计个数，去重
  For(i, 2, n) {
    while (top && stk[top] < ch[i]) {
      ans += cnt[top];
      top--;
    }
    if (ch[i] == stk[top]) {
      ans += cnt[top];
      cnt[top]++;
      if (top >= 2)
        ans++;
      continue;
    }
    if (top)
      ans++;
    stk[++top] = ch[i];
    cnt[top] = 1;
  }
  For(i, 2, n) {
    if (!llgr[i] && rlgr[i])
      ans++;
  }
  cout << ans << endl;
  return 0;
}