[luogu] CF243A The Brand New Function 或二进制,剪枝暴力

前言

传送门:

思路

题意 : 给你一个数组,询问有多少个区间[l,r]或出来的值,不同于给的值

本来看上区间问题就没想到使用暴力的,而是想到了线性基

但是没想到还是可以使用暴力过的

而且我们可以使用 a [ j ] ∣ a [ i ] = a [ j ] a[j]|a[i] = a[j] a[j]∣a[i]=a[j] 剪枝

这样子在我们倒序枚举 j j j的时候,如果出现了这个既能保证不出现又可以保证…

Mycode

'const int N  = 1e6+10;
int a[N];


void solve()
{
	int n;cin>>n;
	
	int cnt = 0 ;
	for(int i = 1;i>a[i];
		if(!st[a[i]]){
			++cnt;
			st[a[i]] = 1;
		}
	}
	
	for(int i=1;i= 1; j -- ){
			if(a[j] == (a[j]|a[i])) break;
			
			a[j] |= a[i];
			
			if(!st[a[j]]){
				++cnt;
				st[a[j]] = 1;
			}
		}
	}
	
	cout