LuoguP4887 第十四分块(前体)题解/莫队二次离线学习笔记

题目大意:

给定一个序列a,每次询问给定l,r,求ai xor aj在二进制下有k个1的对数.

题解:

设数字x在二进制下有k个1.则若ai xor aj = x时,由异或性质可得ai xor x = aj.
考虑莫队,设区间内数字x的出现次数为cnt[x],二进制下有k个1数字集合为α,则当向区间内加入一个数字y时,答案会加上:

    \[\Delta ans(y,[l,r])=\sum_{x\in \alpha }^{} cnt_{y\ xor\ x}\]

这个转移不是O(1),不太行.

以左端点右移为例,需要知道a[l]关于[l+1,r]区间的答案并将它减去.为了描述方便,我们将数字x关于区间[l,r]的答案设为Δans(x,[l,r]).

不难发现:

    \[\Delta ans(x,[l,r])=\Delta ans(x,[1,r])-\Delta ans(x,[l-1])\]

关于后半部分,我们可以预处理出来.关于前面部分,我们可以把它离线出来一起求出.

LuoguP4887 第十四分块(前体)代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100050;
typedef long long lint;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Qry {int l, r, id; lint ans;} q[MAXN];
struct T{int l, r, id;};
int n, m, a[MAXN], siz[MAXN], k, blsz, bl[MAXN], t[MAXN], pref[MAXN];
vector <int> buc; vector <T> v[MAXN]; lint ans[MAXN];
int cmp(Qry a, Qry b) {return bl[a.l] == bl[b.l] ? a.r < b.r : a.l < b.l;}
int main() {
	read(n); read(m); read(k); blsz = sqrt(n);
	if(k > 14) {for(int i = 1; i <= m; ++i) puts("0"); return 0;}
	for(int i = 1; i <= n; ++i) read(a[i]);
	for(int i = 0; i < 16384; ++i) if((siz[i] = siz[(i>>1)] + (i&1)) == k) buc.push_back(i);
	for(int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), q[i].id = i;
	for(int i = 1; i <= n; ++i) bl[i] = (i-1) / blsz + 1;
	sort(q+1, q+m+1, cmp);
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < buc.size(); ++j) ++t[a[i]^buc[j]];
		pref[i] = t[a[i+1]];
	}
	for(int L = 1, R = 0, i = 1; i <= m; ++i) {
		int l = q[i].l, r = q[i].r;
		   if(L < l) v[R].push_back((T) {L, l-1, -i});
		while(L < l) {q[i].ans += pref[L-1]; ++L;}
		   if(L > l) v[R].push_back((T) {l, L-1, i});
		while(L > l) {q[i].ans -= pref[L-2]; --L;}
		   if(R < r) v[L-1].push_back((T) {R+1, r, -i});
		while(R < r) {q[i].ans += pref[R]; ++R;}
		   if(R > r) v[L-1].push_back((T) {r+1, R, i});
		while(R > r) {q[i].ans -= pref[R-1]; --R;}
	}
	memset(t, 0, sizeof t);
	for(int l, r, id, i = 1; i <= n; ++i) {
		for(int j = 0; j < buc.size(); ++j) ++t[a[i]^buc[j]];
		for(int o = 0; o < v[i].size(); ++o) {
			l = v[i][o].l; r = v[i][o].r; id = v[i][o].id;
			for(int j = l, tmp = 0; j <= r; ++j) {
				tmp = t[a[j]];
				if(j <= i && !k) --tmp;
				if(id > 0) q[id].ans += tmp;
				else q[-id].ans -= tmp;
			}
		}
	}
	for(int i = 1; i <= m; ++i) q[i].ans += q[i-1].ans;
	for(int i = 1; i <= m; ++i) ans[q[i].id] = q[i].ans;
	for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
LuoguP5047 Yuno loves sqrt technology II代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 123456;
const int blsz = 317;
typedef long long lint;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Qry {int l, r, id; lint ans;} q[MAXN];
struct T {int l, r, id;};
int bl[MAXN], n, m, a[MAXN], b[MAXN], t[MAXN], cr[MAXN], cl[MAXN], blnm, c[MAXN], s[MAXN];
lint ans[MAXN], pref1[MAXN], pref2[MAXN];
int cmp(Qry a, Qry b) {return bl[a.l] == bl[b.l] ? a.r < b.r : a.l < b.l;}
vector <T> vl[MAXN], vr[MAXN];
void update(int x) {for(; x <= 100005; ++t[x], x += x & (-x));}
int query(int x) {int res = 0; for(; x > 0; res += t[x], x ^= x & (-x)); return res;}
int main() {
	read(n); read(m);
	for(int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];
	sort(b+1, b+n+1); int _n = unique(b+1, b+n+1)-b-1;
	for(int i = 1; i <= n; ++i) a[i] = lower_bound(b+1, b+_n+1, a[i])-b;
	for(int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), q[i].id = i;
	for(int i = 1; i <= n; ++i) bl[i] = (i-1) / blsz + 1; blnm = bl[n];
	for(int i = 1; i <= n; ++i) {
		pref1[i] = pref1[i-1] + query(1e5) - query(a[i]);
		update(a[i]);
	} memset(t, 0, sizeof t);
	for(int i = n; i >= 1; --i) {
		pref2[i] = pref2[i+1] + query(a[i]-1);
		update(a[i]);
	}
	sort(q+1, q+m+1, cmp);
	for(int L = 1, R = 0, i = 1; i <= m; ++i) {
		int l = q[i].l, r = q[i].r;
		q[i].ans = pref1[r]-pref1[R]+pref2[l]-pref2[L];
		if(L < l) vl[r+1].push_back((T) {L, l-1, i});
		if(L > l) vl[r+1].push_back((T) {l, L-1, -i});
		if(R < r) vr[L-1].push_back((T) {R+1, r, -i});
		if(R > r) vr[L-1].push_back((T) {r+1, R, i});
		L = l; R = r;
	}
	for(int i = 1; i <= blsz; ++i) {
		cl[i] = cr[i-1] + 1; cr[i] = i*blsz;
		for(int j = cl[i]; j <= cr[i]; ++j) bl[j] = i;
	}
	//cout << m << endl;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < bl[a[i]]; ++j) ++s[j];
		for(int j = cl[bl[a[i]]]; j <= a[i]; ++j) ++c[j];
		for(int j = 0; j < vr[i].size(); ++j) {
			int l = vr[i][j].l, r = vr[i][j].r, id = vr[i][j].id;
			lint tmp = 0;
			for(int k = l; k <= r; ++k)
				tmp += s[bl[a[k]+1]] + c[a[k]+1];
			q[max(id, -id)].ans += (id < 0 ? -1 : 1) * tmp;
		}
	} memset(c, 0, sizeof c); memset(s, 0, sizeof s);
	for(int i = n; i >= 1; --i) {
		for(int j = bl[a[i]]+1; j <= blsz; ++j) ++s[j];
		for(int j = a[i]; j <= cr[bl[a[i]]]; ++j) ++c[j];
		for(int j = 0; j < vl[i].size(); ++j) {
			int l = vl[i][j].l, r = vl[i][j].r, id = vl[i][j].id;
			lint tmp = 0;
			for(int k = l; k <= r; ++k)
				tmp += s[bl[a[k]-1]] + c[a[k]-1];
			q[max(id, -id)].ans += (id < 0 ? -1 : 1) * tmp;
		}
	}
	for(int i = 1; i <= m; ++i) q[i].ans += q[i-1].ans, ans[q[i].id] = q[i].ans;
	for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}

 

点赞
  1. Okami说道:

    I AK IOI

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00