CF243A The Brand New Function
题意翻译
题目大意
Polycarpus有一个由n个非负整数组成的序列
我们定义函数f(l,r)(1 \le l,r \le n)f(l,r)(1≤l,r≤n)，表示序列的子串[l,r]各项的“或”和:f(l,r)=a_l|a_{l+1}|⋯|a_rf(l,r)=a**l∣a**l+1∣⋯∣a**r
Polycarpus在纸上写下了所有的f(l,r)的值，他想知道他写下了多少个不同的值
输入
第一行1个整数n(1 \le n \le 10^5)n(1≤n≤105)，表示序列a的元素个数。
第二行nn个整数，表示序列各项元素a_i(0 \le a_i \le 10^6)a**i(0≤a**i≤106)。
输出
输出f(l,r)f(l,r)有多少个不同的值。
样例解释
第一个样例中：66个f(l,r)f(l,r)分别为：f(1,1)=1,f(1,2)=3,f(1,3)=3,f(2,2)=2,f(2,3)=2,f(3,3)=0f(1,1)=1,f(1,2)=3,f(1,3)=3,f(2,2)=2,f(2,3)=2,f(3,3)=0。有4种不同的值：00, 11, 22, 33.
题解：
一开始想维护一棵线段树+遍历线段树。
过了所有样例，但是假了，因为线段树维护的区间并不是全部区间，所以不能直接这么维护。
于是开始想推性质。思考每次转移会对答案造成何种影响。失败。
最后看题解之后发现可以直接暴力枚举+剪枝。
很容易发现，暴力是\(n^2\)的。但是可以剪枝。当一个数各位都是1的话，怎么或都没有用了，直接剪枝。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
int a[maxn],n;
set<int>s;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int x=a[i],y=0;
s.insert(x);
for(int j=i+1;j<=n;j++)
{
x|=a[j];
y|=a[j];
s.insert(x);
if(x==y)
break;
}
}
printf("%d\n",s.size());
return 0;
}