上海营X02-Day3学习笔记

CSP复赛考试注意事项

CSP复赛在即，祝各位考生发挥最佳状态，RP+++！以下是考试注意事项，快来看看吧。 CSP复赛考试注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 原文：CSP注意事项 考前准备 1. 考前注意检查身份证、准考证等证件，以及笔等基本工具。 2. CSP 允许带食品和饮料，可带一瓶水和巧克力等进入考场补充体力。 3. 比赛开始前调整屏幕分辨率至个人舒适大小。 4. 比赛开始前将编译器字体调整为平时惯用字体。 5. 在不影响视野的情况下，尽可能调大字号以方便查错，特别是模拟或搜索题目。 6. 比赛前多敲键盘，熟悉常用按键。 比赛时注意事项 1. 保持心态平稳，相信自己。对于题意不明确的情况，通读题面与样例，必要时询问工作人员。 2. 如果机器出现问题，不要慌，可申请加时并利用时间思考题目。 3. 如果感到紧张，可以尝试上厕所冷静一下。 4. 不要因为旁边人写得快而慌乱，每个人的解题速度不同。 5. 仔细读题，通读完后再开始深入思考。 6. 不要因为题目看似简单就急于写代码，先明确每一步要做什么。 7. 对于看似无解的题目，不要提前放弃，尝试几个例子可能找到解题思路。 8. 写题前先在纸上规划思路，判断可行性后再编写代码。 9. 认真计算时间复杂度，避免将低复杂度代码误算为高复杂度。 10. 不要浪费时间在大模拟或大搜索上，到一定程度即可。 11. 数学题或找规律题要在纸上写出来。 12. 充分利用时间，如果15分钟内没有思路就换题。 13. 先写暴力解，再写正解。 14. 时刻计算当前代码的复杂度。 15. 写完程序后，通读代码进行静态查错，注意变量调用、数组大小、变量类型等。 16. 通过样例后，自行设计数据测试程序，确保程序健壮性。 17. 出现问题时，分模块调试程序。 18. 可以使用 #include <bits/stdc++.h>，不需要背诵大量头文件。 19. 代码保存按照考场PDF指示，不清楚可询问监考老师。 20. 避免使用下划线开头的函数，除非自己定义。 21. 变量名避免使用完整单词或不清晰的命名方式。 22. 删除调试语句，定期保存代码。 23. 注意数据范围，合理分配内存空间。 24. 注意输出方式，如取模操作。 25. 自己手写 abs 函数。 26. 注意题目输出要求，如大写问题。 27. 整数指数时避免使用 pow 函数。 28. 注意 scanf 类型正确性。 29. 避免使用 floor 和 ceil 函数。 比赛结束前的注意事项 1. 比赛最后5至15分钟，不要再改动程序。 2. 检查文件名是否正确。 3. 检查是否正确处理文件输入输出。 4. 整理物品，离开时带走垃圾。 代码示例 以上是对考前准备、比赛时注意事项以及比赛结束前的检查事项的详细整理，希望对你有所帮助。 2024 CSP-J/S 第二轮缴费及系统使用说明流程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、赛事相关信息 📍 关于 CCF 2024 CSP-J/S 有关问题的解答 可先点击链接了解： 关于CCF CSP-J/S2024有关问题的解答 📋 关于 CCF 2024 CSP-J/S 各省特派员信息 点击链接查看各省负责人联系方式： CSP-J/S各省负责人联系方式 📆 CSP-J/S 2024第二轮报名通知 点击链接查看报名通知： NOI报名网站 二、第二轮认证时间 🕐️ 第二轮认证时间：2024年10月26日 * 入门级：8:30-12:00 * 提高级：14:30-18:30 三、第二轮认证参加资格 凡已参加 CSP-J/S 2024 第一轮认证，且成绩符合所在省市第一轮晋级第二轮认证规则者均可参加 CSP-J/S 2024 第二轮认证。 各省晋级规则将陆续公布在“NOI网站—各省新闻”中。 时间 8:30-12:00 14:30-18:30 2024年10月26日(周六) 入门级认证 提高级认证 未参加第一轮认证，或不符合本省参加第二轮认证晋级规则者均不能参加第二轮认证。 四、第二轮认证报名流程 CSP-J/S 2024 第二轮不需要认证者操作报名及指导教师进行审核，由各省负责人直接统一为本省具有晋级资格的认证者报名。 CSP-J/S 2024 第二轮报名流程及操作时间点具体如下 日期 时间 内容 角色 10月2-9日 全天 统一报名 各省负责人 10月10-18日 10月18日 15:00前 认证者审核状态为“请确认报名并缴费”后，认证者如确认参加活动，在报名页面进行交费 认证者 10月19-21日 10月21日 17:00前 生成准考证号、提交报名表、上传考点信息、CCF审核报名表 各省负责人,CCF管理员 10月22-26日 全天 下载准考证 认证者 10月26日 8:30-12:00 入门级认证 入门级认证者 10月26日 14:30-18:30 提高级认证 提高级认证者 👉 查看更多： 欢迎在留言区评论，畅所欲言！

