\(Solution\)
考虑\(a[i]\)互不相同的情况。
对于\([L,R]\)区间,当\(mx-mi=R-L\)的时候才满足条件。
且此时有个恒等式:\(mx-mi>=R-L\),变化得\(mx-mi+L>=R\)。
我们在线段树的每一位存当前位置\(mx-mi+x\)的值。
我们可以从小到大枚举\(R\),然后对于\(mx\)和\(mi\)的更新直接在线段树上区间修改。
对于查找答案的话,由于恒等式,我们只需要存储值的最小值及其个数即可。
然后考虑\(100\)分(\(a[i]\)可能相同)的情况。
这样的话,设\(cnt\)表示\([L,R]\)区间内相同数值的个数,当\(mx-mi+cnt=R-L\)的时候才满足条件。
且此时又有一个恒等式:\(mx-mi+cnt>=R-L\),变化得\(mx-mi+cnt+L>=R\)。
对于\(cnt\),我们预处理上一个和\(a[i]\)相同的位置\(k\),这样\([1,k]\)加\(1\)即可。
其他和前一种情况类似即可。
#include <cstdio>
#include <algorithm>
#define N 100010
#define ll long long
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
using namespace std;
struct node{int v, fr;}b[N];
int n, a[N], las[N];
int bg_z[N], top1 = 0, sm_z[N], top2 = 0;
ll mi[N << 2], cnt[N << 2], lazy[N << 2];
ll ans = 0;
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
inline bool cmp(node x, node y) {return x.v == y.v ? x.fr < y.fr : x.v < y.v;}
void prepare() {
fo(i, 1, n) b[i] = (node){a[i], i};
sort(b + 1, b + n + 1, cmp);
fo(i, 2, n) if (b[i].v == b[i - 1].v)
las[b[i].fr] = b[i - 1].fr;
}
void back_(int x) {
if (mi[ls] < mi[rs]) mi[x] = mi[ls], cnt[x] = cnt[ls];
else if (mi[ls] > mi[rs]) mi[x] = mi[rs], cnt[x] = cnt[rs];
else mi[x] = mi[ls], cnt[x] = cnt[ls] + cnt[rs];
}
void update(int x, int l, int r) {
mi[ls] += lazy[x], lazy[ls] += lazy[x];
mi[rs] += lazy[x], lazy[rs] += lazy[x];
lazy[x] = 0;
}
void insert(int x, int l, int r, int f, int val) {
if (l < r && lazy[x]) update(x, l, r);
if (l == r) {mi[x] = val, cnt[x] = 1; return;}
int mid = (l + r) >> 1;
if (f <= mid) insert(ls, l, mid, f, val);
else insert(rs, mid + 1, r, f, val);
back_(x);
}
void modify(int x, int l, int r, int fl, int fr, int val) {
if (l < r && lazy[x]) update(x, l, r);
if (fl <= l && r <= fr) {mi[x] += val, lazy[x] += val; return;}
int mid = (l + r) >> 1;
if (fl <= mid) modify(ls, l, mid, fl, fr, val);
if (fr > mid) modify(rs, mid + 1, r, fl, fr, val);
back_(x);
}
ll query(int x, int l, int r, int fl, int fr, int val) {
if (l < r && lazy[x]) update(x, l, r);
if (fl <= l && r <= fr) {
if (mi[x] == val) return cnt[x];
return 0;
}
int mid = (l + r) >> 1; ll s = 0;
if (fl <= mid) s += query(ls, l, mid, fl, fr, val);
if (fr > mid) s += query(rs, mid + 1, r, fl, fr, val);
return s;
}
int main()
{
freopen("easy.in", "r", stdin);
freopen("easy.out", "w", stdout);
n = read(); ans = 1;
fo(i, 1, n) a[i] = read();
prepare();
bg_z[top1 = 1] = sm_z[top2 = 1] = 1;
insert(1, 1, n, 1, 1);
fo(i, 2, n) {
insert(1, 1, n, i, i);
while (top1 && a[bg_z[top1]] < a[i])
modify(1, 1, n, bg_z[top1 - 1] + 1, bg_z[top1], a[i] - a[bg_z[top1]]), top1--;
bg_z[++top1] = i;
while (top2 && a[sm_z[top2]] > a[i])
modify(1, 1, n, sm_z[top2 - 1] + 1, sm_z[top2], a[sm_z[top2]] - a[i]), top2--;
sm_z[++top2] = i;
if (las[i] > 0) modify(1, 1, n, 1, las[i], 1);
ans = ans + query(1, 1, n, 1, i, i);
}
printf("%lld\n", ans);
return 0;
}