求有多少区间并且区间里面所有数进行或运算的值小于m。首先知道或运算的性质，固定一个左端点，那么往右边进行或运算，那么这个值一定是不减的，那么这样就很明显了。首先预处理所有区间的进行或运算的值，这个直接用ST表即可，然后就在O（1）的时间内求出想要的结果。通过枚举左端点，然后二分查找的方法确定又断电，这样就可以得到结果了。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1e5+5; typedef long long LL; int dp[maxn][35]; int T, n, m; void ST_build(int n){ for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i+(1<<j)-1 <= n ; i++) dp[i][j] = dp[i][j-1]|dp[i+(1<<(j-1))][j-1]; } int query(int l, int r){ int cnt = log2(r-l+1), len = 1<<cnt; return dp[l][cnt]|dp[r-len+1][cnt]; } int main(){ scanf("%d", &T); for(int kase = 1; kase <= T; kase++){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &dp[i][0]); ST_build(n); LL ans = 0; for(int i = 1; i <= n; i++){ int l = i, r = n; while(l <= r){ int mid = (l+r)/2; if(query(i, mid) < m) l = mid+1; else r = mid-1; } ans += l-i; } printf("Case #%d: %I64d\n", kase, ans); } return 0; }