Codeforces Educational Round 90 G.Pawns @ Wings            分类 ACM
发布于 星期一, 一月 25 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

一个 $n \times n$ 的棋盘上会有 $m$ 次变化, 每次变化都会在某个空的位置上出现一个兵 或者 移去存在棋盘上的某个兵. 一个兵处于坐标 $(x, y)$ 可以移动到 $(x, y + 1)$, $(x − 1, y + 1)$ 或 $(x + 1, y + 1)$, 前面是列, 后面是行. 有一个特殊列 $k$, 每次变化, 你都要计算把所有的兵移动到第 $k$ 列(不可以重叠), 需要在棋盘上第 $n$ 之后额外添加的最少行数.

$1 \le n, m \le 2 \cdot 10^5, 1 \le k \le n$

题解

首先把棋子都用最近的移动方式移动到第 $k$ 列, 可让他们重叠在一格里. 这样就变成一维的问题了.

考虑这个一维的序列, 如图, 我们需要把多的兵往下移.

把多的兵往下移动

我们记录这个点的权值为当把所有兵依次往下放, 走的最远的那个兵的行号. 图中即 $w(2) = 5$.

要维护这样的一个权值, 首先可以考虑初始化第 $i$ 行的权值为 $i-1$, 然后这一个点出现一个兵, 就把这个点的权值 $+1$; 同理消失一个兵就 $-1$.

但是会出现这样的情况: 上面要走的兵与下面有的兵冲突了! 见下图左.

冲突了

我们先让下面蓝色的兵走, 然后再让上面红色的兵"跳过"蓝色的兵, 走到蓝色底下, 见上图右.

这样就有 $w(2) = 6, w(4) = 7$.

按照这样的想法, 下面的兵会对上面的兵产生影响, 而影响就是让上面的权值增加. 增加的数量就是下面的兵的数量.

那么我们可以用线段树维护一段 $2n$ 的序列: 先初始化每个点为$i-1$, 在 $pos$ 位置放一个兵, 就让区间 $[1, pos]$ 都 $+1$; 拿走就 $-1$. 然后取区间 $[1, pos_{last}]$ 中的最大值, 就是最远放的兵了.

注意, 这个线段树中不是每个点的权值都有"实际意义". 比如, 没有兵的点, 权值不能代表什么. 有兵的点, 权值可能大于"这个点的所有兵能走的最远行号", 比如这样:

不是所有的点都有意义

我们认为的$w(1) = 1$, 而按照上述维护线段树的方法, 得到在 $1$ 处的值是 $7$.

这种情况其实不用担心, 因为最远的那个兵对应的起点, 在线段树上的值就是$w$, 而取max一定是取到最远的兵.

出现位置用 set 记录一下就就行.

复杂度$O(mlogn + mlogm)$

代码
const int MAXN = 2e5+10;

int n, k, q;

struct SegTree {
	struct Node {
		int l, r, mid, val, tag;
	};
	int n;
	vector<Node> tree;
	void init(int _n) {
		n = _n;
		tree.clear();
		tree.resize((n+10) << 2);
	}
	void push_up(int u) {
		tree[u].val = max(tree[LCH(u)].val, tree[RCH(u)].val);
	}
	void build(int u, int l, int r, VI &data) {
		tree[u] = Node{l, r, (l + r) >> 1, 0, 0};
		if (l == r)
			tree[u].val = data[l];
		else {
			build(LCH(u), l, tree[u].mid, data);
			build(RCH(u), tree[u].mid + 1, r, data);
			push_up(u);
		}
	}
	void build(VI &data) {
		build(1, 1, n, data);
	}
	void update_node(int u, int d) {
		tree[u].val += d;
		tree[u].tag += d;
	}
	void push_down(int u) {
		update_node(LCH(u), tree[u].tag);
		update_node(RCH(u), tree[u].tag);
		tree[u].tag = 0;
	}
	void update(int l, int r, int d, int u = 1) {
		if (tree[u].l == l && tree[u].r == r)
			update_node(u, d);
		else {
			push_down(u);
			if (r <= tree[u].mid)
				update(l, r, d, LCH(u));
			else if (l > tree[u].mid)
				update(l, r, d, RCH(u));
			else {
				update(l, tree[u].mid, d, LCH(u));
				update(tree[u].mid + 1, r, d, RCH(u));
			}
			push_up(u);
		}
	}
	int query(int l, int r, int u = 1) {
		if (tree[u].l == l && tree[u].r == r)
			return tree[u].val;
		else {
			push_down(u);
			if (r <= tree[u].mid)
				return query(l, r, LCH(u));
			else if (l > tree[u].mid)
				return query(l, r, RCH(u));
			else
				return max(query(l, tree[u].mid, LCH(u)), query(tree[u].mid + 1, r, RCH(u)));
		}
	}
};

int main() {
#ifdef GDB
	freopen("B.in", "r", stdin);
	// freopen("B.out", "w", stdout);
#endif
	scanf("%d%d%d", &n, &k, &q);
	SegTree tree;
	tree.init(n<<1);
	VI data = {0};
	for (int i = 1; i <= n<<1; i++)
		data.push_back(i-1);
	tree.build(data);
	set<PII> apd;
	multiset<int> ocp;
	while (q--) {
		int x, y;
		scanf("%d%d", &x, &y);
		PII cood = {x, y};
		int pos = y + abs(x - k);
		if (apd.find(cood) != apd.end()) {
			apd.erase(cood);
			ocp.erase(ocp.find(pos));
			tree.update(1, pos, -1);
		}
		else {
			apd.insert(cood);
			ocp.insert(pos);
			tree.update(1, pos, 1);
		}
		if (ocp.empty())
			puts("0");
		else
			printf("%d\n", max(0, tree.query(1, *ocp.rbegin()) - 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