补题情况

题目	蒋贤蒙	王赵安	王智彪
A	0	0	0
B	1	0	0
C	1	0	0
D	0	0	0
E	2	0	0
F	2	0	0
G	0	0	0
H	0	0	0
I	2	0	0
J	2	0	0

题解

I. Kuriyama Mirai and Exclusive Or

题意

给定一个序列 $A$，接下来两种操作：

$a_i\gets a_i\oplus x(i\in [l,r])$
$a_i\gets a_i\oplus (x+i-l)(i\in [l,r])$

题解

$$ a_n=\left(\bigoplus_{i=1}^n b_i\right)\oplus\left(\bigoplus_{i=1}^n\bigoplus_{k=0}^{29} 2^k c(i,k)\right)\\ c(n,k)=\bigoplus_{i\times 2^k\le n} d(n-i\times 2^k,k) $$

简单来讲 $a_n$ 是 $b_i,c(i,k)$ 的前缀和，$c(n,k)$ 是 $d(i,k)$ 的隔 $2^k$ 项前缀和。

然后操作 $1$ 只需要修改 $b_i$ 即可。操作 $2$ 的影响按位考虑影响，将 $[l,r]$ 区间操作等效于 $[l,\inf),[r+1,\inf)$ 两次操作。

每次操作对每个位是按 $001111000011110000$ 的规律周期性变化的。

对该序列进行一次差分，于是得到 $001000100010001000$，这个可以利用 $c(n,k)$ 维护。

再一次差分得到 $001000000000000000$ 发现可以利用 $d(n,k)$ 维护。

最后处理一下最开始非周期的部分即可，时间复杂度 $O((n+q)\log v)$。

查看代码

const int MAXN=6e5+5,MAXB=30,mod=1<<30;
int n,a[MAXN],b[MAXN];
bitset<MAXN> c[MAXB];
void update(int pos,int v){
	_for(i,0,MAXB){
		int cyc=1<<(i+1),p1=pos%cyc,p2=((cyc-v%cyc)%cyc+(1<<i))%cyc,d=pos>>(i+1);
		if(p1>=p2){
			if(p1<p2+(1<<i)){
				b[pos]^=1<<i;
				if(d*cyc+p2+(1<<i)<MAXN)
				b[d*cyc+p2+(1<<i)]^=1<<i;
			}
			d++;
		}
		else if(p1<p2-(1<<i)){
			b[pos]^=1<<i;
			if(d*cyc+p2-(1<<i)<MAXN)
			b[d*cyc+p2-(1<<i)]^=1<<i;
		}
		if(d*cyc+p2<MAXN)
		c[i].flip(d*cyc+p2);
	}
}
int main() {
	n=read_int();
	int q=read_int();
	_for(i,0,n)a[i]=read_int();
	while(q--){
		int opt=read_int(),l=read_int()-1,r=read_int()-1,x=read_int();
		if(opt==0){
			b[l]^=x;
			b[r+1]^=x;
		}
		else{
			update(l,(x-l+mod)%mod);
			update(r+1,(x-l+mod)%mod);
		}
	}
	_for(i,0,MAXB){
		_for(j,0,n)if(j+(1<<i)<MAXN)
		c[i][j+(1<<i)]=c[i][j+(1<<i)]^c[i][j];
		_for(j,1,n)
		c[i][j]=c[i][j]^c[i][j-1];
		_for(j,0,n)
		a[j]^=(c[i][j]<<i);
	}
	_for(i,1,n)b[i]^=b[i-1];
	_for(i,0,n)a[i]^=b[i];
	_for(i,0,n)
	space(a[i]);
	return 0;
}

CVBB ACM Team

目录

补题情况

题解

I. Kuriyama Mirai and Exclusive Or

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

补题情况

题解

I. Kuriyama Mirai and Exclusive Or

题意

题解

页面工具