题解:
把思路转换成总-非法方案数。
对于第i个点来说 找到L[i], R[i] 然后 对于所有的在[ L[i], R[i] ] 的值都 < a[i],
然后对于第i个点来说 在 [L[i], i]这段区间中找到最大的x使得 a[x] | a[x+1] | … | a[i] > a[i]
同样在[i, R[i]]这段区间中找到最小的y使得 a[i] | a[i + 1] | a[i + 2] | … | a[ x] > a[i]
那么对于[x+1, y – 1]这段区间都是非法的区间。
然后总答案 – 非法方案数。
这样处理完之后,我们会发现样例二过不去 Orz,,,
因为有相同数的时候,我们这个区间没有考虑过。
所以我们定义在L[i] 和 i 之间的数是 <= a[i]的
i 到 R[i]的数是 < a[i]的
这样就可以使得每个区间只访问到一次。
然后继续做上诉操作。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
int a[N];
int l[N], r[N];
int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
a[] = a[n+] = inf;
for(int i = ; i <= n; ++i){
l[i] = i - ;
while((a[l[i]] | a[i]) == a[i]) l[i] = l[l[i]];
}
for(int i = n; i >= ; --i){
r[i] = i + ;
while((a[r[i]]|a[i]) == a[i] && a[i] != a[r[i]]) r[i] = r[r[i]];
}
LL ans = n * (n + 1ll) / ;
for(int i = ; i <= n; ++i){
ans -= (1ll*i-l[i]) * (r[i]-i);
}
cout << ans << endl;
return ;
}