互动｜ 我们2岁啦～参与掉落周年限定礼品

🎉🎉🎉 我们2岁啦！🎉🎉🎉 ACGO社区即将2周年啦！🎉这不仅是一段旅程，更是一段充满回忆的成长史。🎊亲爱的同学们，ACGO社区即将迎来它的2周岁生日（11月11日），在此，我们诚挚地邀请每一位同学，共同来庆祝这个特别的时刻！🎂 参与评论赢取周年限定礼品 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📅【活动时间】 从11月5日开始，一直到11月17日24点结束哦！🕙 🎁【如何参与】 * 方式1. 在评论区分享你与ACGO的小故事，快来告诉我们你是如何认识社区的，在社区发生过最难忘或最开心的一件事…… * 方式2. 分享你对ACGO社区的祝福。💕！在这个特殊的日子里，你又有哪些心里话想对ACGO说呢？🧐 🏆【活动奖励】 * 限定保温杯+2周年贴纸：我们会从大家分享的故事中，精心挑选出3-6篇最真实、最走心、最能打动我们的小故事，获得我们特别准备的2周年限定礼品！🥤 * 2周年限定贴纸：另外，我们还会在参与留言的同学中，随机抽取10位送上ACGO贴纸。🎁 💌【特别提示】 注意啦，我们会在活动结束后的一周内公布获奖名单哦，请大家耐心等待。😜 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感谢每一位同学一直以来对ACGO社区的支持与陪伴。未来，让我们继续携手同行，在ACGO社区创造更多美好的回忆！✨

互动｜1024吐槽大会

🚀话题#6｜ 1024吐槽大会 😎 1024程序员节即将到来！大家在编程学习过程中，是不是有很多想吐槽的呢？比如学习中最难的算法，编程学习中遇到的最搞笑最或最崩溃的时刻，或者最最难的编程题，或者是ACGO的最难用的地方。不管是什么，都快来这里畅所欲言吧！ 🎁话题奖励 奖励设置：抽取3个人，获得ACGO盲盒1件。 🎁话题时间 活动时间：2024/10/21 -2024/10/30。 🎁获奖公告 ID 昵称 4347789 复仇者 4495551 VIVI 4156430 手持剑，刺锋芒 在这个时间段内，大家都可以积极参与留言分享哦，快来吐槽你的编程学习经历吧😎

无聊的我雕了一个南瓜

Happy Halloween 🎃👻万圣节快乐！\textcolor{orange}{\textbf{\Huge \text{Happy Halloween 🎃👻}}}\\ \textcolor{orange}{\textbf{\Huge \text{万圣节快乐！}}} Happy Halloween 🎃👻万圣节快乐！ > 无聊的我雕刻了一个南瓜。 Trick or Treat 🍭👻\textcolor{purple}{\textbf{\Huge \text{Trick or Treat 🍭👻}}} Trick or Treat 🍭👻 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 游《温哥华》记 - 2024 Thanksgiving

Acgo 竞赛积分系统

