Codeforces243A The Brand New Function
2 seconds
256 megabytes
standard input
standard output
Polycarpus has a sequence, consisting of n non-negative integers: a1, a2, ..., an.
Let's define function f(l, r) (l, r are integer, 1 ≤ l ≤ r ≤ n) for sequence a as an operation of bitwise OR of all the sequence elements with indexes from l to r. Formally: f(l, r) = al | al + 1 | ... | ar.
Polycarpus took a piece of paper and wrote out the values of function f(l, r) for all l, r (l, r are integer, 1 ≤ l ≤ r ≤ n). Now he wants to know, how many distinct values he's got in the end.
Help Polycarpus, count the number of distinct values of function f(l, r) for the given sequence a.
Expression x | y means applying the operation of bitwise OR to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "|", in Pascal — as "or".
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of sequence a. The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 106) — the elements of sequence a.
Print a single integer — the number of distinct values of function f(l, r) for the given sequence a.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64dspecifier.
3
1 2 0
4
10
1 2 3 4 5 6 1 2 9 10
11
In the first test case Polycarpus will have 6 numbers written on the paper: f(1, 1) = 1, f(1, 2) = 3, f(1, 3) = 3, f(2, 2) = 2, f(2, 3) = 2, f(3, 3) = 0. There are exactly 4 distinct numbers among them: 0, 1, 2, 3.
大致题意:给定一个长度为n的区间,问有多少个子区间或起来的值不相同.
分析:非常好的一道题.为了实现O(1)查询,可以先用一个ST表处理出所有区间或起来的值.然后就可以O(n^2)的做了.
有关二进制的题一个常见的优化就是分位处理.在枚举区间的时候,先固定右端点,向左延伸确定左端点,考虑二进制下的第j位,记pre[i][j]表示在第i个数前二进制下第j位为1的最右边的数的位置.这个可以在读入的时候预处理出来.根据处理出来的这个pre数组,就能够不用一维一维地枚举左端点,而是可以“跳”.将所有跳到的点l标记一下,那么[l,i]的或值就要被考虑,放到数组里.最后排序去重就可以了.
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, a[], pre[][], ans, use[], maxn;
int st[][], s[], tot, T;
bool flag = false; void init()
{
for (int j = ; j <= ; j++)
for (int i = ; i + ( << j) - <= n; i++)
st[i][j] = st[i][j - ] | st[i + ( << (j - ))][j - ];
} void col(int l, int r)
{
int k = (int)((log(r - l + )) / log(2.0));
s[++tot] = st[l][k] | st[r - ( << k) + ][k];
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] == )
flag = true;
st[i][] = a[i];
}
init();
for (int i = ; i <= n; i++)
{
memcpy(pre[i], pre[i - ], sizeof(pre[i - ]));
int x = a[i], cnt = ;
while (x)
{
if (x % == )
pre[i][cnt] = i;
x /= ;
cnt++;
}
cnt--;
maxn = max(maxn, cnt);
}
for (int i = ; i <= n; i++)
{
T++;
for (int j = ; j <= maxn; j++)
{
if (pre[i][j])
{
if (use[pre[i][j]] != T) //时间戳
{
use[pre[i][j]] = T;
col(pre[i][j], i);
}
}
}
s[++tot] = a[i];
}
sort(s + , s + tot + );
ans = unique(s + , s + + tot) - s - ;
printf("%d\n", ans); return ;
}
最新文章
- Android----消息弹出框
- C#之方法的声明与调用
- django(五)
- POJ 1151 Atlantis 线段树求矩形面积并 方法详解
- 在ios中解析json数据
- PyQt4--QPushButton阵列
- ajax验证码检测
- Flex自定义组件开发之日周月日期选择日历控件
- (转)hibernateTools工具安装及使用总结(eclipse 3.6)
- sort和uniq去重操作【转】
- 【CV】CVPR2015_A Discriminative CNN Video Representation for Event Detection
- Ajax进阶 FormData对象
- HBase Filter
- Hbase数据读写流程
- 用JAVA实现大文件上传及显示进度信息
- 七牛云A账号数据迁移到B账号下
- Linux命令详解-用户管理
- leetcode 刷题
- Java导出引用jar包的文件
- AVAudioFoundation(1):使用 AVAsset
热门文章
- adb shell top 命令详解
- Hyperledger Fabric 1.0 从零开始(十三)——orderer分布式方案
- Pycharm 2018.2.1-2018.1
- 笔试题——C++字符排序
- linux下搭建python机器学习环境
- Variable() placeholder() constant() 的区别
- Python基础知识-05-数据类型总结字典
- Live Archive 训练题
- Thunder团队第七周 - Scrum会议1
- 团队项目NABCD