拾柒的元旦封条

\\n\\n## 题目背景\\n\\n2025 年的最后一天，拾柒在街角摆了一排烟花，准备迎接 2026 年的元旦。\\n\\n为了“年味儿”，拾柒给每串烟花贴了一个编号 $a_i$。但这些编号并不是普通的数字：它们会经历一种奇怪的“压岁合并仪式”。更怪的是，店家扎绳成“束”的方式也依赖这套仪式。\\n\\n“新的一年，要学会把复杂的东西压缩成简单的样子。”拾柒一边贴封条一边念叨。\\n\\n于是它设计了如下规则，并抛给你一堆封条与询问，让你找出最早能把“年味预算”压到合格线的时刻。\\n\\n\\n## 题目描述\\n\\n设常数 $B=2026$。\\n\\n对任意非负整数 $x$，进行如下仪式：\\n\\n* 初始时，你有 $x$ 个“0 级火星”。\\n* 允许重复执行操作：选择某个等级 $t\\\\ge 0$，若当前存在 **恰好 $B$ 个 $t$ 级火星**，则把这 $B$ 个 $t$ 级火星合并为 **1 个 $(t+1)$ 级火星**。\\n* 当无法继续合并时停止。\\n\\n将停止时各等级火星的个数记为一个序列（按等级从小到大排列），称为 $x$ 的**纹样**，记作 $\\\\operatorname{Pat}(x)$。\\n\\n题目保证：无论合并操作执行顺序如何，最终得到的 $\\\\operatorname{Pat}(x)$ 都相同（即纹样是良定义的）。\\n\\n定义：\\n$$\\ng(x)=\\\\text{纹样中火星总数}=\\\\sum_{t\\\\ge 0}\\\\operatorname{Pat}(x)_t .\\n$$\\n\\n\\n称两个数 $x,y$ **相印** 当且仅当 $\\\\operatorname{Pat}(x)=\\\\operatorname{Pat}(y)$。\\n\\n给定序列 $a_1,\\\\dots,a_n$，如果相邻两项 $a_i,a_{i+1}$ 相印，则它们会被自动扎在同一束中。\\n一束定义为按此规则得到的一个**极大连续区间**（不能再向左右扩展）。\\n\\n你有 $m$ 张封条，第 $j$ 张覆盖区间 $[L_j,R_j]$，按顺序执行。\\n\\n执行第 $j$ 张封条时：\\n\\n* 对当前所有束中，满足“该束区间 $[l,r]$ 完全落在封条内”，即 $L_j\\\\le l$ 且 $r\\\\le R_j$ 的束：\\n\\n * 将这整束内所有位置的值 $a_k$ 统一替换为 $g(a_k)$。\\n* 执行完替换后，按“相印”规则重新自动扎绳成束（可能发生合并）。\\n\\n记执行前 $t$ 张封条后的序列为 $a^{(t)}$（$t=0$ 表示不执行任何封条）。\\n\\n### 4) 询问：最早满足预算\\n\\n共有 $q$ 个询问，第 $i$ 个询问给出 $(l_i,r_i,S_i)$。你需要输出最小的 $t\\\\in[0,m]$ 使得\\n\\n$$\\n\\\\sum_{k=l_i}^{r_i} a^{(t)}_k \\\\le S_i.\\n$$\\n\\n若不存在这样的 $t$，输出 $-1$。\\n\\n\\n## 输入格式\\n\\n第一行三个整数 $n,m,q$。\\n\\n第二行 $n$ 个整数 $a_1,\\\\dots,a_n$。\\n\\n接下来 $m$ 行，每行两个整数 $L_j,R_j$。\\n\\n接下来 $q$ 行，每行三个整数 $l_i,r_i,S_i$。\\n\\n\\n## 输出格式\\n\\n输出共 $q$ 行，每行一个整数，表示对应询问的答案；若不存在则输出 $-1$。\\n\\n\\n```input1\\n6 3 4\\n2026 2026 5 4052 4052 2027\\n1 5\\n2 6\\n3 4\\n1 6 10000\\n1 5 20\\n3 6 10\\n4 6 6\\n```\\n\\n```output1\\n1\\n1\\n-1\\n2\\n```\\n\\n\\n## 数据范围\\n\\n对于 $10\\\\%$ 的测试数据，$n,m,q\\\\le 3000$。\\n\\n对于另 $20\\\\%$ 的测试数据，$n,m,q\\\\le 10^5$，且每次封条区间 $[L_j,R_j]$ 都恰好对齐束边界（不会切开任何束）。\\n\\n对于 $100\\\\%$ 的测试数据：\\n\\n* $1\\\\le n,m,q\\\\le 10^5$\\n* $0\\\\le a_i\\\\le 10^{18}$\\n* $1\\\\le L_j\\\\le R_j\\\\le n$\\n* $1\\\\le l_i\\\\le r_i\\\\le n$\\n* $0\\\\le S_i\\\\le 10^{18}$\\n\\n\

统计

递交统计

拾柒的元旦封条

信息

还没有账户？

登录