The Brand New Function CodeForces - 243A（二进制,st表,dp）

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”.

Input
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.

Output
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 %I64d specifier.

Examples
Input
3
1 2 0
Output
4
Input
10
1 2 3 4 5 6 1 2 9 10
Output
11
Note
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.

题意： 多少个子区间或起来不同

思路：
以前写复杂了，其实可以直接用dp写，定义$dp[i][j]$代表以$a[i]$为右端点时是否能得到或出$j$来。用$map$动态的维护$j$，那么状态转移就是 $dp[i+1][j|a[i]]=dp[i][j]$
因为我们可以确保dp[i].size() < 32（下面可以证明），那么复杂度就是$nlogn$.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
using namespace std;

typedef long long ll;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;

set<int>s,ans;
int a[maxn];

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        set<int>now;
        scanf("%d",&a[i]);
        for(auto it: s) {
            int s = it;
            ans.insert(s | a[i]);
            now.insert(s | a[i]);
        }
        now.insert(a[i]);
        ans.insert(a[i]);
        s.clear();
        s = now;
    }
    printf("%lldn",ans.size());
    return 0;
}

还有一种是st表写法
使用st表可以打出任意一个区间的异或值，使用pre数组记录了前i个数字第j个位为1时的最后一个位置。这样每次枚举i的时候，枚举终点为i的区间，我们只需要考虑每一位为1的部分就可以了（因为0不会影响或的结果），这样就把每一位上有1的部分的区间算进来了。

简单地说，固定好右端点（右端点一定取），找左端点组成一个区间。
比如只有一位的时候，那只有0，1。
当前位为1的时候，你不用找了，再怎么或都是1。
当前位为0的时候，找前i个数中最后一个1，或起来，也就是代码中的$pre[i][j]$

证明
对于a[k],假设有60位二进制，对于第i位，假设其为0，往前寻找找到第一个位置si,使得a[si]的第i位为1。
最后得到s1,s2,s3…sx，进行排序，此处我们假设其本来就是递减的。
则最后得到 [s1,k]的第1位二进制位为1，[s2,k]的第1位第2位二进制位为1，[s3,k]的第1,2,3位二进制位为1。。。
而对于[sx,k]，如果s2<sx<s1,则该值等于[s1,k]。
如果s3<sx<s2,则该值等于[s2,k]。

所以最后最多只有60个不同区间，只有60个值。

感觉太神奇了。
来源：https://www.cnblogs.com/zbtrs/p/7856772.html

ACNEW

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>

using namespace std;

const int maxn = 1e5 + 7;
set<int>s;
int a[maxn];
int f[maxn][30];
int pre[maxn][30];
int n;

void init() {
    for(int j = 1;j <= 20;j++) {
        for(int i = 1;i + (1 << (j - 1)) - 1 <= n;i++) {
            f[i][j] = f[i][j - 1] | f[i + (1 << (j - 1))][j - 1];
        }
    }
}

void query(int l,int r) {
    int k = (int)log2(r - l + 1);
    s.insert(f[l][k] | f[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
    }
    init();
    int mx = 0;
    for(int i = 1;i <= n;i++) {
        memcpy(pre[i],pre[i - 1],sizeof(pre[i - 1]));
        int tmp = a[i],cnt = 1;
        while(tmp) {
            if(tmp & 1) {
                pre[i][cnt] = i;
            }
            tmp >>= 1;
            cnt++;
        }
        mx = max(mx,cnt);
    }
    
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= mx;j++) {
            if(pre[i][j]) {
                query(pre[i][j],i);
            }
        }
        s.insert(a[i]);
    }
    printf("%dn",s.size());
    return 0;
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 7;

int a[maxn];
int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    
    set<int>s;
    for(int i = 1;i <= n;i++)
    {
        int t1 = a[i];
        int t2 = 0;
        s.insert(t1);
        for(int j = i + 1;j <= n;j++)
        {
            t1 |= a[j];
            t2 |= a[j];
            s.insert(t1);
            if(t1 == t2)break;
        }
    }
    
    printf("%lun",s.size());
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 7;
int a[maxn],f[maxn][30],pre[maxn][30],s[maxn],used[maxn],n,tot;

void init()
{
    for(int j = 1;j <= 20;j++)
    {
        for(int i = 1;i + (1 << (j - 1)) - 1 <= n;i++)
        {
            f[i][j] = f[i][j - 1] | f[i + (1 << (j - 1))][j - 1];
        }
    }
}

void query(int l,int r)
{
    int k = (int)log2(r - l + 1);
    s[++tot] = f[l][k] | f[r - (1 << k) + 1][k];
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
    }
    
    int mx = 0;
    init();
    for(int i = 1;i <= n;i++)
    {
        memcpy(pre[i],pre[i - 1],sizeof(pre[i - 1]));
        int tmp = a[i],cnt = 1;
        while(tmp)
        {
            if(tmp & 1)
                pre[i][cnt] = i;
            tmp >>= 1;
            cnt++;
        }
        mx = max(mx,cnt - 1);
    }
    
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= mx;j++)
        {
            if(pre[i][j])
            {
                if(used[pre[i][j]] != i)
                {
                    used[pre[i][j]] = i;
                    query(pre[i][j],i);
                }
            }
        }
        s[++tot] = a[i];
    }
    
    sort(s + 1,s + 1 + tot);
    int ans = (int)(unique(s + 1,s + 1 + tot) - s - 1);
    printf("%dn",ans);
    return 0;
}

最后

以上就是敏感方盒为你收集整理的The Brand New Function CodeForces - 243A（二进制,st表,dp）的全部内容，希望文章能够帮你解决The Brand New Function CodeForces - 243A（二进制,st表,dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。