概述 新版 Acgo\tt{Acgo}Acgo 竞赛分系统参考了 AtCoder\tt{AtCoder}AtCoder 平台的 AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00[1]。 该积分系统基于 Logistic Distribution\tt{Logistic\ Distribution}Logistic Distribution（或 Sigmoid Function\tt{Sigmoid\ Function}Sigmoid Function），类似于 Elo\tt{Elo}Elo 评分系统，但进行了许多修改。 新版竞赛分系统上线后，用户参加 Acgo\tt{Acgo}Acgo 的所有比赛将会有 Rated\tt{Rated}Rated 和 Unrated\tt{Unrated}Unrated（即「评分」与「不评分」）两种状态。 正常情况下参加比赛的选手状态为 Rated\tt{Rated}Rated，状态被评为 Unrated\tt{Unrated}Unrated 包含但不仅限于以下情况： 1. 参加本场比赛前竞赛分超过本场比赛的 Rated\tt{Rated}Rated 分数线限制（RATEDBOUNDRATEDBOUNDRATEDBOUND）； 2. 比赛中作弊，被取消比赛成绩； 3. 本场比赛因不可抗力因素导致无法正常进行的将参与本场比赛的所有用户设置为 Unrated\tt{Unrated}Unrated。 对于 Rated\tt{Rated}Rated 的选手，在每场比赛中，会获得一个「表现分」。这个值代表了你在比赛中的表现如何。 粗略地说，你的每场比赛后的竞赛分为「表现分」的加权平均值（最近的比赛权重更高）减去 f(x)f(x)f(x)（xxx 为 Rated\tt{Rated}Rated 比赛的参与次数），其中 f(1)=1200f(1) = 1200f(1)=1200，且 fff 随参加的 Rated\tt{Rated}Rated 比赛的次数增加而逐渐减小并趋于零。 这意味着如果你持续获得 XXX 的表现分，你的竞赛分将从 X−1200X−1200X−1200 开始，并逐渐趋近于 XXX。 请不要担心在第一场比赛中获得很低的竞赛分，如果你参加更多比赛，分数很可能会迅速上升。当参加 101010 场比赛后，你的竞赛分将会非常接近于你的真实实力。 计算表现分 在系统内部有两种类型的「表现分」：PerfPerfPerf 和 RPerfRPerfRPerf（修正后的 PerfPerfPerf） 。 首先，对于每个参赛选手，我们计算出他们的 APerfAPerfAPerf（平均表现分）。 令 Perf1,Perf2,⋯ ,PerfkPerf_1, Perf_2, \cdots, Perf_kPerf1 ,Perf2 ,⋯,Perfk 为一位参赛选手的历史 PerfPerfPerf。其中 Perf1Perf_1Perf1 是最近参加的一场比赛，PerfkPerf_kPerfk 是最早参加的一场比赛，这位选手的 APerfAPerfAPerf 被定义为： APerf=∑i=1kPerfi×0.9i∑i=1k0.9i\begin{equation} APerf = \frac{\sum_{i=1}^{k}Perf_i \times 0.9^i}{\sum_{i=1}^{k}0.9^i} \end{equation} APerf=∑i=1k 0.9i∑i=1k Perfi ×0.9i 所有第一次参与 Acgo\tt{Acgo}Acgo 的 Rated\tt{Rated}Rated 比赛的选手的 APerfAPerfAPerf 将会被设置为 CenterCenterCenter。 CenterCenterCenter 和每一场 Rated\tt{Rated}Rated 比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND（即 Rated\tt{Rated}Rated 上限）有关。 Center=RATEDBOUND×0.4Center = RATEDBOUND \times 0.4Center=RATEDBOUND×0.4。 令 nnn 为一场比赛中所有的 Rated\tt{Rated}Rated 的参赛选手的数量，令 APerfiAPerf_iAPerfi 为第 iii 个选手的 APerfAPerfAPerf。那么比赛的 Rated\tt{Rated}Rated 榜单中，排行第 rrr 名选手的 PerfPerfPerf 被定义为满足以下公式的唯一的 XXX： ∑11+6.0(X−APerfi)/400.0=r−0.5\begin{equation} \sum\frac{1}{1 + 6.0^{(X - APerf_i) / 400.0}} = r - 0.5 \end{equation} ∑1+6.0(X−APerfi )/400.01 =r−0.5 这个 XXX 可以使用二分来计算得出。 请注意，以上的排名是所有并列名次的平均值。例如，如果有四个人并列第 333 名至第 666 名，那么这些人的排名为 4.54.54.5。 除此之外，为了避免在第一场比赛中的「表现分」方差过小，Acgo\tt{Acgo}Acgo 使用新竞赛分系统的第一场比赛（这里指 排位赛#4）的表现值会被放大处理，具体如下： Perf=(Perf−Center)×1.5+Center\begin{equation} Perf = (Perf - Center) \times 1.5 + Center \end{equation} Perf=(Perf−Center)×1.5+Center 最终，对于每个用户其 RPerfRPerfRPerf 使用以下方式计算： RPerf=min⁡{Perf,RATEDBOUND+100}\begin{equation} RPerf = \min{\{Perf, RATEDBOUND + 100\}} \end{equation} RPerf=min{Perf,RATEDBOUND+100} 其中 RATEDBOUNDRATEDBOUNDRATEDBOUND 对于不同的比赛是不一样的，每场比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND 会在竞赛说明中给出。 计算竞赛分 定义 FFF 为： F(n)=∑i=1n0.81i∑i=1n0.9i\begin{equation} F(n) = \frac{\sqrt{\sum_{i=1}^{n} 0.81^i}}{\sum_{i=1}^n 0.9^i} \end{equation} F(n)=∑i=1n 0.9i∑i=1n 0.81i 定义 fff 为： f(n)=F(n)−F(∞)F(1)−F(∞)×1200\begin{equation} f(n) = \frac{F(n) - F(\infin)}{F(1) - F(\infin)} \times 1200 \end{equation} f(n)=F(1)−F(∞)F(n)−F(∞) ×1200 定义 ggg 为： g(X)=2.0X800\begin{equation} g(X) = 2.0^{\frac{X}{800}} \end{equation} g(X)=2.0800X 该函数可以给更好的表现赋予更多的权重。因此，极好表现与较好表现之间的差异会非常大，而重大失误与一般失误之间的差异则不会那么大。 这样可以使得当参赛者在比赛中打出了超出水平的发挥时，会增加更多的竞赛分；当参赛者在比赛中打出了远低于自己水平的表现分时，不会减少太多的竞赛分； 令 RPerf1,RPerf2,⋯ ,RPerfkRPerf_1, RPerf_2, \cdots, RPerf_kRPerf1 ,RPerf2 ,⋯,RPerfk 为一位参赛选手的历史 RPerfRPerfRPerf，其中 RPerf1RPerf_1RPerf1 为当场比赛的 RPerfRPerfRPerf。那么本场比赛结束后，其竞赛分为： Rating=g−1(∑1kg(RPerfi)×0.9i∑1k0.9i)\begin{equation} Rating = g^{-1}(\frac{\sum_1^k g(RPerf_i) \times 0.9^i}{\sum_1^k 0.9^i}) \end{equation} Rating=g−1(∑1k 0.9i∑1k g(RPerfi )×0.9i ) 然后考虑公式 (6)(6)(6) 的 fff 函数对竞赛分的影响，定义以下函数[2]： mapRating(r)={400exp⁡(400−r400)r≤400rr>400\begin{equation} mapRating(r) = \begin{cases} \frac{400}{\exp{(\frac{400 - r}{400})}} &{r \le 400}\\ r & {r \gt 400}\\ \end{cases} \end{equation} mapRating(r)={exp(400400−r )400 r r≤400r>400 最终 RatingRatingRating 计算出来为： TrueRating=mapRaing(Rating−f(n))\begin{equation} TrueRating = mapRaing(Rating - f(n)) \end{equation} TrueRating=mapRaing(Rating−f(n)) 其中 nnn 为已经参加的 Rated\tt{Rated}Rated 的比赛场次（包括本场）。 本文档的版本记录 * 10/29/2024 Ver. 1.00: 第一版。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00 ↩︎ 2. AtCoderのレート計算式\tt{AtCoderのレート計算式}AtCoderのレート計算式 ↩︎

