【CodeForces 243A】 The Brand New Function

题目大意

给出一个序列 $a$，设 $f(l,r)$ 表示 $a_l|a_{l+1}|a_{l+2}|\cdots|a_r$，求 $f(l,r)$ 有多少不同的值。

思路

显然，对于任意 $l$，$f(l,r)\le f(l,r+1)$，也就是说，对于从同一个数开始的所有区间，它们的值一定是随长度增加而增加的，所以，我们假设有一个变量 $t$，它从 $a_l$ 开始不停地与下一个数相或，这个 $t$ 的值增加的次数就是所有以 $a_l$ 为左端点的区间中不同的 $f(l,r)$ 的值的数量，因为 $t$ 只会增大，不会变小。

那么我们怎么知道这个 $t$ 变大了多少次呢？考虑 $t$ 在什么情况下会变大，显然，$t$ 会变大，当且仅当原来 $t$ 为 $0$ 的位变成了 $1$，而且每一位最多会变一次，所以，我们维护一个 $nxt$ 数组，用 $nxt_{i,j}$ 表示 $a_i$ 到 $a_n$ 这些数中第 $j$ 位为 $1$ 的第一个数的下标，由于有些位可能同时变成 $1$，所以我们还需要对下标进行去重。

最终时间复杂度 $O(n\log M)$，常数稍大。

参考代码

对于 $nxt$ 数组，这里采用的是滚动数组的方法，减小了一点空间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
struct QwQ
{
	int val;
	int id;
	bool operator < (const QwQ &a) const
	{
		return val == a.val ? id < a.id : val < a.val;
	}
};
QwQ t[30];
int n, mx, a[N], b[N*15], nxt[30];
ll ans;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for(int i = n; i >= 1; i--)
	{
		int x = a[i];
		for(int j = 0; j <= 20; j++)
		{
			t[j] = (QwQ){nxt[j], j};
			if((a[i]>>j)&1)
				nxt[j] = i;
		}
		sort(t, t+21);//排个序方便去重
		for(int j = 0; j <= 20; j++)
			if(t[j].val)
			{
				if(!b[x] && (j == 0 || t[j].val != t[j-1].val))
				{
					ans++;
					b[x] = 1;
				}
				x |= (1<<t[j].id);
			}
		if(!b[x])//上面那样循环会漏掉最后一个，得额外加上。
		{
			ans++;
			b[x] = 1;
		}
	}
	printf("%lld", ans);
	return 0;
}