$Or三元组$Or三元组

$正解部分$正解部分

$\mathrm{\"}前言\mathrm{\"}:$"前言": 若处理出 $sum[i,j]$sum[i,j] 表示前 $i$i 个数字 $j$j 出现的次数,
预处理时空复杂度为 $O(N\ast 255)$O(N∗255), 单次查询时间复杂度 $O(255\ast 255)$O(255∗255), 显然不能过.

记录 $sum[i,j]$sum[i,j] 为前 $i$i 个数 $orj=j$or j=j 的数字数量,
设 $cn{t}_x=sum[r,x]-sum[l-1,x]$cntx​=sum[r,x]−sum[l−1,x], 则 $cn{t}_x$cntx​ 个数中 $3$3个 或 起来并不一定等于 $x$x, 可能小于 $x$x,
考虑怎么 得到或起来等于 $x$x 的三元组 个数, 可以使用 容斥,
Ans=Ccntx​3​−Ccnta1​​3​−Ccnta2​​3​⋯+⋯−⋯⋯

在 $orx=x$or x=x 的数中 与 $x$x 二进制相差奇数个 $1$1 的数 容斥系数为 $-1$−1, 否则为 $1$1.

由于每次容斥最多调用 $255$255 个数字, 所以单次查询复杂度为 $O\left(255\right)$O(255) .

$实现部分$实现部分

注意不能写成下面这个代码, 因为这样会计算重复 .

#include<bits/stdc++.h>
#define reg register

const int maxn = 1e5 + 5;

int N;
int M;
int Ans;
int A[maxn];
int pw[20];
int sum[maxn][257];

void DFS(int opt, int x, int r, int l){
        int cur_cnt = sum[r][x] - sum[l-1][x];
        if(opt & 1) Ans += (cur_cnt>=3)*cur_cnt*(cur_cnt-1)*(cur_cnt-2)/6;
        else Ans -= (cur_cnt>=3)*cur_cnt*(cur_cnt-1)*(cur_cnt-2)/6;
        for(reg int i = 0; pw[i] <= x; i ++)
                if(pw[i] & x) DFS(opt^1, x^pw[i], r, l);
}

int main(){
        scanf("%d%d", &N, &M);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]); 
        pw[0] = 1;
        for(reg int i = 1; i <= 10; i ++) pw[i] = pw[i-1] << 1;
        for(reg int j = 1; j <= 255; j ++)
                for(reg int i = 1; i <= N; i ++) sum[i][j] = sum[i-1][j] + ((A[i]|j) == j);
        for(reg int i = 1; i <= M; i ++){
                int l, r, x;
                scanf("%d%d%d", &l, &r, &x);
                Ans = 0;
                DFS(1, x, r, l);
                printf("%d\n", Ans);
        }
        return 0;
}

这个是对的 .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e5 + 5;

int N;
int M;
int cnt_1;
int A[maxn];
int pw[20];
int tmp_1[20];
int sum[maxn][257];

ll Ans;

void DFS(int opt, int x, int cur, int r, int l){
	if(x == cnt_1 + 1){
	     int cur_cnt = sum[r][cur] - sum[l-1][cur];
	     if(opt & 1) Ans += 1ll*(cur_cnt>=3)*cur_cnt*(cur_cnt-1)*(cur_cnt-2)/6;
	     else Ans -= 1ll*(cur_cnt>=3)*cur_cnt*(cur_cnt-1)*(cur_cnt-2)/6;
	     return ;
	}
        DFS(opt, x + 1, cur, r, l);
        DFS(opt^1, x + 1, cur^tmp_1[x], r, l);
}

int main(){
        freopen("Or.in", "r", stdin);
        freopen("Or.out", "w", stdout);
        scanf("%d%d", &N, &M);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]); 
        pw[0] = 1;
        for(reg int i = 1; i <= 10; i ++) pw[i] = pw[i-1] << 1;
        for(reg int j = 1; j <= 255; j ++)
                for(reg int i = 1; i <= N; i ++) sum[i][j] = sum[i-1][j] + ((A[i]|j) == j);
        for(reg int i = 1; i <= M; i ++){
                int l, r, x;
                scanf("%d%d%d", &l, &r, &x);
                Ans = 0;
                cnt_1 = 0;
                for(reg int j = 0; j <= 10; j ++)
                	if(pw[j] & x) tmp_1[++ cnt_1] = pw[j];
                DFS(1, 1, x, r, l);
                printf("%lld\n", Ans);
        }
        return 0;
}