2024-07-22 10:05:57
发布于：北京
万能头文件:
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
算法的特性：
1.有穷性
2.确定性
3.可行性
4.零个或多个输入
5.一个或多个输出
#可能没有输入但一定有输出
时间复杂度&空间复杂度
时间复杂度：
衡量效率或速度 t(n)
可以用O(n)来表示T(n)
这种方法被称为大O表示法
修改后的时间频度函数只保留最高阶
O(n*n)为平方阶复杂度
eg:
O(1)常数时间
O(logN)对数时间
O(N)线性时间
O(NlogN)对数线性时间
O(NN)二次时间
O(NN*N)三次时间
O(2的N次方）指数时间
O(N!)阶乘时间
c++一秒钟10的八次方
互动｜「寒假生存实录」开播中！
🌟「寒假生存实录」开播中！ 寒假模式已启动！你的生活主页面，从【教室】切换到了哪里？ 是燃系励志番、日常搞笑番，还是“摆烂”治愈番？ 这个假期，#寒假生存实录# 专属频道持续开放！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📮 参与指南：两种方式，任你选择 🎬 方式一：评论打卡 · 速记名场面** 懒得开新帖？直接在 本帖评论区，用一句话或一张图，晒出你当日的“高光/崩坏瞬间”。 📖 方式二：深度连载 · 开启个人剧集** 欢迎 单独发帖，进行连载或深度记录。只需： 1. 在讨论区发布帖子； 2. 在 帖子标题开头 带上 #寒假生存实录# 话题，即视为成功参演。 ⏰ 放映期间：即日起 ~ 2月28日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 互动奖励 🏆 人气打卡奖（TOP8瓜分奖池） 在 本帖评论区 打卡互动。活动结束后，符合评论要求&点赞数超过20的用户，将共同瓜分2016罐头！ ✨ 深度连载奖（优质内容激励） 在讨论区发表 #寒假生存实录# 主题的深度帖子。我们将根据内容的真实性、趣味性和故事性，评选出优质连载，送出稀有道具 「AC之神的祝福」 一张！ 🍀 随机幸运奖（全员参与抽奖） 所有有效参与者（包含评论打卡与发帖连载），均自动加入抽奖池！我们将随机抽取10位幸运儿，每人赠送 「昵称变色卡」 道具一张！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题 你的寒假日常，就是最真实的原创剧集。 快在评论区抛出你的“今日更新”，或开启你的专属连载吧！期待看到你的精彩“放映”。🎉
#寒假生存实录#「失败/成功-我的成绩」
️ 🏷️本集标题： 「失败/成功-我的成绩」 ⚠分数： 学科 分数 成绩 最高分 排名 语文 100 92 97 NO.5-NO.10 数学 100 100 100 NO.1 英语 100 94 100 NO.5-NO.10 科学 100 100 100 NO.1 ✌总分： 总分 班级排名 386 NO.5 班级最高分： 分数 昵称（不透露真实姓名） 395 @BUG_花批（围观他的主页） 🎵氛围BGM： 紧张气氛 📈能量值之表： 时间 能量值 Day-1（期末考第一天） ▮▮▮▮▮▯➡▮▮▮▯▯▯➡▮▮▮▮▮▮ Day-1（期末考第一天） ▮▮▮▮▮▮➡▮▮▮▮▮▮➡▮▮▮▮▮▮ Day-3（期末考结束第一天） ▮▮▮▮▮▮➡▮▮▮▮▯▯➡▮▮▯▯▯▯ Day-4（期末考结束第二天） ▮▮▮▮▮▮➡▮▮▮▮▮▮（附加▮▮）➡▮▮▮▮▮▯ Day-5（期末考结束第三天） ▮▮▮▮▯➡▮▮▮▮▮▮（附加▮）➡▮▮▮▮▮▯ Day-6（期末考结束第四天） ▮▮▮▮▮▮（附加▮▮）▮▮▮▮▮▯➡▮▮▮▮▮▯ 🎮主线任务进展： 寒假作业： 时间 进度 Day-1（期末考第一天） / Day-2（期末考第二天） 20% Day-3（期末考结束第一天） 50% Day-4（期末考结束第二天） 98% Day-5（期末考结束第三天） 100% 也是在Day-5（期末考结束第三天）完成了寒假作业！ 🏂寒假日记（前方高能） Day−1:{\normalsize Day-1:}Day−1: 8:00~12:00:语文考试，感觉良好，但有一题写了”毛主席万岁“&”中华人民共和国万岁“也是929292分非常不好吧 1:00~3:00:英语考试，感觉良好，后面才知道作文要有格式（题目没说要格式！）也是949494分好吧，直接考砸，起飞！ Day−2:{\normalsize Day-2:}Day−2: 8:00~12:00:数学考试，感觉非常肥肠nice，随便乱写，也是100100100分好吧 1:00~3:00:科学考试，感觉良好，有一题目问腕关节则么运动：也是一直在那绕手腕好吧，100100100分照样拿下 Day−3:{\normalsize Day-3:}Day−3: 1:00~4:00:没啥感觉，出分数时炸毛了，呜呜呜 Day−4:{\normalsize Day-4:}Day−4: 1:00~4:00:上香炉峰，扔雪球，快乐一天 Day−5:{\normalsize Day-5:}Day−5: 12:00~3:00:中午喝奶茶，吃云吞（云吞加太多醋不好吃），虽然云吞加太多醋了，但味道也是肥肠的nicenicenice!! Day−6:{\normalsize Day-6:}Day−6: 一天:直接赚爆，入账130￥ ⚡ 突发副本： 罐头：（每日记录）罐头：（每日记录）罐头：（每日记录） 时间 事件 Day-1（期末考第一天） 当”赌神 · 皮尔 · 卡松“失败，亏本400+罐头 Day-2（期末考第二天） 当”赌神 · 皮尔 · 卡松“成功，赚200+罐头 （没回本），数学期末考试有人睡觉睡着了 Day-3（期末考结束第一天） 当”赌神 · 皮尔 · 卡松“再次失败，亏本50+罐头 （但比一开始200个罐头好多了） Day-4（期末考结束第二天） 当”赌神 · 皮尔 · 卡松“照样失败，亏本133罐头 习以为常 Day-5（期末考结束第三天） 当”赌神 · 皮尔 · 卡松“失败，亏本133罐头 Day-6（期末考结束第四天） 当”赌神 · 皮尔 · 卡松“成功，直接1144罐头 其他：（非每日记录）其他：（非每日记录）其他：（非每日记录） 时间 事件 Day-4（期末考结束第二天） 一书包零食，给班主任看蒙蔽了！哈哈哈 😎高光/崩坏时刻： 时间 具体事件 Day-1（期末考第一天） 脑抽忘记语文“日积月累”不会，写了”毛主席万岁“&”中华人民共和国万岁“ Day-2（期末考第二天） 闲的没事干去找@BUG_花批玩，没想到刚考的科学分数100分！！！！！ （上次期末89分） Day-3（期末考结束第一天） 数学100分，曾在各科老师前发誓考不到100分倒立**，不用吃qwq,哈哈哈 Day-4（期末考结束第二天） 香炉峰，山顶打雪仗（对屋顶砸）（此处附加选项（2025/12/17）@BUG_花批宣读当乐子感言） Day-5（期末考结束第三天） 开王者荣耀没想到……我爸深藏不露有电玩小子……高贵皮肤！ Day-5（期末考结束第三天） 突然发现Aler这小子小号，大号都封了 我真棒——EMO……中 ️ 🗣️经典台词： * 死手快写，死脑快想（emo……） * 疯子何尝不是另类的天才？ 💥彩蛋： * 数学100分，曾在各科老师前发誓考不到100分倒立**，不用吃qwq,哈哈哈（选自 高光/崩坏时刻-Day-3） @人时间到 @ppl_帅童（92134） @Daquavis MC @cjj(不加团) @BUG_花批 @༺དༀ༒∞░∞༒ༀཌ༻（不加团） @huangze @墨白渊作者本人 @昌振兴 @dream92143 @༺ཌༀཉི༒白·羊༒༃ༀད༻ @朱朗枫 @Gragher（不敢@怕被喷） 亿个小小建议链接描述
#寒假生存实录#寒假日记
致谢:不会C++的noah 灵感来源。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 期末日期:upd at 2026.2.4~5 DAY -开学第一天 交作业... .... DAY -114514....7891114514....7891114514....7891 DAY -SIN2XSIN^2XSIN2X 简单考一次数学 尝试拿满分awa 哈哈《满分》，用了我42min42min42min,真简单难 等待考试结果 ... ... ... ... .... 6，考了一般，屁股得烧红了qwq 寻找ACGO遗留的NOI小题... 水了几题 可恶，被神秘入嘲讽了 sleeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeep DAY -∞∞∞ 早上去了麦当当吃了美味的食物，happy! 中午的饭...难评 > 学习语文ing... 冲向理科高地，猛攻！！！ 我们班有几个入因为讨论三角洲然后被我们“善良”的牢湿狙击了 作业越来越多... 疯狂写作业中...流口水 最后一节课是体育课，我们班为了夺取体育课，我们派出了数学课代表和一大坨同学，结果全军覆没 我们班的同学现状: > 哈...数学....6...**** DAY −∞+1-∞+1−∞+1 作业好多,被迫学习，学习，学习，学习，学习，学习，学习，学习，学习，学习，学习，学习.... 我还是太可怜了awa 挑战洛谷的水题 DAY -∞+X∞+X∞+X 今天遇到一位小孩哥，他善良的说我跨楼梯，我直接白了一眼，但他太善良了，用它的爪子抓住了我的书包， 我只是轻轻地抚摸了一下，他就被我抽倒在地，眼睛直接飞了出去，然后有另外一个shazi叫来了一小坨蒟蒻， 我直接跟他进行了友好的交流， 他就吓哭了 能怪我吗？ DAY -6 日常生活，切了几道水题 DAY -5 想象着寒假的美好生活awa 我想的:美味的零食、美好的电脑、美好的旅行、美好的... 实际上:无穷无尽的作业、数不胜数的培训班... 落差好大啊! 水了一下ACGO的灌水池塘... DAY -4 正常的一天... RP++; 心中暗自乞讨分数 : ) DAY -3 也是在家中熬夜复习了一遍语文书qwq 看了91min91min91min,实际上只有67min67min67min才是真正的复习时间 我想考好啊... 祖宗保佑啊啊啊 爆切洛谷比赛，勉强拿下865865865分 DAY -2 上午烤语文,下午烤英语 语文烤试是9:009:009:00~10:4010:4010:40，时间还算充裕，勉强能写。 语文试卷一发下来直接大脑爆炸了，一道课外的古诗词题硬控我50min50min50min,演都不演了. 考试中: 8:55:拿到试卷，我去怎么题目这么多，有诈。 8:56:看到一道古诗词的题目，”课外积累:__________,___________“？有点难绷，想想想，想不出来，待会随便套一个吧 【基础】完成度：0，思考时间：2min 【现代文】完成度：0，思考时间：0min 【非联】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：0min 8:59:欸不是我怎么忘了古诗词格式怎么写了，得完了，QWQ。 9:00~9:19:闪击基础，除了那个课外积累别的没有了，还是easy 【基础】完成度：100，思考时间：18min 【现代文】完成度：0，思考时间：0min 【非联】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 9:20~9:26:看看现代文，”穿越大草地“？猎奇，什么玩意？？？，但不多，还能做（不知道有没有伏笔） 看眼时间，WC怎么只剩1h22min了，我还要留50min写作文，赶紧写写写。 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：6min 【非连】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 什么玩意，太猎奇了，思考3min,无果，跳跳跳，要没时间了。 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：23min 【非连】完成度：95，思考时间：11min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 9:50~10:05:什么玩意文言文还要写200字小作文？赶紧跳跳跳去写大作文吧 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：23min 【非连】完成度：95，思考时间：11min 【文言文】完成度：70，思考时间：15min 【作文】完成度：0，思考时间：2min 考完对答案选择题全对，古文也是轻松全对，但是阅读就错了一堆...希望上909090 考完直接一阵狂吃，然后狂泻,然后复习英语 中午的食物一般，还是沙威玛好呲 > 下午烤英语，有的紧张 > 英语试卷刚刚发下来，用了2s2s2s扫视了整张试卷，应该ok。用了几十分钟写完. > 跟别的入核对答案ing...幸好幸好...英语还好，起码没扣几分。 考试ing... 1:59:59拿到卷子 用3s3s3s看完题目,还挺简单的 【听力】完成度：0，思考时间：0min 【基础】完成度：0，思考时间：0min 【阅读】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：0min 几分钟后... 什么玩意？这个图片好像似曾相识啊...是AI画的... ???让我写豆包？？？？****猎奇 【听力】完成度：100，思考时间：10min 【基础】完成度：100，思考时间：5min 【阅读】完成度：91，思考时间：13min 【作文】完成度：0，思考时间：0min 然后我们班有人打喷嚏像喇叭一样，啊哈哈哈哈，笑死我嘞. 完了，我忘记格式怎么写了，快动脑子啊啊啊 【听力】完成度：100，思考时间：10min 【基础】完成度：100，思考时间：5min 【阅读】完成度：100，思考时间：19min 【作文】完成度：99，思考时间：7min 想不出来了QWQ 哦！！！！我想到了，哈哈哈哈哈哈笑抽笑抽 希望明天的数学和科学能考好，保佑我啊啊QWQ 今晚想要尝试ABC 傲...好困期待明天，睡了... DAY -1 考的数学也都是肥肠的简单啊，期待明天 ButBUtBUT!!! 我数学错了一道111分的题目，气死我也！！！ 科学也就十几分钟写完了好吧嘻嘻嘻 可恶，有道题目给我卡了6min6min6min,脑袋要爆炸了awa 熬夜通宵的看电视 爽! \Huge 爽!~爽! 写作业................ 呜呜呜，我不想写作业啊啊啊(哈哈，我要写完了！((( 谁能帮我写寒假作业？ 今晚ABC好吧 不行了，我完CSGO匹配到了一群猪队友，我搁那口吐国粹，他们搁那卡住了，我直接蚌主了 DAY 0 嗯？ DAY 1 哈哈，洛谷大吉 早饭呲了一堆乱七八糟的食物... 写作业ing... 自己预估的成绩: 语文 数学 英语 科学 总分 考前预估 96 100 93 98 387 考后 92 100 92 97 381 实际上 -- -- -- -- -- 哎，买祝福真的需谨慎，千万不要乱贝者 啊 经过我的不懈努力，终于学会了截图QAQ 细节这一坨全是棕名 细节我绍兴一中的排名被轰炸到47了呜呜呜 发现一道可怜的黄题，肝到CE 啊啊啊啊，可恶 * 肝到黄题，卡了 * 肝到绿题，没了 不！！！！ 今日战绩: * AK P1493、P1498、P1477、P1469 * 70分:P1465、P1863、P1873 * 30分:P2028 * 10分:P3615 * 0分:P4026 这把肯定估值暴涨 被吓哭了 出成绩了AWA 语文 数学 英语 科学 总分 考前预估 96 100 93 98 387 考后 92 100 92 97 381 实际上 92 100 96 98 386 * 语文...一般，班级rk6 * 数学正常发挥，简单过百，rk1 * 英语超常发挥，班级rk2 * 科学无敌，班级rk1 去打lg的比赛咯 666，洛谷的那什么比赛没数据点？？？ 打了那么久，样例对了，结果输出直接UKE me: 链接直达比赛 我的思路 : [COCI 2025/2026 #4] 僵尸启示录 解题思路 问题理解 我们需要模拟 mmm 个僵尸从僵尸窝出发，沿直线向城市行进的过程： * 城市距离僵尸窝 nnn 米 * 僵尸速度：1米/秒 * 僵尸出发间隔：1秒（第一个僵尸在第1秒初出发） * 在路上有 kkk 个炸弹，每个炸弹有： * 位置 xxx（距离僵尸窝的距离） * 爆炸半径 rrr * 放置时刻 ttt（秒末） 当炸弹在时刻 ttt 放置在位置 xxx 时，会炸死该时刻位于 [x−r,x+r][x-r, x+r][x−r,x+r] 范围内的所有僵尸。 关键观察 1. 僵尸移动规律： * 第 iii 个僵尸在第 iii 秒初出发 * 在第 ttt 秒末，第 iii 个僵尸的位置为： * 如果 t<it < it<i：还在僵尸窝（位置为0） * 否则：位置为 min(t−i+1,n)\min(t-i+1, n)min(t−i+1,n) 2. 时间范围： * 最后一个僵尸（第 mmm 个）最晚在第 mmm 秒出发 * 到达城市需要 nnn 秒移动时间 * 最晚在第 m+nm+nm+n 秒末可能到达 * 炸弹时间 t≤500t \le 500t≤500，题目保证足够 3. 问题规模： * n,m,k≤200n, m, k \le 200n,m,k≤200，暴力模拟可行 时间复杂度：O(m×(m+n)×k)O(m \times (m+n) \times k)O(m×(m+n)×k)，最大约 200×400×200=1.6×107200 \times 400 \times 200 = 1.6 \times 10^7200×400×200=1.6×107，可行。 起码我是这么想的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 可怜的洛谷讨论区： 到了下午： 小小的本蒟蒻开始学习 报名了尼谷的课程，然后吃起了香香的泡面 开始刷题了QAQ e...好难啊 尝试卡常,好消息，前几个样例直接变成了绿色，最后一个TLE了 666，我的好心情瞬间消失一般 卡了几十次，电脑要卡废了，还是TLE 好消息：不是TLE！ 坏消息：是RE... 翻翻洛谷的陶片放逐： 666贴脸开大 因为有些过于猎奇我还是不放了 em... 接着刷题ing... DAY 2 嗯。 洛谷中平，还行 勉强能过。 随便呲几口面当早餐QAQ 下午还要返校。。。 回来了qwq,赚大了哈哈哈哈，学校里的积分直接718，唔哈哈哈 为什么你们不点赞了吗QAQ 我写的不好吗？ 好吧，把自己的评论放在下面，我有可能会把你挂在评论墙上: name say/problem Why DAY 3 哈 洛谷大凶 上午编程课啊啊啊 下午上奥数qwq 晚上还要英语课 呜呜呜，我好可怜啊 只能晚上更了... 加油啊啊啊，可怜的我 昨晚ABC忘说了,烂的一匹 今晚刷题 顺便开个盲盒 亏大了... 回来了em.... DAY 4 刚刚上完编程课，下午还有奥数课... 要连续上444天 今晚AWC DAY 5 发了AWC题解，然后开罐头赚了2发399，一发199，亏了133+100 QAQ，可怜的我下午还有奥数课...啊啊啊呜呜呜 我不想上啊啊啊 打了会儿州，跟老太对狙，护甲直接打爆了 玩了会儿MC，下了个亡者世界+畸变+光影+咆哮者+随机BOSS直接一个大洪水给我KO了 呜呜呜，我的钻石啊啊啊，我的护甲啊啊啊 还好没亏多少qwq
#创作计划#莫比乌斯反演
头图 补充说明左边是一个同班的（五年级）同学 @你好。 正文 本人来随便学点高级数论 （其实是乱翻《算法竞赛》），有错轻喷。 莫比乌斯函数 μ(n)={1n=1(−1)kn 是 k 个不同质数的乘积0n 含有平方因子\mu(n)= \begin{cases} 1 & n=1 \\\\ (-1)^k & n\text{ 是 }k\text{ 个不同质数的乘积} \\\\ 0 & n\text{ 含有平方因子} \end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n 是 k 个不同质数的乘积n 含有平方因子 即： * 只要有 p2∣np^2 \mid np2∣n，就有 μ(n)=0\mu(n)=0μ(n)=0。 * 若 n=p1p2⋯pkn=p_1p_2\cdots p_kn=p1 p2 ⋯pk （pip_ipi 都是质数且所有数互不相同），则 μ(n)=(−1)k\mu(n)=(-1)^kμ(n)=(−1)k。 计算 因为莫比乌斯函数是积性函数（即 f(1)=1f(1) =1f(1)=1 且在 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1 的情况下有 f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)），所以可以用在 O(n)O(n)O(n) 时间内预处理出所有 [1,n][1,n][1,n] 内的莫比乌斯函数值。 [1] 质数的 μμμ 为 −1-1−1。 [2] 如果一个数存在某个质因子的指数大于 111，那么它的 μμμ 值为 000 。 * 值得注意的是，只有当数存在最小质因子的指数大于 111 时，才会被直接筛为 000 * 其他情况则由公式 μ(d)=−μ(i)\mu(d)=-\mu(i)μ(d)=−μ(i) 完成，其中 ddd 是当前数，iii 是某个小于 ddd 的数 这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。 示例 Python 代码： 基础恒等式 这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。 ∑d∣nμ(d)={1n=10n>1\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases} d∣n∑ μ(d)=⎩⎨⎧ 10 n=1n>1 莫比乌斯反演 根据上方恒等式，可推出若两个函数满足： g(n)=∑d∣nf(d)g(n)=\sum_{d\mid n} f(d) g(n)=d∣n∑ f(d) 则有： f(n)=∑d∣nμ(d) g (nd)f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right) f(n)=d∣n∑ μ(d)g(dn ) 莫比乌斯反演例子 欧拉函数 已知： n=∑d∣nφ(d)n = \sum_{d\mid n} \varphi(d) n=d∣n∑ φ(d) 反演得： φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d} φ(n)=d∣n∑ μ(d)dn 统计互质对数 ∑i=1n∑j=1n[gcd(i,j)=1]=∑d=1nμ(d)⌊nd⌋2\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=1] = \sum_{d=1}^n \mu(d)\left\lfloor \frac{n}{d}\right\rfloor^2 i=1∑n j=1∑n [gcd(i,j)=1]=d=1∑n μ(d)⌊dn ⌋2 莫比乌斯反演例题 P2522 题目求的是 ∑i=xn∑j=ym[gcd(i,j)=k]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) = k]∑i=xn ∑j=ym [gcd(i,j)=k]，简单的类似二维前缀和的方法优化式子，然后消掉 kkk 变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ [gcd(i,j)=1]。 再变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ ∑d∣gcd(i,j) μ(d)。 接下来交换求和顺序，在上述式子中，如果 ddd 要被枚举到，显然需要当且仅当 d∣id∣id∣i 并且 d∣jd∣jd∣j。所以把这个部分计入到贡献当中： ∑dμ(d)∑i=1⌊nk⌋[d ∣ i]∑j=1⌊mk⌋[d ∣ j]\sum_d \mu(d) \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} [d \space | \space i] \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor } [d \space | \space j] d∑ μ(d)i=1∑⌊kn ⌋ [d ∣ i]j=1∑⌊km ⌋ [d ∣ j] 最后化简： ∑dμ(d)⌊ndk⌋⌊mdk⌋\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 O(n)O(\sqrt n)O(n ) 的复杂度求解。 P2257 题目求的是 ∑i=xn∑j=ym[gcd(i,j)∈Prime]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) \in \text{Prime}]∑i=xn ∑j=ym [gcd(i,j)∈Prime]。 按照 P2522 的套路变为： ∑k∈Prime∑dμ(d)⌊ndk⌋⌊mdk⌋\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor k∈Prime∑ d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 发现过不了。 观察到复杂度高的原因是双求和导致的，并且 dkdkdk 重复出现了，所以可以令 T=dkT = dkT=dk。接下来，先枚举 TTT，显然 T≤min(n,m)T \le \min(n,m)T≤min(n,m)。先把后面的那个部分写下来。再考虑会有多少的 μ()μ()μ() 会加在这个部分上。我们要让求的和的值等价不变，由于 d=T÷kd = T \div kd=T÷k，所以： ∑T=1min(n,m)⌊nT⌋⌊mT⌋∑k∣T,k∈Primeμ(Tk)\sum _{T=1} ^{\min(n,m)} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum _{k | T,k \in \text{Prime}} \mu (\dfrac{T}{k}) T=1∑min(n,m) ⌊Tn ⌋⌊Tm ⌋k∣T,k∈Prime∑ μ(kT ) 发现后面那个部分跟 n,mn,mn,m 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。 注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。 我的这份 Python 代码由于语言本身较慢所以是无法通过的。 应该不会有人第一遍就发现代码里的小彩蛋。
#寒假生存实录#寒假日记
null
【学习笔记】拉格朗日插值入门
同步发布于 我的 cnblogs 这篇应该比较简单（） LAGRANGE 插值 > 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi ,yi ) 满足 xi≠xjx_i\neq x_jxi =xj ，可以唯一确定一个 n−1n-1n−1 次多项式 y=f(x)y=f(x)y=f(x) 过上述所有 nnn 个点。 > > 现在给出 kkk，求 f(k)f(k)f(k) 的值。 一个简单的想法是直接 Gauss 消元，可以 O(n3)O(n^3)O(n3) 解出这个 n−1n-1n−1 次多项式每一项的系数。 这里介绍一下用 Lagrange 插值的解法： * 构造 nnn 个函数 fi(x)f_i(x)fi (x) 表示该函数过点 (xi,yi)(x_i,y_i)(xi ,yi )，对于任意 j≠ij\neq ij=i 都过点 (xj,0)(x_j,0)(xj ,0)。容易发现令 f(x)=∑i=1nfi(x)f(x)=\sum\limits_{i=1}^nf_i(x)f(x)=i=1∑n fi (x) 就可以得到一个满足条件的函数 f(x)f(x)f(x)。 * 然后考虑构造因式分解：对于每个 fi(x)f_i(x)fi (x) 多项式构造一项 x−xj(i≠j)x-x_j(i\neq j)x−xj (i=j)，然后凑一个系数 aia_iai 满足 fi(xi)=yif_i(x_i)=y_ifi (xi )=yi ，容易解方程得到 ai=yi∏j≠i(xi−xj)a_i=\dfrac{y_i}{\prod\limits_{j\neq i}(x_i-x_j)}ai =j=i∏ (xi −xj )yi 。 * 于是有：f(k)=∑i=1nfi(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k)=\sum\limits_{i=1}^nf_i(k)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}f(k)=i=1∑n fi (k)=i=1∑n yi j=i∏ xi −xj k−xj ，可以在 O(n2)O(n^2)O(n2) 的时间复杂度内求解。 :::success[O(n2logn)O(n^2\log n)O(n2logn) 解法] ::: :::success[O(n2)O(n^2)O(n2) 解法] ::: 001. P5667 拉格朗日插值2 根据上面的理论，容易得到： f(m+k)=∑i=0nyi∏j≠im+k−ji−jf(m+k)=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j} f(m+k)=i=0∑n yi j=i∏ i−jm+k−j 可以 O(n2)O(n^2)O(n2) 时间复杂度求解。 考虑对这个东西进行优化。注意到 kkk 的取值是连续的一段，所以从这里突破： f(m+k)=∑i=0nyi∏j≠im+k−ji−j=∑i=0nyi∏j≠i(m+k−j)∏j≠i1i−j=∑i=0nyi(m+k)!(m+k−n−1)!(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0nyi(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0n[1i!×yi×(−1)n−i1(n−i)!]×1m+k−i\begin{aligned} f(m+k) &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j}\\ &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}(m+k-j)\prod\limits_{j\neq i}\frac1{i-j}\\ &=\sum\limits_{i=0}^ny_i\frac{(m+k)!}{(m+k-n-1)!}(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^n\left[\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!}\right]\times \frac1{m+k-i} \end{aligned} f(m+k) =i=0∑n yi j=i∏ i−jm+k−j =i=0∑n yi j=i∏ (m+k−j)j=i∏ i−j1 =i=0∑n yi (m+k−n−1)!(m+k)! (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n yi (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n [i!1 ×yi ×(−1)n−i(n−i)!1 ]×m+k−i1 记 Pi=(m+i)!(m+i−n−1)!,Ai=1i!×yi×(−1)n−i1(n−i)!,Bi=1m+iP_i=\frac{(m+i)!}{(m+i-n-1)!},A_i=\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!},B_i=\frac1{m+i}Pi =(m+i−n−1)!(m+i)! ,Ai =i!1 ×yi ×(−1)n−i(n−i)!1 ,Bi =m+i1 ，则可以用 NTT 求出 C=A⊙BC=A\odot BC=A⊙B 即 CCC 为 A,BA,BA,B 两个序列的等差卷积，而 PiP_iPi 显然可以线性递推。 但是这真的对吗？？？把卷积形式写出来之后发现其形如：Ck=∑iAiBk−iC_k=\sum\limits_iA_iB_{k-i}Ck =i∑ Ai Bk−i （0≤i≤n0\le i\le n0≤i≤n），这怎么还出来负数下标了（）不过解决这个问题也是简单的，重新记 Bi=1m+i−nB_i=\frac1{m+i-n}Bi =m+i−n1 ，此时有 Cn+k=∑i=0nAiBn+k−iC_{n+k}=\sum\limits_{i=0}^nA_iB_{n+k-i}Cn+k =i=0∑n Ai Bn+k−i ，将其写成卷积的形式只需要对所有 i>ni>ni>n 都记 Ai=0A_i=0Ai =0 就可以扩展为 Cn+k=∑i=0n+kAiBn+k−iC_{n+k}=\sum\limits_{i=0}^{n+k}A_iB_{n+k-i}Cn+k =i=0∑n+k Ai Bn+k−i 的形式。 一次 NTT 卷积即可求出 C=A⊙BC=A\odot BC=A⊙B 这个等差卷积。 因此总时间复杂度为 O(nlogn+m)O(n\log n+m)O(nlogn+m)，分段打表阶乘可以把后面的 O(m)O(m)O(m) 省去。 跑了 973ms，喜提最劣解（没事至少这个能过） :::success[Code] ::: 006. CF622F THE SUM OF THE K-TH POWERS 通过作差可以发现答案是一个 k+1k+1k+1 次多项式的形式，因此想到 Lagrange 插值。将 xi=ix_i=ixi =i（0≤i≤n0\le i\le n0≤i≤n）带入，有： ∑i=0nyi∏j≠ix−ji−j=∑i=0nyi(∏j=0i−1x−ji−j∏j=i+1nx−ji−j)=∑i=0nyi(∏j=0i−1(x−j)∏j=i+1n(x−j)∏j=0i−11i−j∏j=i+1n1i−j)=∑i=0nyi(−1)n−i1x!1(n−x+2)!∏j=0i+1(x−j)∏j=i+1n(x−j)\begin{aligned} &\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{x-j}{i-j}\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}\frac{x-j}{i-j}\prod\limits_{j=i+1}^n\frac{x-j}{i-j})\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}(x-j)\prod\limits_{j=i+1}^n(x-j)\prod\limits_{j=0}^{i-1}\frac1{i-j}\prod\limits_{j=i+1}^n\frac1{i-j})\\ =&\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{x!}\frac1{(n-x+2)!}\prod\limits_{j=0}^{i+1}(x-j)\prod\limits_{j=i+1}^n(x-j) \end{aligned} === i=0∑n yi j=i∏ i−jx−j i=0∑n yi (j=0∏i−1 i−jx−j j=i+1∏n i−jx−j )i=0∑n yi (j=0∏i−1 (x−j)j=i+1∏n (x−j)j=0∏i−1 i−j1 j=i+1∏n i−j1 )i=0∑n yi (−1)n−ix!1 (n−x+2)!1 j=0∏i+1 (x−j)j=i+1∏n (x−j) 后面这两个 ∏\prod∏ 一看就很能预处理，而前面的显然可以直接算。时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。注意到 iki^kik 是积性函数，所以使用线性筛可以将其优化至严格 O(n)O(n)O(n) 求解。 007. P4593 [TJOI2018] 教科书般的亵渎 设 S(n,k)=∑i=1nikS(n,k)=\sum\limits_{i=1}^ni^kS(n,k)=i=1∑n ik，则容易观察到该题要求的答案为：∑i=0mS(n−ai,m+1)+∑i=0m∑j=i+1m(aj−ai)m+1\sum\limits_{i=0}^mS(n-a_i,m+1)+\sum\limits_{i=0}^m\sum\limits_{j=i+1}^m(a_j-a_i)^{m+1}i=0∑m S(n−ai ,m+1)+i=0∑m j=i+1∑m (aj −ai )m+1。后半部分可以暴力快速幂求解，而前半部分是 CF622F，直接套用上面的公式求解即可。
AC罐头商店使用说明
AC罐头商店 使用说明 💰 一、罐头获取方式 刷题赚罐头 🎯 获取方式 罐头奖励 说明 攻克新题 1-7罐头/题 每成功攻克一道自己未AC的官方题目，根据题目难度获得罐头：• 入门：1罐头；• 普及-：2罐头；普及/提高-：3罐头；• 普及+/提高：4罐头；• 提高+/省选：5罐头；• NOI/CTSC级别：7罐头；每日上限：5题（即每日最多通过5道新题获得罐头） 题目首杀 5-35罐头/题 首位攻破“零通过”的官方题目，根据题目难度获得• 入门：5罐头；• 普及-：10罐头；• 普及/提高-：15罐头• 普及+/提高：20罐；• 提高+/省选：25罐头；• NOI/CTSC级别：35罐头 ；每日上限：5题（即每日最多通过5道首杀获得罐头） 首次竞赛报名 20罐头 用户第一次报名ACGO的官方竞赛时获得 排位等级晋升 100-800罐头/级 排位等级从上一级晋升到下一级时获得（每个等级仅奖励一次）：• 青铜→白银：100罐头；• 白银→黄金：200罐头；• 黄金→铂金：300罐头；• 铂金→钻石：400罐头；• 钻石→大师：600罐头；• 大师→王者：800罐头 天梯闯关过关 1-200罐头/关 每通过一关天梯闯关即可获得罐头，奖励金额随关卡难度递增，具体以关卡实际显示为准 活跃赚罐头 🎪 获取方式 罐头奖励 每日上限 每日点赞 1罐头/次 5次（5罐头） 每日评论 1罐头/次 5次（5罐头） 每日收藏题单 1罐头/次 5次（5罐头） 帖子被点赞 1罐头/次 10次（10罐头） 题单被收藏 5罐头/次 10次（50罐头） 每日活跃罐头上限：75罐头（5+5+5+10+50） 运营与贡献 🏆 获取方式 罐头奖励 说明 管理员手动发放 50-5000罐头 适用于以下场景：• 参与各类赛事并按赛事规则分配奖励；• 贡献优质题解、技术分享等内容被官方采纳；• 为社区发展提供特殊贡献等 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⏰ 二、罐头过期说明 滚动过期规则 AC罐头采用 【滚动过期】 方式管理： 1. 过期时间：每个自然年年底（12月31日23:59） 2. 过期范围：上一个年度获得且未消耗的罐头 3. 过期示例： * 2024年获得的罐头，将在2025年12月31日23:59过期 * 2025年获得的罐头，将在2026年12月31日23:59过期 * 以此类推... 过期提醒服务 * 提醒时间：每年12月1日开始 * 提醒方式： * 站内信通知 * 平台置顶帖子公告 * 提醒内容：“您有XXX罐头即将在12月31日到期，请尽快兑换！” 过期应对策略 1. 及时消费：不要过度囤积罐头，看到心仪商品及时兑换 2. 年度规划：每年11月开始规划罐头使用，避免年底过期浪费 3. 关注提醒：每年12月注意查看站内信和公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 三、重要提醒 1. 罐头与账号绑定，不可转让、不可交易 2. 商品一经使用，概不退换，请确认后再购买 3. 请合理安排罐头使用计划，避免过期造成浪费 每年年底记得清空旧罐头，迎接新一年的赚罐头之旅！ 🎉
#寒假生存实录#寒假日记
本文不知道是不是但是好像和优先队列的文章同步更新捏。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY-2 早上考语下午考数 早上 999 点到 111111 点半 考语文，当时看到卷子直接吓哭了。就我这个作文水平百分百语文烤焦，当时作文背了几篇但是很幸运的，没考到。808080 稳了。 考完对答案选择题错 222 幸运的扣 666 分捏，666 分不多有扣 181818 的捏 下午 222 点半 到 444 点半 考数学，数学属于主场优势了哈。但是考完之后依然吓哭。填空的不定项选择选错 111 项掉。大题 m=1m=1m=1 写成 m=−1m=-1m=−1 掉。班任说大概掉 555 分。勉强可以接受。 考完之后朋友发烧了，甲流给我吓哭了（每天和他贴脸讲话互喷口水抢他碗里饭菜的）。 晚上回寝室复习政史，舍友抱怨历史要是不考论文就好了，然后另外一个舍友喷他说你要是不想写论文可以不写，那你就比别人满分少 101010 分就行了捏。 DAY-1 早上 8∼108\sim108∼10 点考政史。政治一直是薄弱学科，开卷考 yyds 闭卷考拉完捏。历史一直还不错。当时试卷发下来的时候一直想看看论文题在哪里然后没找到。后来发现确实没考论文题。 理论上 10:30∼12:0510:30\sim 12:0510:30∼12:05 是复习英语捏，但是我比较懒，于是不想复习，就在那个地方看作文，然后看着看着两眼一黑原地睡着。 然后 121212 点跑到食堂呲东溪。 午休一会下午考英语。英语一直不算很差但是也不好，最后对完答案完型错 111 扣 111 ，阅读错 111 扣 222 ，作文预计扣 3∼43\sim43∼4 反正 110110110 应该稳了。 晚读对答案，晚自习看《魔丸2》和《飞驰人生2》以放松 DAY0 false DAY 1~2 在校 突然意识到这次区里考试收了试卷收了答题卡，估计是不打算出分。我们学校自己改了一遍，办事效率依然高，考完之后第 222 天发成绩。 语 数 英 政 史 All 101/120 115/120 113/120 52/60 58/60 439/480 考完了燃尽了兄弟们。 寝室依旧闹 当时原本说还要补一周课，教育局发力没补。 DAY3~DAY4 周末在尼姑上刷水体，然后在 CXXP 里出点题。去 xmw 上了几节课然后报了尼姑网校。准备这个假期稍稍沉淀下。个人觉得恐惧的球(ScaredQiu)牢湿说话还是好听的。 DAY5 励志要大粪抹墙，寒假能见黄就切，绿要能ctj，已经能切一小部分了捏 收集题目背景 P4514 上帝造题的七分钟 题目背景 裸体就意味着身体。 题目描述 “第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 000 的 n×mn\times mn×m 矩阵。 第二分钟，L 说，要能修改，于是便有了将左上角为 (a,b)(a,b)(a,b)，右下角为 (c,d)(c,d)(c,d) 的一个矩形区域内的全部数字加上一个值的操作。 第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。 第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。 第五分钟，和雪说，要有耐心，于是便有了时间限制。 第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 323232 位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”。 ——《上帝造裸题的七分钟》。 所以这个神圣的任务就交给你了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 清早起来看到水绿 P4136 赶紧做了 早上看洛谷网校做了一橙一黄 上午想试试 NOIPT1 部分分有 70 还可以。在湖北这样的弱省是拿奖的捏。 中午又听了下洛谷网校 P7585 A了 下午 1 点多 尝试今年第四题 P14360 把考场代码又打一遍依旧 40 分 两点多钟和优先队列在比黄题P5266卡常。不知道为什么他卡 8ms 但是好像不对的样子。准备帮他看看但是码风太友好了算了。最终我或许是以\n的优势获胜捏。 下午休息了下 晚上又找优先队列比做题速度这个题单。从 6 点 57 比到 7 点 50 。规则 橙题分数*0.5+黄题分数+绿分数*1.5 策略选错空悲切。 先看到了一个以为很简单的黄，然后磕了20分钟没磕出来。果断放弃。 又看到了一个黄，又以为很简单然后又磕又没磕出来。 果断放弃尝试绿部分分。P7074dp没考虑往上走，20分，快速做出 1 橙。 然后输了@优先队列。 今日战绩： * A掉 P1044 P5266 P7585 B4305 P4136 P11908 P1044 B3843 * 70分 P14635 * 50分 P2678 * 20分 P7074 * CE P1022 吓哭了 DAY6 12 点当赌狗，开了一个 888 一个 199 1 点找黄题+水犇犇 纠结睡不睡午觉捏 睡了。。。 两点半和优先队列一起水找到的题 不知道谁输谁赢 公开赛上首页，然后发布卡 SE 教程 和 jodio，优先队列讨论了一下关于公开赛的事。 今日战绩： * A： P8738 P1115 P2440 P1012 * 0：P1022 P1167 DAY7 今天早上中午下午都很闲。 下午回来炸优先队列 改了下申请出题组的表单 晚上ABC444吃9罚。 罚时大蛇。 rk2420还能涨分我去了 这是我的第三场ABC，应该下次就不会涨很多了。 晚间刷题。 DAY8 励志要开始卷寒假作业不能再颓废下去了，晚点把计划表贴出来 从明天开始执行 DAY9 早上一觉起来 10 点钟 中午和那个甲流的同学一起吃了个饭 下午和那个甲流的同学一起电玩城呆了一下午 写会作业 晚上愉快做题 DAY9 看了下昨晚做了 16 题 早上连开 5 个罐头：66+99+199+399+1999 去找优先队列刷题的时候，他说他要出去玩捏 于是不能歇着，于是：
数状数组/线段树 代码存档
UPDATE: 决定把这个做成较为详细的笔记 UPDATE: 骗你的，做不下去了，只做了树状数组 排版很乱，见谅哈。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.树状数组（BINARY INDEXED TREE,BIT,二叉索引树） 简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。 问题：给出一个数组 {an}\{a_n\}{an }，请在 logn\log{n}logn 的时间复杂度内执行区间修改或区间查询操作。 关于树状数组，我们从一个很聪明的函数讲起： lowbit(x)=x&(−x)\tt{lowbit(x)=x\&(-x)}lowbit(x)=x&(−x) 指 xxx 与 −x-x−x 按位与的结果。 可以发现，当 xxx 是奇数时，lowbit(x)=1\tt{lowbit(x)=1}lowbit(x)=1，反之 lowbit(x)=\tt{lowbit(x)}=lowbit(x)= 二进制下的 xxx 从左往右出现的最后一个 111 及其后面的 000 组成的数的十进制。这么听着有点绕，例如 lowbit(6)\tt{lowbit(6)}lowbit(6)，(6)10=(110)2,(6)_{10}=(110)_2,(6)10 =(110)2 , 取 101010，得 (10)2=2(10)_2=2(10)2 =2，所以 lowbit(6)=2\tt{lowbit(6)=2}lowbit(6)=2。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值一定是 222 的幂次，前提 x≠0x\ne 0x=0。 关键在于我们按 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图） 这棵二叉树非常神奇，对于节点 iii，如果他是左子结点，他的父节点为 i+lowbit(i)\tt{i+lowbit(i)}i+lowbit(i)，否则他的父节点为 i−lowbit(i)\tt{i-lowbit(i)}i−lowbit(i)。因此我们可以利用 lowbit\tt{lowbit}lowbit，对区间段进行前缀和计算。 构造一个辅助数组 c[]c[]c[]，定义 cic_ici 为覆盖节点 iii 及其左子树的区间和，即： ci=∑i−lowbit(i)+1iaic_i=\sum_{i-lowbit(i)+1}^i a_i ci =i−lowbit(i)+1∑i ai 这时我们回归问题。 修改 观察 cic_ici 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。 查询 只需要将所有其左上方的祖先及其本身的值即可。 对于区间修改问题，由于 query\tt{query}query 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性） 模板题，上模板。 例题： * 股票 提醒各位初学者，本题虽然不必离散化，但是你拿 aia_iai 建的树状数组就需要注意阈值上限是 maxai\max a_imaxai 不是 nnn 了。可能你们会觉得这句话很糖。 * 逆序对 由于 aia_iai 达到了 10910^9109，我们无法直接按照 aia_iai 的值建树状数组，因此考虑离散化： * 1.复制 aaa 数组存入 ttt，将 ttt 排序。 * 2.将 ttt 用 unique\tt{unique}unique 函数去重。 * 3.用二分找原 aia_iai 在 ttt 中的位置。 这样我们就得到了 aia_iai 的相对大小顺序，把值域缩到了 5×1055\times 10^55×105 之内，可以建树状数组了。 2.线段树/(LAZY_TAG) 没写完。 3.权值线段树 洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。 题目描述 给出 n,{an}n,\{a_n\}n,{an }，约定 b1=a1b_1=a_1b1 =a1 。对于 2≤i≤n2\le i \le n2≤i≤n： bi=minj=1i−1∣aj−ai∣ b_i=\min_{j=1}^{i-1}|a_j-a_i| bi =j=1mini−1 ∣aj −ai ∣ 求出 {bn}\{b_n\}{bn }。 输入 给出 n,{an}n,\{a_n\}n,{an } 输出 {bn}\{b_n\}{bn } 输入 111 输出 111 1≤n≤105,1≤ai≤1071\le n \le 10^5,1\le a_i\le 10^71≤n≤105,1≤ai ≤107 无需离散化&动态开点 Code:\tt{Code:}Code: 回转寿司,luogu5459,绿 九转大肠有没有食欲 发现与区间和有关，套上前缀和 sumsumsum。 考虑列不等式 L≤sumr−suml−1≤RL\le sum_r-sum_{l-1}\le RL≤sumr −suml−1 ≤R，直接维护这个是 n2n^2n2 的肯定不现实。 考虑变换得 sumr−R≤suml−1≤sumr−L(l<i)sum_r-R\le sum_l-1\le sum_r-L(l<i)sumr −R≤suml −1≤sumr −L(l<i)，考虑枚举 sumisum_isumi ，那么我们只要找出满足条件的 suml−1sum_{l-1}suml−1 的数量，就是对于 sumisum_isumi 的选择。 于是我们使用权值线段树维护 sumsumsum 的值，也就是要计算的 [sumi−R,sumi−L][sum_i-R,sum_i-L][sumi −R,sumi −L]，那把小于 iii 的 sumjsum_jsumj 全部丢进权值线段树即可。 需要注意的是，本题阈值很大，记得动态开点处理。
一个新的寻找二次函数顶点的方法？
首先，形如 ax2+bx+cax^2+bx+c ax2+bx+c 的柿子 要变为 k(x−l)2+r (k,l,r不含x)k(x-l)^2+r\ (k,l,r不含x) k(x−l)2+r (k,l,r不含x) 先化简原式 k(x−l)2+rk(x-l)^2+r k(x−l)2+r =k(x2+l2−2xl)+r=k(x^2+l^2-2xl)+r =k(x2+l2−2xl)+r =kx2+kl2−2kxl+r=kx^2+kl^2-2kxl+r =kx2+kl2−2kxl+r 那么你就会发现 (因为 (k,l,r不含x)(k,l,r不含x)(k,l,r不含x) ) {k=abx=−2kxlkl2+r=c\left\{\begin{matrix}k=a \\bx=-2kxl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=abx=−2kxlkl2+r=c 若 x=0x=0x=0 ，则 y=cy=cy=c 嗯对。。。 否则 {k=ab=−2klkl2+r=c\left\{\begin{matrix} k=a \\ b=-2kl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=ab=−2klkl2+r=c 将 k=ak=ak=a 代入方程组 {b=−2alal2+r=c\left\{\begin{matrix}b=-2al \\al^2+r=c \end{matrix}\right. {b=−2alal2+r=c 单独求解①式，得： l=−b2al=-\frac{b}{2a} l=−2ab 将其带入②式 a×b24a2+r=ca\times \frac{b^2}{4a^2}+r=c a×4a2b2 +r=c b24a+r=c\frac{b^2}{4a}+r=c 4ab2 +r=c 所以 r=c−b24ar=c-\frac{b^2}{4a} r=c−4ab2 所以 {k=al=−b2ar=c−b24a\left\{\begin{matrix}k=a \\l=-\frac{b}{2a} \\r=c-\frac{b^2}{4a} \end{matrix}\right. ⎩⎨⎧ k=al=−2ab r=c−4ab2
有帮助，赞一个