H. 0 and 1 in BIT_牛客博客

写给 H 题，用了和正解看上去完全不同的思路并且 A 掉了 QAQ

题目大意

给定一个长为 $n$ 的只含 A 和 B 两种字符的字符串。字符串中的每个字符表示对给定二进制数 $t$ 的一个操作，字符 A 表示将 $t$ 中的所有元素 $0, 1$ 取反，B 表示令 $t$ 增加 $1$ 。

进行 $Q$ 次询问，第 $i$ 次询问对给定二进制数 $t_{i}$ 顺序进行字符串中区间 $[l_{i}, r_{i}]$ 里的所有操作，输出操作后形成的二进制数，与给定的 $t_{i}$ 位数相同，即溢出的高位舍弃。

数据范围 $2 e 5$ 级别，询问强制在线。

思路

考虑对一段区间中的操作进行合并。

我们可以将操作 B 的 $+ 1$ 和给定的被操作二进制数 $t_{i}$ 都在逻辑上增添符号位 $1$ ，即将它们都视为负数。由于我们只输出操作后二进制数的有效后缀，该行为不会影响答案的正确性。

对每个区间 $[l, r]$ ，我们将其中所有的操作压为一个三元组 $(x, y, z)$ ，表示将“对 $t$ 顺序执行字符串中区间 $[l_{i}, r_{i}]$ 里的所有操作”等价为顺次进行以下三个操作：

令 $t$ 增加 $x$ 。
如果 $y = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

让我们用数学归纳法来证明上述等价是可行的。

首先由三元组的定义可以知道，操作 A 可以表示成三元组 $(0, 0, 1)$ ，操作 B 可以表示成三元组 $(1, 0, 0)$ 。

假设两个相邻的操作区间分别可以用上述三元组表示为 $(x 1, y 1, z 1)$ 和 $(x 2, y 2, z 2)$ ，即我们要顺序进行如下操作：

令 $t$ 增加 $x_{1}$ 。
如果 $y_{1} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{1} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。
令 $t$ 增加 $x_{2}$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

怎样将这六个操作合并为一个三元组呢？我们进行如下讨论：

如果 $y_{1} = 0$ 且 $z_{1} = 0$ ，相当于顺序进行下述操作：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 增加 $x_{2}$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

等价为三元组 $(x_{1} + x_{2}, y_{2}, z_{2})$ 。

如果 $y_{1} = 0$ 且 $z_{1} = 1$ ，相当于顺序进行下述操作：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 中的所有元素 $0, 1$ 取反。
令 $t$ 增加 $x_{2}$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

观察操作 $2, 3$ ，又我们将所有操作数都视为负数，可以发现：

\begin{aligned} &(\sim t)+x_2\\ =&[[(\sim t)]_补+[x_2]_补]_补\\ =&[[\sim(\sim t)]+1+(\sim x_2)+1]_补\\ =&[t+(\sim x_2)+2]_补 \end{aligned}

所以操作等价于：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 增加 $(\sim x_2)+2$ 。
令 $t$ 变成 $t$ 的补码。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

等价为三元组 $(x_1+(\sim x_2)+2,y_2\oplus 1,z_2)$ 。

如果 $y_{1} = 1$ 且 $z_{1} = 0$ ，相当于顺序进行下述操作：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 变成 $t$ 的补码。
令 $t$ 增加 $x_{2}$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

观察操作 $2, 3$ ，又我们将所有操作数都视为负数，可以发现：

\begin{aligned} &[t]_补+x_2\\ =&[[[t]_补]_补+[x_2]_补]_补\\ =&[t+[x_2]_补]_补\\ =&[t+(\sim x_2)+1]_补 \end{aligned}

所以操作等价于：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 增加 $(\sim x_2)+1$ 。
令 $t$ 变成 $t$ 的补码。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

则等价为三元组 $(x_1+(\sim x_2)+1,y_2\oplus 1,z_2)$ 。

