题意:定义F(i,j)为数组a中从ai到aj的或运算,求使F(i,j)<m的对数。

思路:或运算具有单调性,也就是只增不减,如果某个时刻结果大于等于m了,那么再往后一定也大于等于m。所以可以用两个指针i,j来维护一段区间,同时开一个数组记录二进制每位上的1的个数(类似于前缀和),利用该数组可以得到区间或的值。一旦大于m则i前移。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long
#define len 31
using namespace std;
];
];
int n,m;
void add(int val)
{
    ; i<len; ++i)
        <<i))
            num[i]++;
}
void sub(int val)
{
    ; i<len; ++i)
        <<i))
            num[i]--;
}
int convers()
{
    ;
    ; i>=; --i)
        res=res*+(bool)num[i];
    return res;
}
int main()
{
    ;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(num,,sizeof(num));
        ; i<n; ++i)
            scanf("%d",&arr[i]);
        ll ans=;
        ,lst=,res=;
        while(lst<n)
        {
            if(arr[lst]>=m)
            {
                fst=++lst;
                memset(num,,sizeof*(num));
                continue;
            }
            add(arr[lst]);
            ans+=(lst-fst+);
            <n)&&(convers()|arr[lst+])>=m)))
            {
                ])>=m)
                    sub(arr[fst++]);
            }
            lst++;
        }
        printf("Case #%d: %I64d\n",++kase,ans);
    }
    ;
}

最新文章

  1. [LeetCode] Water and Jug Problem 水罐问题
  2. webstorm添加vue插件支持
  3. poj3295
  4. 解决Windows和Ubuntu时间不一致的问题
  5. MySQL数据库的登陆
  6. CQRS学习——Storage实现(EF+Code First+DynamicReponsitory)[其四]
  7. 在ec2上创建root用户,并使用root 通过Xshell远程登录aws云服务器
  8. SQL Server索引进阶:第五级,包含列
  9. BST(Binary Search Tree)
  10. layer属性
  11. angular高级篇之transclude使用详解
  12. Mac通过brew安装reds、memcached
  13. Linux记录~持续更新~
  14. 我要曝光!CDN 省钱大法!
  15. springMVC使用HandlerMethodArgumentResolver 自定义解析器实现请求参数绑定方法参数
  16. Unity设置播放模式下始终先执行指定的场景
  17. Python基础(五) python装饰器使用
  18. Vijos1605 NOIP2008 提高组T4 双栈排序 BFS
  19. compile FFMPEG under windows
  20. 对&quot;某V皮&quot;N服务器节点的一次后渗透测试

热门文章

  1. linux笔记:linux系统安装-linux系统安装
  2. python 练习 3
  3. python中range和xrange的区别
  4. Roman to Integer [LeetCode]
  5. 一个.net mvc的例子
  6. 选择列表中的列无效,因为该列没有包含在聚合函数或 GROUP BY 子句中
  7. Linux Bash代码 利用for循环实现命令的多次执行
  8. JMETER JDBC操作
  9. VS2005保存文件很慢
  10. linux 磁盘管理以及维护