若处理出 表示前 个数字 出现的次数,
预处理时空复杂度为 , 单次查询时间复杂度, 显然不能过.
记录 为前 个数 的数字数量,
设 , 则 个数中个 或 起来并不一定等于 , 可能小于 ,
考虑怎么 得到或起来等于 的三元组 个数, 可以使用 容斥,
在 的数中 与 二进制相差奇数个 的数 容斥系数为 , 否则为 .
由于每次容斥最多调用 个数字, 所以单次查询复杂度为 .
注意不能写成下面这个代码, 因为这样会计算重复 .
#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
", 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
", Ans);
}
return 0;
}