如果 $y_{1} = 1$ 且 $z_{1} = 1$ ，相当于顺序进行下述操作：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 变成 $t$ 的补码。
令 $t$ 中的所有元素 $0, 1$ 取反。
令 $t$ 增加 $x_{2}$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

由过去两种方案的讨论可知，操作 $3, 4$ 可以合并为先令 $t$ 增加 $(\sim x_2)+2$ ，再令 $t$ 变成 $t$ 的补码。然后我们将 $(\sim x_2)+2$ 求补后可以交换和操作 $2$ 的执行顺序。而两次求补操作可以相互抵消，则最终相当于顺序执行下述操作：

令 $t$ 增加 $x_{1}$ 。
令 $t$ 增加 $(\sim((\sim x_2)+2))+1$ 。
如果 $y_{2} = 1$ 则令 $t$ 变成 $t$ 的补码。
如果 $z_{2} = 1$ 则令 $t$ 中的所有元素 $0, 1$ 取反。

等价为三元组 $(x_1+(\sim((\sim x_2)+2))+1,y_2,z_2)$ 。

综上所述，我们证明了可以用三元组表示一段操作区间，同时证明了相邻的两个操作区间可以 $O (1)$ 进行合并。用线段树进行维护即可。

代码

#include <bits/stdc++.h>
using namespace std;
using LL=unsigned long long;
const int N=2e5+5;
unsigned int m,n;
struct asdf{
	LL x;
	unsigned int y,z;
	asdf operator + (const asdf a) const
	{
		if (y==0&&z==0) return {x+a.x,a.y,a.z};
		if (y&&z) return {x+(~((~a.x)+2))+1,a.y,a.z};
		if (y) return {x+(~a.x)+1,!a.y,a.z};
		return {x+(~a.x)+2,!a.y,a.z};
	}
}s[N<<2];
char a[N];
void build(unsigned int l,unsigned int r,unsigned int rt)
{
	if (l==r)
	{
		if (a[l]=='A') s[rt].z=1;
		else s[rt].x=1;
		return;
	}
	build(l,(l+r)>>1,rt<<1);
	build((l+r>>1)+1,r,rt<<1|1);
	s[rt]=s[rt<<1]+s[rt<<1|1];
}
asdf query(unsigned int l,unsigned int r,unsigned int rt,unsigned int x,unsigned int y)
{
	if (x<=l&&r<=y) return s[rt];
	if (y<=(l+r>>1)) return query(l,l+r>>1,rt<<1,x,y);
	if (x>(l+r>>1)) return query((l+r>>1)+1,r,rt<<1|1,x,y);
	return query(l,l+r>>1,rt<<1,x,y)+query((l+r>>1)+1,r,rt<<1|1,x,y);
}
char ch[101];
LL val[101];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf(" %c",&a[i]);
	build(1,n,1);
	LL x,ans=0,L,R;
	for (int i=1,k,l,r;i<=m;++i)
	{
		scanf("%llu%llu %s",&L,&R,ch+1);
		l=min((ans^L)%n+1,(ans^R)%n+1);
		r=max((ans^L)%n+1,(ans^R)%n+1);
		asdf opt=query(1,n,1,l,r);
		k=strlen(ch+1);
		for (int j=0;j<k;++j) val[j]=ch[k-j]-'0';
		val[0]+=opt.x;
		for (int j=0;j<k;j++)
		{
			val[j+1]+=val[j]/2;
			val[j]%=2;
		}
		if (opt.y)
		{
			for (int j=0;j<k;j++) val[j]=!val[j];
			val[0]++;
			for (int j=0;j<k;j++)
			{
				val[j+1]+=val[j]/2;
				val[j]%=2;
			}
		}
		if (opt.z) for (int j=0;j<k;j++) val[j]=!val[j];
		ans=0;
		for (int j=k-1;j>=0;--j)
		{
			ans=ans<<1|val[j];
			printf("%d",val[j]);
		}
		printf("\n");
	}
}