看到 \(\max, \min\) 考虑单调栈。枚举右端点，计算有多少个符合条件的左端点。
单调栈维护的是对于每个右端点，以每个点为左端点的后缀 \(\max, \min\) 形成的极长的段。先枚举 \(\text{popcount} = k\)，然后如果一个段的 \(\max\) 的 \(\text{popcount} = k\) 就在线段树上把这段区间 \(+1\)。\(\min\) 同理。那么查询就是查 \([1, n]\) 的 \(2\) 的个数。可以维护区间最大值个数解决。
时间复杂度 \(O(n (\log n + \log V))\)。但是因为 \(\log n\) 是线段树的 \(\log\) 所以要卡常才能通过。
code
// Problem: F. Interesting Sections
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1609/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline ll read() {
char c = getchar();
ll x = 0;
for (; !isdigit(c); c = getchar()) ;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x;
}
const int maxn = 1000100;
ll n, a[maxn];
struct node {
int mx, cnt, tag;
};
inline node operator + (const node &a, const node &b) {
node res;
res.mx = max(a.mx, b.mx);
res.cnt = (a.mx == res.mx ? a.cnt : 0) + (b.mx == res.mx ? b.cnt : 0);
res.tag = 0;
return res;
}
namespace SGT {
node a[maxn << 2];
inline void pushup(int x) {
a[x] = a[x << 1] + a[x << 1 | 1];
}
inline void pushdown(int x) {
if (!a[x].tag) {
return;
}
int &t = a[x].tag;
a[x << 1].mx += t;
a[x << 1].tag += t;
a[x << 1 | 1].mx += t;
a[x << 1 | 1].tag += t;
t = 0;
}
void build(int rt, int l, int r) {
a[rt].mx = a[rt].tag = 0;
a[rt].cnt = r - l + 1;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}
void update(int rt, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) {
a[rt].mx += x;
a[rt].tag += x;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
}
int stk1[maxn], top1, stk2[maxn], top2, hd[maxn], len, nxt[maxn << 2];
struct wwh {
int l, r, x;
wwh(int a = 0, int b = 0, int c = 0) : l(a), r(b), x(c) {}
} to[maxn << 2];
inline void add(int x, wwh y) {
to[++len] = y;
nxt[len] = hd[x];
hd[x] = len;
}
void solve() {
n = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
for (int i = 1; i <= n; ++i) {
vector<wwh> vc;
while (top1 && a[stk1[top1]] < a[i]) {
vc.pb(stk1[top1 - 1] + 1, stk1[top1], -__builtin_popcountll(a[stk1[top1]]) - 1);
--top1;
}
vc.pb(stk1[top1] + 1, i, __builtin_popcountll(a[i]) + 1);
stk1[++top1] = i;
while (top2 && a[stk2[top2]] > a[i]) {
vc.pb(stk2[top2 - 1] + 1, stk2[top2], -__builtin_popcountll(a[stk2[top2]]) - 1);
--top2;
}
vc.pb(stk2[top2] + 1, i, __builtin_popcountll(a[i]) + 1);
stk2[++top2] = i;
sort(vc.begin(), vc.end(), [&](const wwh &a, const wwh &b) {
return abs(a.x) > abs(b.x);
});
for (wwh u : vc) {
add(i, u);
}
}
ll ans = 0;
for (int j = 0; j < 60; ++j) {
SGT::build(1, 1, n);
for (int i = 1; i <= n; ++i) {
while (hd[i] && abs(to[hd[i]].x) == j + 1) {
wwh u = to[hd[i]];
hd[i] = nxt[hd[i]];
SGT::update(1, 1, n, u.l, u.r, u.x > 0 ? 1 : -1);
}
if (SGT::a[1].mx == 2) {
ans += SGT::a[1].cnt;
}
}
}
printf("%lld\n", ans);
}
int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}