[牛客多校5] Interval • CC's

给出 $A_1, \cdots, A_n$ 。每次询问一个区间，求该区间的子区间的[与]^(&)分别有多少不相同结果。

询问强制在线。

$A_i < 2^{30}$

分析#

第一个要解决的问题是如何找到不相同的结果。根据与的性质，如果固定一个左端点（或者右端点），我们最多也就拿到30种不同的取值（每一位成0后不再变化）。第一步是把这些取值全部求出来。只要记录一下从哪一个 $A$ 起，二进制位第 $i$ 位发生了变化即可。这样拿到的结果就是形如 $(i,j)$ 表示以第 $i$ 个为左端点，在第 $j$ 个时结果发生了一次变化。对于一个固定的i来讲，j一定是升序的。

每次查询时查询对于 $[l,r]$ ，有多少个 $(i,j)$ 满足 $i\geq l,j\leq r$ 。这个时候可以考虑二维偏序的一般套路。第1维表示 $i$ ，从末尾枚举到开头，保证第一维偏序，第二维通过数据结构去维护。对于这道题来讲，每一个 $j$ 都表达了一次值的突变，所以我们就是去查对应区间中包含了多少个 $j$ 。然而这样有个问题，这个不同只是针对固定 $i$ 来讲的，对于不同的 $i$ 可能相互有一样的值。……这个转化套路我第一次听说，就是对于任意两个相同值的相邻突变点 $j$ ，插入一个新的贡献-1，从而把重复的一个减掉。

如果是离线的话到现在就已经做完了，强制在线多出来一些额外的问题。需要把第一维也扔进数据结构里维护才可以。一番查找后我了解到了主席树（心碎）。

xjb理解来说，可持久化线段树能够保存每次修改时的线段树版本——倒不如说可持久化就是指的这个特性。而利用这个特性我们可以完成这道题的要求。仍旧采用一样的枚举顺序和更新策略，并且保存下每一位更新后的历史版本，每次查询到对应的历史版本里去查即可。

想象一下最暴力的做法，我对于每个后缀 $i$ 都维护一个线段树，除了空间爆炸、时间爆炸之外，其他都挺好。可持久化线段通过一些手段，使得新版本能够利用旧版本已有的节点来优化时空占用。具体是对于一次修改操作，它最多会影响一条链上的节点，而其他部分保持不变，所以我们可以每次只创建一条新的链。

自己yy了份板子。

int idx = 0;
int lc[XN], rc[XN];
int dat[XN];

void pushup(int n) {
	dat[n] = dat[lc[n]] + dat[rc[n]];
}

int update(int pos, int x, int L, int R, int n) {
	int ne = ++idx;

	lc[ne] = lc[n], rc[ne] = rc[n];
	dat[ne] = dat[n];

	if (L == R && L == pos) {
		dat[ne] += x;
		return ne;
	}

	int mid = (L + R) / 2;
	if (pos <= mid)lc[ne] = update(pos, x, L, mid, lc[ne]);
	if (mid < pos)rc[ne] = update(pos, x, mid + 1, R, rc[ne]);

	pushup(ne);
	return ne;
}

int query(int l, int r, int L, int R, int n) {
	if (l <= L && R <= r)return dat[n];

	int res = 0;
	int mid = (L + R) / 2;
	if (l <= mid)res += query(l, r, L, mid, lc[n]);
	if (mid < r)res += query(l, r, mid + 1, R, rc[n]);

	return res;
}

cpp

看起来和一般的线段树没啥大区别，至少对这道题来讲。

代码#

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
const int XN = 1e5 * 40 * 4;
const int XM = 40;


int idx = 0;
int lc[XN], rc[XN];
int dat[XN];

void pushup(int n) {
	dat[n] = dat[lc[n]] + dat[rc[n]];
}

int update(int pos, int x, int L, int R, int n) {
	int ne = ++idx;

	lc[ne] = lc[n], rc[ne] = rc[n];
	dat[ne] = dat[n];

	if (L == R && L == pos) {
		dat[ne] += x;
		return ne;
	}

	int mid = (L + R) / 2;
	if (pos <= mid)lc[ne] = update(pos, x, L, mid, lc[ne]);
	if (mid < pos)rc[ne] = update(pos, x, mid + 1, R, rc[ne]);

	pushup(ne);
	return ne;
}

int query(int l, int r, int L, int R, int n) {
	if (l <= L && R <= r)return dat[n];

	int res = 0;
	int mid = (L + R) / 2;
	if (l <= mid)res += query(l, r, L, mid, lc[n]);
	if (mid < r)res += query(l, r, mid + 1, R, rc[n]);

	return res;
}

int a[XN], b[XM];
vector<int> cha;

struct Line {
	int l, r, x;
	int delta;
};
vector<Line> lines;
vector<Line> offset;

int rt[XN];

int main() {
	ios::sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < XM; i++)b[i] = n + 1;

	for (int i = n; i >= 1; i--) {
		cha.clear();
		for (int j = 0; j < XM; j++) {
			if (((a[i] >> j) & 1) == 0) {
				b[j] = min(b[j], i);
			}
			cha.push_back(b[j]);
		}
		sort(cha.begin(), cha.end());
		int temp = (1 << 30) - 1;
		for (auto pos : cha) {
			if (pos > n)continue;

			int t = temp & a[pos];
			if (t == temp)continue;
			temp = t;
			lines.push_back({ i,pos,temp,1 });
		}
	}

	sort(lines.begin(), lines.end(), [](const Line& a, const Line& b) {
		if (a.x != b.x)return a.x < b.x;
		if (a.l != b.l)return a.l < b.l;
		return a.r < b.r;
	});
	/*
	for (auto item : lines) {
		cout << item.l << " " << item.r << "=" << item.x << "/" << item.delta << endl;
	}
	*/

	for (int i = 0, j = 0; i < lines.size(); i++, j++) {
		while (j < lines.size() && lines[i].x == lines[j].x) {
			j++;
		}
		j--;
		if (i == j) {
			continue;
		}

		for (; i < j; i++)
			offset.push_back({ lines[i].l,lines[i + 1].r,-1,-1 });
	}

	lines.insert(lines.end(), offset.begin(), offset.end());
	sort(lines.begin(), lines.end(), [](auto a, auto b) {
		if (a.l != b.l)return a.l > b.l;
		return a.r < b.r;
	});
	/*
	for (auto item : lines) {
		cout << item.l << " " << item.r << "=" << item.x << "/" << item.delta << endl;
	}
	*/

	int lastl = 0;
	for (int i = 0; i < lines.size(); i++) {
		rt[lines[i].l] = update(lines[i].r, lines[i].delta, 1, n, rt[lastl]);
		lastl = lines[i].l;
	}

	int q; cin >> q;
	int lastans = 0;
	while (q--) {
		int l1, r1; cin >> l1 >> r1;
		int l = (l1 ^ lastans) % n + 1;
		int r = (r1 ^ lastans) % n + 1;
		if (l > r)swap(l, r);

		lastans = query(l, r, 1, n, rt[l]);
		//cout << l << " " << r << "=" << lastans << endl;
		cout << lastans << "\n";
	}


	return 0;
}

cpp