题目描述
http://codeforces.com/problemset/problem/875/D
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间满足区间或等于区间最大值
$n\le 2\times 10^5,a_i\le 10^9$
Solution
首先我们知道区间或是大于等于区间最大值的
然后我们考虑枚举作为区间最大值的点，那么我们用单调栈可以求出一个数左边和右边第一个大于它的数
然后我注意到当且仅当区间中存在一个值，它有一个 $1$ 是区间最大值所没有的
所以我们求一下每个数左边和右边第一个这样的值，然后就可以愉快的求答案了
时间复杂度 $O(n\log c)$
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
| #include <iostream>
#include <cstdio>
#define maxn 200010
#define INF 1000000001
#define ll long long
using namespace std;
const int N = 30;
int n, a[maxn];
int st[maxn], top, l[maxn], r[maxn], L[maxn], R[maxn], t[31];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i]; a[0] = a[n + 1] = INF;
st[top = 1] = 0;
for (int i = 1; i <= n + 1; ++i) {
while (top && a[st[top]] < a[i]) r[st[top--]] = i - 1;
l[i] = st[top] + 1; st[++top] = i;
}
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= N; ++j)
if (a[i] >> j & 1) t[j] = i;
else L[i] = max(L[i], t[j]);
fill(t, t + 31, n + 1); fill(R, R + maxn, n + 1);
for (int i = n; i; --i)
for (int j = 0; j <= N; ++j)
if (a[i] >> j & 1) t[j] = i;
else R[i] = min(R[i], t[j]);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
if (l[i] <= L[i])
ans += 1ll * (r[i] - i + 1) * (L[i] - l[i] + 1);
if (R[i] <= r[i])
ans += 1ll * (i - l[i] + 1) * (r[i] - R[i] + 1);
if (l[i] <= L[i] && R[i] <= r[i])
ans -= 1ll * (L[i] - l[i] + 1) * (r[i] - R[i] + 1);
}
cout << ans << "\n";
return 0;
}
|