2021 牛客多校第三场 I.Kuriyama Mirai and Exclusive Or @ Wings            分类 ACM
发布于 星期四, 八月 12 日, 2021 年
更新于 星期四, 八月 12 日, 2021 年

题目

题意

长度为 $n$ 的序列 $a$, $q$ 次操作, 每次如下一种:

  1. 0 l r x 区间 $[l, r]$, $a_i \leftarrow a_i \oplus x$
  2. 1 l r x 区间 $[l, r]$, $a_i \leftarrow a_i \oplus (x + i - l)$

$\oplus$ 是按位异或.

求所有操作后的数组.

$1 \le n \le 6 \times 10^5, 1 \le q \le 4 \times 10^5, 0 \le a_i < 2^30$

题解

并看不懂dls(还是他学弟?)的做法. 我太菜了

第一个操作直接维护差分数组 $d$, 即 $d_l \leftarrow d_l \oplus x, d_{r+1} \leftarrow d_{r+1} \oplus x$. 只需要对 $d$ 做一次前缀和, 然后异或上对应的 $a_i$ 即可.

考虑第二个操作, 先考虑一个大的"差分", 设一个操作 update(p, x), 为 $a_{p+i} \leftarrow a_{p+i} \oplus (x + i)$, 由于异或的减等于加的性质, 对一个区间做操作1, 就是 update(l, x), update(r+1, x+r-l+1).

位运算的套路是按位做, 那么按位看看会发生什么. 一个从 $0$ 开始的连续的序列, 每次加增加 $2^i$ 个数, 才会改变第 $i$ 位的值. 比如从 $0$ 开始的连续的数在二进制下为:

$$0\color{red}000, 0\color{red}001, 0\color{red}010, 0\color{red}011, 0\color{red}100, 0\color{red}101, 0\color{red}110, 0\color{red}111, 1\color{red}000, 1\color{red}001, 1\color{red}010, 1\color{red}011, 1\color{red}100, \dots$$

第 $2$ 位在上面已经标出, 拿出来看是这样的:

$$0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, \dots$$

这东西不也是区间异或吗? 那就维护差分数组 $d$. 需要在每一段 $1$ 的开始, 和每一段 $1$ 结束的下一位, 也就是每一段 $0$ 的开始异或上 $1$, 然后就会发现, 对于第 $i$ 位, 需要每隔 $2^i$ 位对 $d$ 的第 $i$ 位异或一下.

但是, 每次操作枚举第 $i$ 每隔 $2^i$ 进行一次异或, 这样复杂度较高. 但是可以记录一下每一个位置的数每一位第一个"需要异或标记". 最后在处理的时候, 将这个标记"向后推" $2^i$ 个数. 这样本来一次操作就要每隔 $2^i$ 进行一次异或, 变成了现在所有操作完成后, 枚举 $i$ 每隔 $2^i$ 进行一次异或.

现在来看具体的 update(p, x) 函数, 首先枚举第 $i$ 位, 由于x并不是0, 会造成类似于这样的东西, 以 $x=3, i=2$ 举例:

$$0, 1, 1, 1, 1, 0, 0, 0, 0, 1, \dots$$

所以需要找到第一个"整块"的 $1$ 或 $0$ 的位置, 在这个位置上打标记. 这个很好解决, 就把连续的数分成 $2^i$ 组, 然后用 $x$ 去模 $2^i$, 就知道他是一组里的第几个, 所以 $x - (x \bmod 2^i)$ 就是找到了第一个整块的 $0$ 或者 $1$, 打上标记. 当然如果碰到这样的情况:

$$1, 1, 0, 0, 0, 0, 1, 1, 1, 1, \dots$$

第个一数是1, 那就需要对差分数组进行异或.

复杂度 $O(n\log a + q\log a)$

连续区间并且和异或有关, 就有"分块"的性质, 要善于挖掘.

代码
int q, n, a[MAXN], d[MAXN];
bool tag[MAXN][32];

void update(int p, int x) {
	if (p > n)
		return;
	for (int i = 0; i < 30; i++) {
		int pw = 1 << i;
		if (x & pw)
			d[p] ^= pw;
		int first = p + pw - (x % pw);
		if (first <= n)
			tag[first][i] ^= 1;
	}
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	while (q--) {
		int op, l, r, x;
		scanf("%d%d%d%d", &op, &l, &r, &x);
		if (op)
			update(l, x), update(r + 1, r - l + x + 1);
		else
			d[l] ^= x, d[r+1] ^= x;
	}
	for (int j = 0; j < 30; j++)
		for (int i = 1; i <= n; i++) {
			if (tag[i][j])
				d[i] ^= 1 << j;
			int nxt = i + (1 << j);
			if (nxt <= n)
				tag[nxt][j] ^= tag[i][j];
		}
	for (int i = 1; i <= n; i++) {
		d[i] ^= d[i-1];
		a[i] ^= d[i];
	}
	for (int i = 1; i <= n; i++)
		printf("%d%c", a[i], " \n"[i==n]);
	return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch