XX Open Cup Grand Prix of Korea F.Hilbert’s Hotel @ Wings            分类 ACM
发布于 星期五, 十二月 11 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

背景是希尔伯特的旅馆问题.

一个旅馆有无限个房间, 从$0$开始编号, 一开始都住满了人, 这些人设为第$0$组. 随后会有其他旅客组团入住旅馆. 如果下一组有$k$个旅客入住, 那么原先住在$x$号房间的人移至$x+k$号房间, 空出$0$到$k-1$号房间给新入住的旅客; 如果下一组有无限个旅客入住, 那么原先住在$x$号房间的旅客移至$2x$号房间, 空出$2x+1$号房间给新入住的旅客.

$Q (1 \le Q \le 3 \cdot 10^5)$次操作:

  • 1 k $k \ne 0$时, 有$k$个旅客入住; $k = 0$时, 有无现个旅客入住. $0 \le k \le 10^9$.
  • 2 g x 查询第$g$组旅客第$x$小房号模$10^9 + 7$. $1 \le x \le 10^9$, 保证存在解
  • 3 x 查询房号为$x$的房间住的是第几组的旅客. $0 \le x \le 10^9$

题解

询问$2, 3$是独立的, 先看看$2$怎么做吧.

由于给定了组号, 并且各组之间也是独立的, 每组第$x$小的房间号是否可以用一个函数写出来呢? 答案显然是可以! 一开始第$0$组的函数为$g_0(x) = x$, 如果新来了$k_1$个旅客, 那么原来的函数都加上一个$k_1$, 比如$g_0(x)$变为$g_0(x) = x + k_1, (0 \le x)$, 新来的这一组函数为$g_1(x) = x, (0 \le x < k_1)$. 如果新来了无限个旅客, 那么原来的函数都乘以$2$, 比如$g_0(x) = 2x + 2k_1, (0 \le x)$, $g_1(x) = 2x, (0 \le x < k_1)$, 新来的这一组函数为$g_2(x) = 2x + 1, (0 \le x)$. 这样对于查询$2$, 就可以很方便地代值计算得到答案了.

结合题目和这些函数, 可以发现, 函数是一次函数. 又由于要对前缀进行区间修改, 可以考虑使用线段树, 那么找一个特定的组号就是单点查询. 进一步发现, 一次函数中, $x$的系数一定是$2$的次幂, 所以我们在保存节点信息时, 可以保存系数的指数, 以及截距. 答案需要取模, 所以截距可以取模保存. 因为是区间修改, 还需要打个lazy tag.

对于询问$3$, 先来考虑暴力的做法. 直接存哪个房价住的是哪些人是不现实的, 但是我们可以"回溯". 即给出的$x$, 去考虑上一个操作$1$, 如果是入住$k$个人, 那么这个查询就相当于没有上一个操作$1$, 然后查询3 (x-k). 当然如果$x-k$是负数, 那么显然这个$x$就是属于上一个操作$1$所修改的, 即答案为上一个操作$1$的组号. 入住无限个旅客也是同理, 让$x$除以$2$, 如果$x$是奇数, 那么就是属于上个操作$1$所修改的, 否则就可以看成在上一个操作$1$之前的查询3 x/2. 因为每个操作$1$, 对应每一组, 所以一直回溯, 便可找到相应的组了.

这样复杂度是$O(Q)$的, 加上查询就是$O(Q^2)$, 显然不行. 但是这个做法有优化的空间. 如果有一段连续的加$k$, 设他们的和为$sum$, 那么就可以直接$O(1)$判断答案是不是在这一段连续的加中. 即, 如果$x' = x - sum < 0$, 则在, 否则不在. 在的话可以二分, $O(logQ)$找到具体是哪一个点让他小于$0$. 不在的话, 说明需要再往前找. 连续一段加的前面一个是乘以$2$, 那么首先看$x'$的奇偶性, 像之前说的那样判断是找到了还是需要继续回溯.

记录乘以$2$出现的位置, 即可直接找到一段连续的加(见代码p2[]).

维护一段连续的加, 需要的是后缀和. 其实可以在操作的过程中$O(Q)$维护前缀和$pre[]$, 后缀和可以通过两个前缀和的差得到.

这样查询$3$的复杂度就只和乘以$2$的次数有关. 每次到乘以$2$的点都会让$x$减半, 那么查询$3$的复杂度就是$O(logx + logQ)$