"复仇者联盟"处罚公告

在“10月排位赛#6”中，我们发现用户复仇者小ZUZU_童瑞琪专属奴隶，ID：937283，在比赛T3，T4，T6中涉嫌使用AI生成代码进行不正当竞争，对此做出惩罚，将其踢出团队，此后不得再加入团队。 以下是我们找到的证据 @复仇者小ZUZU_童瑞琪专属奴隶 T3的代码 而这是@复仇者_零提供的由canvas写出的代码 经过AI比对，发现 @复仇者小ZUZU_童瑞琪专属奴隶 T6的代码 而这是@复仇者_零提供的由GPT-4写出的代码 几乎一模一样...... 我们有足够好的检测方式，可以检测出每个作弊的人！！！ 希望这种事情不要再发生，希望大家公平竞争。我们不会惋惜任何一位成员！！！

ACGO名人专访（第二期）预热+预告

相信大家一定特别期待了！ 第一次的名人专访反响不错，且有MACW的神级助攻（置顶了），我已经在马不停蹄地准备下一期的名人专访了！ 这里，我对下一次名人专访做一个小小预告，透露一些信息： 你们最关心的下一位被害者幸运儿是谁，他是： 排位分前十 我这段时间有很多比赛（天文，数学，编程）所以发布时间暂定 12月 我们这次采访的问题做了 较大扩容 希望大家提前预热，在发布前三天，我会再发一条预告，大家敬请期待吧！ tips：我的队伍原力c++正在招人，希望大家踊跃参与。（可参加名人专访） hey，AC君都来了，你不看看？

