CF876 F 思维枚举

给你n个数，问有几个区间满足，区间内或操作大于区间内的任意数。

首先可以知道，两数或操作的结果必定不会小于两者间的最大值，也就是说对于一个区间中，不合法的状态只有两值或相等。那么我们可以考虑枚举每个数，向左向右找到第一个或不相等的，那么该数对所有不合法区间的贡献就能找到了，所以与其找合法的区间不如容斥找不合法的区间。

具体从左往右枚举每个数，同时记录该数某二进制位为0时，左侧数中该位出现1的离i的最近位置，得到左边界。右边界类似。

然后就是要注意重复的数，重复的数出现直接就使区间不合法，左右两侧收缩边界时只要有一侧考虑重复数即可。

/** @Date    : 2017-10-16 23:43:44

  * @FileName: F.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 2e5+20;

const double eps = 1e-8;

int a[N];

LL l[N];

LL r[N];

LL t[N];

map<int, int>q;

int main()

{

	LL n;

	cin >> n;

	for(int i = 1; i <= n; i++)

		scanf("%d", a + i);

	LL ans = 0;

	for(int i = 1; i <= n; i++)

	{

		l[i] = q[a[i]];//标记重复数位置，重复数必定使区间不合法

		for(int j = 0; j < 31; j++)

		{

			if((a[i] & (1LL << j)))

				t[j] = i;

			else l[i] = max(l[i], t[j]);

		}

		q[a[i]] = i;

	}

	for(int i = 0; i < 31; i++)

		t[i] = n + 1;

	for(int i = n; i >= 0; i--)

	{

		r[i] = n + 1;

		for(int j = 0; j < 31; j++)

		{

			if((a[i] & (1LL << j)))

				t[j] = i;

			else r[i] = min(r[i], t[j]);

		}

	}

	for(int i = 1; i <= n; i++)

	{

		//cout << l[i] <<"~"<< i << "~"<< r[i] << endl;

		ans -= (i - l[i]) * (r[i] - i);

	}

	ans += n * (n + 1LL) / 2LL;

	printf("%lld\n", ans);

    return 0;

}

巴特西

CF876 F 思维枚举

最新文章

热门文章

巴特西

CF876 F 思维 枚举

最新文章

热门文章

CF876 F 思维枚举