泛化的前缀和

为了能够使用的前缀和算法，类型T应该具有以下三种性质：

1. 有单位元。由默认构造函数得到；
2. 对于二元运算符+满足结合律；
3. 关于+有逆元。由一元运算符-得到。

用一个结构体来表示前缀和，但带个泛型参数T

template <typename T>
struct PreSum
{
	vector<T> sum;
	PreSum(vector<T> &a) : sum(a.size())
	{
		for (int i = 0; i < a.size(); ++i)
			sum[i + 1] = sum[i] + a[i];
	}

	T of(int l, int r) {
		return -sum[l - 1] + sum[r];
		// = T() + (-(a[0] + ... + a[l-1]))
		//       +   (a[0] + ... + a[l-1])
		//       +   (a[l] + ... + a[r]  )
		// = (a[l] + ... + a[r])
      
		// 若改为 sum[r] + (-sum[l-1]) 则可能出错，因为+不保证满足交换律
	}
};

H-0 and 1 in BIT 题解

在本题中，每个操作都是一个可逆的一次函数 [x => kx + b]。

A是 [x => -x - 1] ，B是 [x => x + 1] 。

于是可以编写一个结构体F来表示“操作”：

struct F
{
	int k = 1; // 只能为1或-1
	int b = 0;
	// [x => kx + b] + [x => k'x + b'] = [x => (k'k)x + (k'b+b')]
	F operator+(F n) // 二元运算+取为一次函数的复合
	{
		return F{.k = n.k * k,
				 .b = n.k * b + n.b};
	}
	// -[x => kx + b] = [x => x/k - b/k]
	F operator-() // 求逆就是求它的反函数
	{
		return F{.k = 1 / k,
				 .b = -b / k};
	}
	ll operator()(ll x) { return k * x + b; }
};

然后是两个函数，一个负责把01字符串转换成long long int，一个负责把long long int以01字符串的形式输出：

ll strtoll(string s)
{
	ll res = 0;
	for (char c : s)
		res = res * 2 + c - '0';
	return res;
}

void output(ll x, int len)
{
	for (int i = len - 1; i >= 0; --i)
		cout << ((x >> i) & 1);
	cout << endl;
}

主函数要优雅：

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;

	vector<F> f(n);

	string s;
	cin >> s;
	transform(s.begin(), s.end(), f.begin(),
			  [](char c)
			  { return c == 'A' ? F{-1, -1} : F{1, 1}; });

	PreSum<F> sum(f);

	ll ans = 0;
	for (int i = 0; i < q; ++i)
	{
		int l, r;
		string xstr;
		cin >> l >> r >> xstr;
		l = (ans ^ l) % n + 1;
		r = (ans ^ r) % n + 1;
		if (l > r)
			swap(l, r);

		int len = xstr.size();
		ans = sum.of(l, r)(strtoll(xstr)) & ((1LL << len) - 1);
		output(ans, len);
	}

	return 0;
}

我觉得这种写法最有意思的的地方，是利用泛型把前缀和算法的作用对象 T 给抽象出来了。于是 T 可以填入 int 、矩阵、或者像这道题里的一次函数 F ，从而适应各种题目，而 PreSum 不必修改。

这FP多是一件美事