2024CSP-J&S江苏游记

DAYFOREVER(前言) 写在前面：作者这次状态极差，很多题都写挂了。无论如何，之前打OI的时光还是很值得留念的。 已AFO。2022.12.14~2024.10.27 DAY-1(2024/10/25) 听了一会歌，复习了一下模板，就去睡觉了，毕竟明天要考一天 睡得还行。但是我后来才知道，我应该是失眠了。 DAY1上午(2024/10/26) 幸好没有被分到南京去。 六点半起床，开半小时去苏州考场。到的时候已经七点半了，还算是比较早的，但是已经有很多人在站着了。天气是阴天。怎么考CCF的时候全是阴天啊喂 精神还行，没有很紧张，毕竟是J。但是怎么还有身高只有一米二的小朋友来考（记住这个小朋友，待会会考）。 分到的考场好闷。考场很小，几乎是挤在一块的。还有足足一个小时的时间开考，我也不急，先打了个Floyd模板试试手，测测运行时间。 大概8：24的时候，监考员下发了压缩包。什么？你跟我说有密码打不开？好吧雀氏打不开，但是可以预览文件。 看了四个文件名：chain?接龙？感觉是模拟。explore？探索？感觉是模拟。poker?扑克牌？感觉是模拟。sticks?火柴棒摆数字？感觉还是甜蜜的模拟。 随着我点开pdf的那一刻，我看到了第一题——poker。读完这题后，我随之感叹一句：J组的第一题水分又增加了114514%，真是滑天下之大稽。我用5分钟过了这道题。 第二题就是一个纯纯的模拟。感觉只有普及-的难度。狂写两分钟，结构代码debug半小时。无论怎样还是过了。 第三题火柴棒，果然猜对了：摆数字。一开始想着用贪心，但是不知道怎么了没有想出来。这时候看了一眼特殊性质：两个全部和7的倍数有关。我很快推出了两个性质，60分到手。然后我又去打表n≤20，打完之后很快发现这里有很明显的规律。 这时候突发事件来了，在整个刚才想的过程中，我的头越来越痛。感觉天旋地转，看到我有三只手。我觉得是机房太闷了，于是去上了个厕所。但是这种症状并没有减轻，差点躺在厕所里。那怎么办？硬抗。我当时这样想。 回来之后，感觉状态已经很差了。于是我朦胧找到的规律被我否决了，于是100分的机会没有拿到，只拿到了70分。 再看第四题。第一眼感觉要把他们连边。但是这样一来连的边就太多了。考虑dp。结果推了2个小时硬是没有推出来，我不会菜的连绿题都不会了吧。 还剩5分钟结束。我只能保存文件。估分100+100+70=270，这个分放在江苏估计连二等奖都拿不到。 考完的时候，那个小朋友说他AK了。wc真是天大的打击。问他了一下思路，也都差不多。 DAY1下午(2024/10/26) 在附近吃了个KFC。然后继续考S。不幸的是，状态仍旧不好，我的好手表竟然说我缺氧，tmd气死我了。 打开文件先看到第一题。哇这么水吗？我直接排序+O(n)遍历。10分钟的时候就写完了。 看到第二题。我勒个超速检测啊，他这次甚至还有公式。模拟了一遍之后很容易求出第一问。至于第二问，可以把检测到的摄像头看作区间，求最大交错区间，然后减去。但是这样的复杂度是O(n2)O(n^{2})O(n2)的，会被卡死。 看了一会，发现他们有单调性，那么两个东西都用二分，O(Tnlogn)O(Tnlogn)O(Tnlogn)解决。这题卡了我一小时。 这时候，脑子已经有点白热化了。 接着看第三题涂色。这题感觉很玄学啊，要用dp。本来要dfs的，后来看了一下数据，老实了。 dp[i][0]和dp[i][1]的转移卡了我有一个多小时。列了满满一草稿纸，算出一个很奇怪的转移方程。结果果然不对。但是思路应该没问题啊？？心态有点崩了。 顺便看了一下第四题，感觉有黑题。就先不做了。于是一直再调前面的题目。 后记(2024/10/27) 我怎么也没想到，3题全写挂？！70+0+5=75,对不起我要退役了。最后4勾的倔强。 这次也不能怪别人，不知道为什么状态出奇的差。也许最近压力太大了？我不知道，也许这就是OI的魅力。 比赛完，有人欢喜有人愁。漫步在校园里，远边夕阳早已落下，楼房灯火通明。或许，夕阳落下的，还有我的生涯吧。 AFOed.也许这条道路不适合我走，心中会有不甘，但是早已没有时间给我再来一次。 "总为浮云能避日，长安不见使人愁。"

