Warning: session_start(): open(/tmp/sess_ef043c168d2b94d58bd6595158bae562, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest6

比赛链接

补题情况

题目 蒋贤蒙 王赵安 王智彪
A 0 0 0
B 1 2 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$,接下来两种操作:

  1. $a_i\gets a_i\oplus x(i\in [l,r])$
  2. $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;
}
2020-2021/teams/legal_string/组队训练比赛记录/contest6.1627310932.txt.gz · 最后更改: 2021/07/26 22:48 由 lgwza