I love counting

HDU6964

题目描述

给出\(n\)个数的序列，每个位置都有一个权值\(c\)，进行 \(Q\) 次询问，每次询问给定一个区间 \([l,r]\) 和两个数字 \(a,b\)，问这个序列有多少种权值 \(c\)满足 \(c ^ a <= b\)。

解题思路

莫队+分块
莫队参考 : 莫队详解 - JSOI爆零珂学家yzhang - 博客园 (cnblogs.com)
仅考虑第 \(j\)位，

\(b\)为1，\(a\)为1，那么 \(c\)为1可满足 \(c ^ a < b\)
\(b\)为1，\(a\)为1，那么 \(c\)为0可满足 \(c ^ a < b\)
\(b\)为0，\(a\)为1，那么 \(c\)只能为1才可满足 \(c ^ a <= b\)
\(b\)为0，\(a\)为0，那么 \(c\)只能为0才可满足 \(c ^ a <= b\)

所以对于前两种情况，我们直接暴力计算其对答案的贡献即可。
即：从高位往低位遍历，当第 \(j\)位出现前两种情况时，直接利用分块+前缀和 计算出当前数对答案的贡献即可。

Code

#include <bits/stdc++.h>
#define qc ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define PII pair<int, int>
#define pb push_back
using namespace std;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct query{
	int l,r,id,bl;
	int a,b;
}q[N];
int sum[N]; //记录每个分块有多少种c
int ans[N]; 
int cnt[N]; //记录c有多少个
int c[2*N]; //c[i] 表示每个i这个数的种数
int v[N];
int k;    //记录分块大小
void add(int x)
{
	if(++cnt[x] == 1)
	{
		sum[x / k] ++;
		c[x] ++;
	}
}
void del(int x)
{
	if(--cnt[x] == 0)
	{
		sum[x / k] --;
		c[x] --;
	}
}
bool cmp(query a,query b)
{
	if(a.bl != b.bl)return a.bl < b.bl;
	else return a.r < b.r;
}
int ask(int x){ //计算前缀和，即到第x位
	int res = 0;
	for (int i = x / k * k; i <= x; i++)res += c[i];
	for (int i = 0; i < x / k; i++)res += sum[i];
	return res;
}
void solve(){
	int n,m;
	cin >> n;
	k = sqrt(n+1);
	for(int i = 1; i <= n; ++i)
		cin >> v[i];
	cin >> m;
	for(int i = 1; i <= m; ++i){
		cin >> q[i].l >> q[i].r >> q[i].a >> q[i].b;
		q[i].bl = (q[i].l - 1) / k + 1;
		q[i].id = i;
	}
	sort(q+1,q+1+m,cmp);
	int l = 1, r = 0;
	for(int i = 1; i <= m; ++i){
		int ll = q[i].l, rr = q[i].r;
		while(l < ll)
			del(v[l++]);
		while(l > ll)
			add(v[--l]);
		while(r < rr)
			add(v[++r]);
		while(r > rr)
			del(v[r--]);
		int s = 0;
		int a = q[i].a, b = q[i].b;
		for(int j = 19; j > -1; --j){
			if((b >> j) & 1){
				int p = s;
				if((a >> j) & 1)
					p |= 1 << j;
				else 
					s |= 1 << j;
				ans[q[i].id] += ask(p + (1 << j) - 1) - ask(p - 1);
			}
			else 
				if((a >> j) & 1)s |= 1 << j;
		}
		ans[q[i].id] += c[q[i].a ^ q[i].b];
	}
	for(int i = 1; i <= m; i++)
		cout << ans[i] << "\n";
}

int main()
{
	#ifdef ONLINE_JUDGE
	#else
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif

	qc;
	int T;
    //cin >> T;
	 T = 1;
	 while(T--){
	 	solve();
	}
	return 0;
}