和新同学秋游感觉真不一样😀紫清湖一日游

标题极致压缩，不然超字数了 看到标题 ，大家也知道复仇者_X也是去秋游了呀 （当然是在痛苦的期中之后） 这次去的是南京紫清湖野生动物园，地方挺大的，所以时间关系，就没有游玩太多的地方，尽管如此，和同学在一起的时光也充满了乐趣。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大巴车上：车上人可嗨了，老师坐在最前面，还有一个倒霉蛋做老师旁边啥也干不了，而我们后面的人有的用手表放音乐 （好像是我），有的人用手机拍照，反正吵吵闹闹的，简直没把老师当回事，老师还算年轻，也就睁只眼闭只眼了，所以这也是我历年来秋游中最GOOD的一段时光了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大概45分钟，到达目的地，快乐时光告一段落，开始排队等小火车进入野生动物园，大概排了一个多小时的队，才轮到我们，结果小火车转了一圈大概也就20多分钟的时间，排队一个多小时，参观20分钟，感觉不太值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参观完，已经十二点左右了，老师准备找个地方给我们吃东西，找到一块空地（在大象旁边，一股*味儿），铺开垫子，摊开书包里装的满满当当的零食，开始大吃特吃，最讨厌白嫖哥了，啥也不带就蹭吃蹭喝，来的时候书包是空荡荡的，走的时候书包都撑不下了，我们通常交换零食，以物换物，但是更多的还是直接互相赠送。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 看马戏时可以说是一天中的高潮了，特别是一开始马戏还在准备的时候再放音乐，全班（校）人合唱孤勇者太壮观了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后再招个人，大家知道吗，CODECRUSHERS团队有邀请赛了，邀请码：TFXN，欢迎大家来参加哦 小互动：满分十分，你会给这篇打几分呢，测试一下我的语言水平😀

ACL｜通用「树状数组」模板

前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 像使用 std::vector 一样，使用「树状数组」。 本文将介绍 AC(AtCoder) Library 中提供的 fenwick_tree 模版。 本文最后提供的 FenwickTree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。 树状数组简单来说即为支持在线求前缀和的一种特殊数据结构（请把复杂的功能交给「线段树」）。 使用树状数组，不需要知道树状数组的原理！ 当你需要一边「修改数组中单个元素」，又同时需要查询数组的「前缀和」时，那么不要犹豫，把此模版粘贴你的代码中去吧！ 然后就可以像使用 STL\tt{STL}STL 中的 std::vector，std::map 等容器一样使用「树状数组」啦！ 示例 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以下为使用 FenwickTree 和 Modint 后，挑战赛#10 的第 6 题，Ptorrweee 最后统计答案部分的代码。 可以看出，结合使用两个算法模板后，可以将最后的代码变得十分简洁。将「树状数组」封装，特别在题目需要有多个树状数组求解时尤其方便。 操作 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 构造函数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 定义一个长度为 nnn 的数组 a0,a1,⋯ ,an−1a_0, a_1, \cdots, a_{n - 1}a0 ,a1 ,⋯,an−1 。所有元素被初始化为 000。 注意 T 的类型为 int，long long，unsigned，unsigned long long 或 Modint 类型。 且 0≤n≤1080 \le n \le 10^80≤n≤108；构造函数的时间复杂度为 O(n)\mathrm{O(n)}O(n)。 2. ADD ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 执行 a[p] += x 操作。 要求 0≤p<n0 \le p \lt n0≤p<n；时间复杂度 O(log⁡n)\mathrm{O(\log{n})}O(logn)。 3. SUM ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 该方法返回 al,al+1,⋯ ,ar−1a_l, a_{l + 1}, \cdots, a_{r - 1}al ,al+1 ,⋯,ar−1 的和。 2. 该方法返回 a0,a1,⋯ ,ar−1a_0, a_{1}, \cdots, a_{r - 1}a0 ,a1 ,⋯,ar−1 的和。 以上方法要求 0≤l≤r≤n0 \le l \le r \le n0≤l≤r≤n；时间复杂度皆为 O(log⁡n)\mathrm{O(\log{n})}O(logn)。 FENWICKTREE.CPP ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------