需要特别注意的是$x = 0$(或者在回溯的过程中$x' = 0$)的情况. 如果此时前面都是乘以$2$的操作, 那么他会一直跑完这些操作, 这样复杂度会被卡成$O(Q^2)$, 所以我们需要特判$x = 0$(或$x' = 0$)的情况: 对于连续的乘以$2$, 直接跳到最前面第一个乘以$2$的操作即可. 可$O(Q)$在过程中预处理(见代码last_2[], gid[]).

总复杂度$O(Q(logQ + logx)) \approx O(QlogQ)$

代码

(过程中需要用到G-1, 所以我的G从$1$开始; 第$x$小是直接代入, 所以$x-1$, 当然也可以初始化一次函数截距b为$10^9 + 6$, $x$直接代入)

const int maxn = 3e5+10;
const int P = 1e9+7;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}

int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

struct SegmentTreeNode {
	int l, r, mid, pk, b;
} tree[maxn << 2];

int n, pw[maxn], G = 1, last_2[maxn], cnt = 0, gid[maxn];
LL pre[maxn];
vector<int> p2;

void Build(int v, int l, int r) {
	tree[v] = SegmentTreeNode{l, r, (l+r)>>1, 0, 0};
	if (l == r)
		return;
	else {
		Build(LCH(v), l, tree[v].mid);
		Build(RCH(v), tree[v].mid+1, tree[v].r);
	}
}

void Init() {
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = Mult(pw[i-1], 2);
	Build(1, 1, n);
}

void UpdateNode(int v, int pk, int b) {
	tree[v].b = Mult(pw[pk], tree[v].b);
	tree[v].b = Plus(tree[v].b, b);
	tree[v].pk += pk;
}

void Down(int v) {
	UpdateNode(LCH(v), tree[v].pk, tree[v].b);
	UpdateNode(RCH(v), tree[v].pk, tree[v].b);
	tree[v].pk = tree[v].b = 0;
}

void Update(int v, int l, int r, int pk, int b) {
	if (tree[v].l == l && tree[v].r == r)
		UpdateNode(v, pk, b);
	else {
		Down(v);
		if (l > tree[v].mid)
			Update(RCH(v), l, r, pk, b);
		else if (r <= tree[v].mid)
			Update(LCH(v), l, r, pk, b);
		else {
			Update(LCH(v), l, tree[v].mid, pk, b);
			Update(RCH(v), tree[v].mid+1, r, pk, b);
		}
	}
}

int Query(int v, int p, int x) {
	if (tree[v].l == tree[v].r)
		return Plus(Mult(pw[tree[v].pk], x), tree[v].b);
	Down(v);
	if (p > tree[v].mid)
		return Query(RCH(v), p, x);
	else
		return Query(LCH(v), p, x);
}

int main() {
	scanf("%d", &n);
	Init();
	pre[1] = 0;
	last_2[1] = -1;
	for (int i = 1; i <= n; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1){
			int k;
			scanf("%d", &k);
			if (k) {
				Update(1, 1, G++, 0, k);
				pre[G] = pre[G-1] + k;
				last_2[G] = 0;
			}
			else {
				Update(1, 1, G++, 1, 0);
				Update(1, G, G, 1, 1);
				pre[G] = 0;
				last_2[G] = last_2[G-1] ? last_2[G-1] : G;
				gid[G] = cnt++;
				p2.push_back(G);
			}
		}
		else if (op == 2){
			int g, x;
			scanf("%d%d", &g, &x);
			printf("%d\n", Query(1, g+1, x-1));
		}
		//下面写的和狗屎一样丑, 能力有限, 见谅
		else {
			int x;
			scanf("%d", &x);
			int cur = G, res = 1, L = 2, R = G, flag = 1;
			for (int i = p2.size() - 1; ~i; i--) {
				// 等于0也可回溯上一步
				if (x - pre[cur] >= 0) {
					x -= pre[cur];
					if (x & 1) {
						res = p2[i];
						flag = 0;
						break;
					}
					else {
						if (x == 0) {
							cur = last_2[p2[i]];
							i = gid[cur];
						}
						x >>= 1;
						cur = p2[i] - 1;
						R = cur;
					}
				}
				else {
					L = p2[i] + 1, R = cur;
					break;
				}
			}
			if (flag) {
				while (L <= R) {
					int mid = (L + R) >> 1;
					if (x - (pre[cur] - pre[mid-1]) < 0) {
						L = mid + 1;
						res = mid;
					}
					else
						R = mid - 1;
				}
			}
			printf("%d\n", res-1);
		}
	}
	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