给定长度为(n,nleq 10^5)的序列(a,a_i,mleq 255)，多组询问求

---

分析

直接求显然不行，考虑容斥，
设(s[i][j])表示前(i)个数中有多少个数与(j)按位或为(j)
那么答案就是

---

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long lll;
const int N=100011,M=256;
int n,Q,s[N][M],a[N],xo[M];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(lll ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
inline lll C(int n){return 1ll*n*(n-1)/2*(n-2)/3;}
signed main(){
	n=iut(); Q=iut();
	for (rr int i=1;i<=n;++i){
	    a[i]=iut();
	    for (rr int j=0;j<M;++j)
	        s[i][j]=s[i-1][j]+((j&a[i])==a[i]);
	}
	for (rr int i=1;i<M;++i) xo[i]=xo[i&(i-1)]+1;
	for (rr int i=1;i<=Q;++i){
		rr int l=iut(),r=iut(),x=iut();
		rr lll ans=0;
		for (rr int j=x;j;j=(j-1)&x)
		if (xo[x^j]&1) ans-=C(s[r][j]-s[l-1][j]);
		    else ans+=C(s[r][j]-s[l-1][j]);
		print(ans),putchar(10);
	}
	return 0;
}