lookas2001

Minecraft 原版玩腻了（龙终于打过了），想玩 Minecraft MOD ，于是乎我装了工业 2 模组。正想着联机，从 mcbbs 里找了半天，感觉靠谱的就没有几个。自己玩又太孤独，那就来搭建一个服吧。这是前言，具体细节不多讲了，总之坑很多，不过好在有前辈们的教程（比如 http://www.mcbbs.net/thread-786074-1-1.html ），路走的还算顺利。本着为人民服务的精神，在这里选取一个坑，总结一下过程，来帮助后来的小伙伴们。

简要介绍

Universal Market 是一个寄售市场，有着类似箱子的界面。

MCBBS 转载贴： http://www.mcbbs.net/thread-792152-1-1.html
Github 原始项目： https://github.com/Xwaffle1/UniversalMarket

下载

20190628 更新：修复了热加载不管用的问题，修复了空手将空气添加到市场的bug

UniversalMarket-1.12.2-v1.3-Bug_fix_and_chinese_translation_by_yys_and_Tollainmear_and_lookas2001.jar

UniversalMarket-master-Bug_fix_and_chinese_translation-source.7z

由于这个项目的各种提示文本是内置在代码里的，所以汉化需要重新编译，上面有项目源代码文件，如果不放心的话，可以按照下方的编译过程自己手动编译。汉化部分采用 Tollainmear 提供的翻译。

出现问题

我搭建的服务器版本为 Minecraft 1.12.2 , Forge 1.12.2-14.23.5.2825 , SpongeForge 1.12.2-2825-7.1.6 。在安装了 1.3 版本的 Universal Market 插件（ https://github.com/Xwaffle1/UniversalMarket/releases/tag/1.3 ）后发现无法正常进入商店，控制台报错如下：

[xx:xx:xx] [Server thread/ERROR] [Sponge]: Error occurred while executing command 'um' for source EntityPlayerMP['lookas2001'/248, l='world', x=302.00, y=64.00, z=229.00]: There's no NBT Data set in the provided container
org.spongepowered.api.data.persistence.InvalidDataException: There's no NBT Data set in the provided container
    at net.minecraft.item.ItemStack.setRawData(ItemStack.java:2534) ~[aip.class:?]
    at com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:38) ~[ItemBuilder.class:?]
    at com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:31) ~[ItemBuilder.class:?]
    at com.xwaffle.universalmarket.market.Market.openMarket(Market.java:247) ~[Market.class:?]
    at com.xwaffle.universalmarket.market.Market.openMarket(Market.java:167) ~[Market.class:?]
    at com.xwaffle.universalmarket.commands.MarketCommand.process(MarketCommand.java:45) ~[MarketCommand.class:?]
    at org.spongepowered.api.command.dispatcher.SimpleDispatcher.process(SimpleDispatcher.java:340) ~[SimpleDispatcher.class:1.12.2-2825-7.1.6]
    at org.spongepowered.common.command.SpongeCommandManager.process(SpongeCommandManager.java:337) [SpongeCommandManager.class:1.12.2-2825-7.1.6]
    at net.minecraft.command.ServerCommandManager.func_71556_a(SourceFile:1156) [dh.class:?]
    at net.minecraft.network.NetHandlerPlayServer.func_147361_d(NetHandlerPlayServer.java:960) [pa.class:?]
    at net.minecraft.network.NetHandlerPlayServer.func_147354_a(NetHandlerPlayServer.java:939) [pa.class:?]
    at net.minecraft.network.play.client.CPacketChatMessage.func_148833_a(SourceFile:37) [la.class:?]
    at net.minecraft.network.play.client.CPacketChatMessage.func_148833_a(SourceFile:9) [la.class:?]
    at org.spongepowered.common.event.tracking.phase.packet.PacketPhaseUtil.onProcessPacket(PacketPhaseUtil.java:193) [PacketPhaseUtil.class:1.12.2-2825-7.1.6]
    at net.minecraft.network.PacketThreadUtil$1.redirect$onProcessPacket$zlk000(SourceFile:539) [hv$1.class:?]
    at net.minecraft.network.PacketThreadUtil$1.run(SourceFile:13) [hv$1.class:?]
    at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511) [?:1.8.0_74]
    at java.util.concurrent.FutureTask.run(FutureTask.java:266) [?:1.8.0_74]
    at net.minecraft.util.Util.func_181617_a(SourceFile:46) [h.class:?]
    at org.spongepowered.common.SpongeImplHooks.onUtilRunTask(SpongeImplHooks.java:307) [SpongeImplHooks.class:1.12.2-2825-7.1.6]
    at net.minecraft.server.MinecraftServer.redirect$onRun$zjo000(MinecraftServer.java:3970) [MinecraftServer.class:?]
    at net.minecraft.server.MinecraftServer.func_71190_q(MinecraftServer.java:723) [MinecraftServer.class:?]
    at net.minecraft.server.dedicated.DedicatedServer.func_71190_q(DedicatedServer.java:397) [nz.class:?]
    at net.minecraft.server.MinecraftServer.func_71217_p(MinecraftServer.java:668) [MinecraftServer.class:?]
    at net.minecraft.server.MinecraftServer.run(MinecraftServer.java:526) [MinecraftServer.class:?]
    at java.lang.Thread.run(Thread.java:745) [?:1.8.0_74]

这时候我有点慌了，因为我之前没有系统的接触过 Java ，只在研究锐捷网络 ESS/SMP 产品授权验证以及 Moegirl Android App 的时候稍微有所了解。

定位和解决

直接上搜索引擎，没找到…

由于这个项目是开源的（Open Source 大法好！），我们可以将代码下载下来慢慢研究。

后来又到原始项目里找 issue 找到了这个 https://github.com/Xwaffle1/UniversalMarket/issues/20 ，通过一些方式联系上了一个已经对前面一个版本的 jar 打完补丁的 dalao Alone，感谢其作品在我没有思路时候对我的启发。

好在有 trace ，我们可以看到最后一个关于这个插件的错误发生在 com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:38) ~[ItemBuilder.class:?] 这里：

我们把 setRawData 这个函数扔到 Sponge Forum 上搜索一下 https://forums.spongepowered.org/t/set-get-modify-subid-of-itemstack/19048/9 ，发现这个函数与在物品上设置一些属性有关，是一个比较 hacky 的做法。

将这段代码对应的函数在项目全局搜索一下：

发现这段代码只跟 Market.java 这个文件相关，打开，查找调用地方。

我们发现实际通过 meta 变量传入设置了 UnsafeDamage （损坏值）的调用点只在这里：

加载了好使的插件后，可以发现这个是支付确认界面的确定按钮。

故推测，这可能是作者想要做的一个类似进度条相关的功能，但是最后可能因为各种原因最后咕咕咕了（人类的本质）。

那就直接把这一行以及相关的两行（即出现 bug 这一行的上面两行）移除掉试一试。

拦路虎——编译

Minecraft 使用 Java 8 作为其运行环境，相应的，其周围 Mod 开发都是在 Java 8 基础上进行的，推荐使用 Java 8 来进行接下来的工作。

我本地用的电脑是 MacBook 开发环境为 MacOS，相对 Windows 系统，在命令行上更加强大一些，周围配套设施也多一些。个人开发的话，平常使用 brew 作为包管理，安装软件快捷迅速。但是 Brew 默认不提供 Java 8 （大概是过时了？），而去 Oracle 官网上下载又是不可能的（下载居然还需要登录），在 StackOverflow 上有这么一个回答 https://stackoverflow.com/a/55774255 ，解决了 Java 8 安装的问题。

看到这个项目使用了 gradle 作为其依赖管理（或者讲构建工具？），依照这我之前用 composer ，npm 的经验，我寻思着应该需要用 brew 安装一下。事实上是不需要的，安装了反而多余。brew 上的 gradle 版本太高，并且项目本身提供了一个包管理命令，即 gradlew 。运行一下会在项目目录以及用户目录生成相应的文件。

于是乎，./gradlew 一下，在下载完必要的文件后，给出了一个提示，按照这个提示，我应该运行 ./gradlew tasks。运行之，找到好像是构建的选项 ./gradlew build 。运行之，傻眼，提示错误：

:compileJava
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:30: 错误: 程序包org.spongepowered.common.item.inventory.adapter.impl.slots不存在
import org.spongepowered.common.item.inventory.adapter.impl.slots.SlotAdapter;
                                                                 ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:31: 错误: 程序包org.spongepowered.common.item.inventory.query.operation不存在
import org.spongepowered.common.item.inventory.query.operation.InventoryPropertyQueryOperation;
                                                              ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:32: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/MarketItem.java:10: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/utils/ItemBuilder.java:11: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
注: Writing plugin metadata to file:/xxxxxx/UniversalMarket-master/build/classes/main/mcmod.info
5 个错误
:compileJava FAILED

FAILURE: Build failed with an exception.

* What went wrong:
Execution failed for task ':compileJava'.
> Compilation failed; see the compiler error output for details.

* Try:
Run with --stacktrace option to get the stack trace. Run with --info or --debug option to get more log output.

BUILD FAILED

翻找 Sponge 文档，看到官方给出的例子都是基于 IDE 的，但是由于我的 MacBook 空间不够，最后在另外一台电脑上（Windows）安装了Intellij IDEA Community ，然后使用 IDE 提供的构建按钮，又花费了很长的一段时间下载，最后提示了两个错误 “PKIX path building failed” 和 “unable to find valid certification path to requested target” （在 Windows 上使用命令构建不会出现这个问题，但是仍然会出现上述在 MacOS 已经出现的错误），看来不是 IDE 的问题，返回我的 MacBook 。

在前一个步骤中，我观察到了一个事情，为什么其他引入不会出现问题，而这些引入会出现问题，我发现这些包都是以 org.spongepowered.common.xxxx 开头。之前有查看过 build.gradle 这个文件，明明有通过 compile 'org.spongepowered:spongeapi:7.0.0' 引入 SpongeAPI 。在是 IDE 的问题排查完后，我决定去看看 Java 编译器到底在引入一些什么东西。

由于之前有过 gradle 相关的经历，知道 gradle 会在用户目录生成文件夹 ~/.gradle ，去之，然后搜索之 find . | grep sponge 。搜索结果中有一个 ./caches/modules-2/files-2.1/org.spongepowered/spongeapi/7.0.0/ada1f9981de3459b182ee16d6408173ef33a8943/spongeapi-7.0.0.jar 这一看就是 api 对应的包嘛。

解压之（反编译就不用了）：

自闭了

哪来的 common 啊！！

回到 build.gradle 目光下移一行，compile files('libs/spongeforge-1.12.2-2555-7.1.0-BETA-2837.jar') 在结合 SpongeCommon 项目的描述，这作者 tm 直接把 SpongeForge 的发布版本当做依赖了啊！而且源代码还把这个目录给删了！！！结合利用偏门 API 的事情来看（Sponge 不推荐插件作者绕过 Sponge 等行为，这个插件作者直接引入了 net.minecraft.nbt.NBTTagCompound），怪不得这个作者在发布 MOD 没在 Ore 上发啊（可能也跟 Sponge 没提供一些 API 有关）。

下载了现在最新的稳定版本 SpongeForge （spongeforge-1.12.2-2825-7.1.6.jar）（老的不想往后翻了），创建 libs 目录扔进去。然后修改一下 build.gradle 里对应的文件名（保持匹配）。再运行一下 ./gradlew build

小宝贝，终于看见你了：

最后经过测试，工作完美。

lookas2001 版权所有，本作品采用知识共享署名 4.0 国际许可协议进行许可，转载使用的时候请注明作者以及来源。

OpenWrt ( https://openwrt.org/ ) 是一个蛮强大的路由器固件，通过安装软件包可以实现很多功能。WebDAV ( http://www.webdav.org/ ) 是一个对 HTTP 的拓展，可用于共享文件。于是乎，我们可以尝试在 OpenWrt 上安装相应的软件包，让设备支持 WebDAV。

相比于 SMB, AFP，在实际测试中，WebDAV 的速度比较占优势。这点可能得益于 WebDAV 是基于 HTTP 的，HTTP 服务端可能有一些黑科技在降低占用的时候提高速度（也有可能是接下来的步骤中的 WebDAV 是基于 http 而不是 https 的原因）。

另外写这一篇文章的原因是 SMB 和 AFP 已经有了比较完善的教程，比如这两篇文章 https://openwrt.org/docs/guide-user/services/nas/samba_configuration https://openwrt.org/docs/guide-user/services/nas/netatalk_configuration 但是 WebDAV 在文档方面就比较缺乏。

Lighttpd ( https://www.lighttpd.net/ ) 是一个轻量级的，但是功能较为完备的 HTTP 服务端，观察到他提供了 WebDAV mod ，故可用其来实现 WebDAV 服务器。

安装 Lighttpd 以及 WebDAV Auth 模块

先 opkg update 来更新本地的软件包信息。

通过 opkg install lighttpd lighttpd-mod-webdav lighttpd-mod-auth lighttpd-mod-authn_file 可将所依赖的软件包一键装齐。

如果出现了下载速度慢或者下载遇到困难，可以手动到 http://downloads.openwrt.org 上下载对应的包然后安装，或者设置一下网络代理（这不属于这篇文章的谈论范围，需要你自己想办法啦）。

配置 Lighttpd

不像 SMB 提供了 uci 统一配置的接口，Lighttpd 需要在 /etc/lighttpd 下修改。

通过 vi /etc/lighttpd/lighttpd.conf 打开 lighttpd 的主配置文件。

可通过 cp /etc/lighttpd/lighttpd.conf /etc/lighttpd/lighttpd.conf.bak 设置一个备份，便于配置出错的时候还原。

这是一份配置过的配置文件：

server.document-root        = "/mnt"
server.upload-dirs          = ( "/tmp" )
server.errorlog             = "/var/log/lighttpd/error.log"
server.pid-file             = "/var/run/lighttpd.pid"
server.username             = "http"
server.groupname            = "www-data"

index-file.names            = ( "index.php", "index.html",
                                "index.htm", "default.htm",
                              )

static-file.exclude-extensions = ( ".php", ".pl", ".fcgi" )

### Options that are useful but not always necessary:
#server.chroot               = "/"
server.port                 = 81
#server.bind                 = "localhost"
#server.tag                  = "lighttpd"
server.errorlog-use-syslog  = "enable"
#server.network-backend      = "writev"

### Use IPv6 if available
#include_shell "/usr/share/lighttpd/use-ipv6.pl"

dir-listing.encoding        = "utf-8"
server.dir-listing          = "enable"

include "/etc/lighttpd/mime.conf"
include "/etc/lighttpd/conf.d/*.conf"

lighttpd 配置文件中注释是通过在行前加入“#”来实现的。

这里修改了几点：

server.document-root = "/mnt" ，即将文档根目录设置为 /mnt ，我为路由器添加了两个硬盘，分别挂载在 /mnt/sda1 和 /mnt/sdb1 下，这个存放位置不是固定的，可以根据你自己的喜好调整。

server.port = 81 ，即后面我们用来访问的端口，80 端口已经被系统自带的 uHTTPd 占用了，这里设置另外一个防止冲突。

server.errorlog-use-syslog = "enable" ，这个选项可以将错误日志输出到 syslog ，便于我们在 web 控制台查看错误。

server.dir-listing = "enable" , dir-listing.encoding = "utf-8" ，这两个选项可以启用列出文件功能，并且防止文件名乱码。

配置 WebDAV 模块

通过 vi /etc/lighttpd/conf.d/30-webdav.conf 打开 lighttpd 的主配置文件。

这是一份配置过的配置文件：

#######################################################################
##
##  WebDAV Module
## ---------------
##
## See https://redmine.lighttpd.net/projects/lighttpd/wiki/Docs_ModWebDAV
##
server.modules += ( "mod_webdav" )

#$HTTP["url"] =~ "^/dav($|/)" {
  ##
  ## enable webdav for this location
  ##
  webdav.activate = "enable"

  ##
  ## By default the webdav url is writable.
  ## Uncomment the following line if you want to make it readonly.
  ##
  webdav.is-readonly = "enable"

  ##
  ## Log the XML Request bodies for debugging
  ##
  #webdav.log-xml = "disable"

  ##
  ##
  ##
  webdav.sqlite-db-name = "/tmp/lighttpd-webdav.db"
#}
##
#######################################################################

这里修改了几点：

注释掉了 $HTTP["url"] =~ "^/dav($|/)" { , } 两行，这里安装 Lighttpd 的目的就是为了 WebDAV ，注释掉这两行可以将整个网站都设置为 WebDAV 。

webdav.activate = "enable" ，为整个站点启用了 WebDAV 。

webdav.is-readonly = "enable" ，设置运行模式是只读模式，这里设置 disable 可以禁用只读（即可写可读）。

"/mnt/sda1/.lighttpd-webdav.db" ，这里需要为 WebDAV 模块设置一个数据库存储位置，位置建议选择在硬盘上，这个数据库文件需要存储的除了锁定还有一些属性，如果存储在易丢失的地方（如 /tmp ）会导致数据丢失，存储上除硬盘以外的位置会缩短闪存寿命（闪存有擦除上限），请注意，Lighttpd 需要对存储位置的目录有写入的权限，可用 chmod a+w xxx，来授予权限。

Ref

• OpenWrt 论坛上的内容 https://forum.openwrt.org/t/webdav-configuration-essense-with-lighttpd-on-openwrt/25357
• Lighttpd 提供的文档 https://redmine.lighttpd.net/projects/lighttpd/wiki/Docs_ModWebDAV

配置 Auth 模块

这块的配置是用于提升你的文件安全性的，但并不是必须的，而且这方面的配置只可提升少许安全性，攻击者仍然可以在中途截获密码，若想更好的提升安全性，请配置 HTTPS 。

通过 vi /etc/lighttpd/conf.d/20-auth.conf 打开 lighttpd 的主配置文件。

这是一份配置过的配置文件：

#######################################################################
##
##  Authentication Module
## -----------------------
##
## See https://redmine.lighttpd.net/projects/lighttpd/wiki/docs_modauth
## for more info.
##
server.modules += ( "mod_auth" )

auth.backend                 = "plain"
auth.backend.plain.userfile  = "/etc/lighttpd/lighttpd.user"
#auth.backend.plain.groupfile = "/etc/lighttpd/lighttpd.group"

#auth.backend.ldap.hostname = "localhost"
#auth.backend.ldap.base-dn  = "dc=my-domain,dc=com"
#auth.backend.ldap.filter   = "(uid=$)"

auth.require               = ( "/" =>
                               (
                                 "method"  => "basic",
                                 "realm"   => "Personal File Server",
                                 "require" => "valid-user"
                               ),
                             )

##
#######################################################################

这里修改了几点：

可能是包打包人员的疏忽，原来的配置文件中没有 server.modules += ( "mod_auth" ) 一行，为了启用这个模块，须有手动加上。

auth.backend = "plain" ，设置认证后端为 plain 。

auth.backend.plain.userfile = "/etc/lighttpd/lighttpd.user" ，设置认证后端存储认证信息的位置。

auth.require = ..... ，取消这里的注释即意味着启用了认证。

"/" ，代表认证的位置，这里是全站。

"method" => "basic" ，认证的类型，这里设置为 basic 是为了更好的客户端兼容性。

"realm" => "Personal File Server" ，即认证时提示的消息，随便设置即可。

通过 touch /etc/lighttpd/lighttpd.user 可以创建我们需要的认证信息文件。

通过 vi /etc/lighttpd/lighttpd.user 编辑认证信息文件。

这是一份样例：

user1:password1
user2:password2

用户名和密码见用 : 隔开，多个用户之间用空行隔开。

Ref

• Lighttpd 提供的文档 https://redmine.lighttpd.net/projects/lighttpd/wiki/docs_modauth

推荐博客： https://blog.csdn.net/qq_33229466/article/details/79679027

下面口胡，一些犄角旮旯地方的理解。

将所有数做质因数分解，考虑将数按照第一个质因子及其次数（即 p^e）分类，我们发现由于积性函数的性质，这一类的和可以共同提取出一个 f(p^e) ，即式子会变成 f(p^e)(f(a_1 / p^e) + f(a_2 / p^e) + …) 。可以发现式子的后半部分就是一个很类似的问题。这大概就是 Min_25 筛的主要思想吧。

具体来讲是定义了两个求和函数，其中一个求和函数（即朱震霆论文中的 h ，网上大多数博客的 g）辅助另外一个求和函数（即朱震霆论文中的 g ，网上大多数博客的 S）求值。

那个辅助求值函数的求值过程非常类似埃氏筛的过程，故这个方法也称拓展埃氏筛法。

空间使用只需要 O(\sqrt n) ，因为每次递归形如（都是向下取整的除法） n -> n / i , n / i -> n / i / j ，而 n / i / j 可以等价为 n / (i * j) 。数论分块，下略。

复杂度啥的见朱震霆的论文吧。

下面是一些（应该没有锅的）数学公式，代码直接套这些公式就好了，模板在 Counting Divisors 。

积性函数： $f(x)$

要求有 $f(p^e) = \sum_k a_k(e)p^k$ 。

辅助求和函数： $h_k(n, j) = \sum_{2 \leq i \leq n 且 (i 的最小质因子 > p_j 或 i 是质数)} i^k$

若 $p_j > \sqrt n$ ，有 $h_k(n, j) = h_k(n, j – 1)$ ;

否则，有 $h_k(n, j) = h_k(n, j – 1) – p_j^k(h_k(\lfloor \frac n{p_j}\rfloor, j – 1) – h_k(p_j – 1, j – 1))$ 。

特别的，对于 $j = 0$ ，有 $h_k(n, j) = \sum_{2 \leq i \leq n} i^k$ 。

简记 $h_k(n) = h_k(n, j)$ 其中 $p_j > \sqrt n$ （即我们要的辅助求和函数最后没有合数项的）。

求和函数： $g(n, m) = \sum_{2 \leq i \leq n 且 (i 的最小质因子 > p_m)} f(i)$

可知 $g(n, m) = \sum_k a_k(1)(h(n) – h(p_m)) + \sum_{p_m < p_j\leq \sqrt n 且 e \geq 1 且 p_j^{e + 1} \leq n} (f(p_j^e) g(\lfloor \frac n{p_j^e}\rfloor, j) + f(p_j^{e + 1}))$

$p_0$ 的话当 $0$ 处理就好咯。

$g(n, 0)$ 即为所求。

#include <cstdio>
#include <cstring>

typedef unsigned long long u64;

const int MAX_SQRT_N = 1e5;

struct euler_sieve {
    static const int MAX_N = MAX_SQRT_N;
    bool f[MAX_N + 10];
    int p[MAX_N + 10];
    int p_n;

    inline void operator()(int n) {
        memset(f, 0, sizeof f);
        p_n = 0;
        for (int i = 2; i <= n; ++i) {
            if (!f[i]) {
                p[++p_n] = i;
            }
            for (int j = 1; p[j] * i <= n; ++j) {
                f[p[j] * i] = true;
                if (i % p[j] == 0) break;
            }
        }
    }
} es;

struct Min_25_sieve {
    u64 n;

    u64 b[2 * MAX_SQRT_N + 10]; // 所有可能的 n / i 值，值是从大到小的（废话）
    int b_n, sqrt_n;
    inline int locate(u64 i) { return i < sqrt_n ? b_n - i + 1 : n / i; } // 查找 b[j] == i 的位置 j 

    int d0[2 * MAX_SQRT_N + 10]; // 存储 h 函数的值，数组命名个人癖好而已。 h 函数的取值只有 O(\sqrt n) 种。这里的第 i 个位置存储的不是 h(i) 而是 h(b[i])
    inline void pre_calc() { // 计算 h 函数
        for (int i = 1; i <= b_n; ++i) d0[i] = 1 * (b[i] - 1); // h(b[i], 0) ，j = 0 理解为没有“i 的最小质因子 > p_j”这条限制即可。这里以及下面的 1 * 代表的就是 i^k （本题中 k = 0（不是输入的那个 k 啊））
        for (int j = 1; (u64)es.p[j] * es.p[j] <= n; ++j) { // 枚举质数
            for (int i = 1; (u64)es.p[j] * es.p[j] <= b[i]; ++i) { // 枚举了有用的，即 b[i] 
                d0[i] = d0[i] - 1 * (d0[locate(b[i] / es.p[j])] - d0[locate(es.p[j] - 1)]); // 一定有 p[j] - 1 < \sqrt n ，所以一定可以找到一个合法的位置（不会落在一个段内） // 由于 b[i] 的值是从大道小的，所以求值顺序是没有问题的，不用开另外一个缓存数组
            }
        }
    }

    u64 f_a0_k;
    inline u64 f_a0(int e) { return e * f_a0_k + 1; }
    inline u64 f(int p, int e) { return f_a0(e); }

    u64 calc(u64 n, int m) { // 计算 g 函数
        u64 rst = f_a0(1) * (d0[locate(n)] - d0[locate(es.p[m])]);
        for (int j = m + 1; (u64)es.p[j] * es.p[j] <= n; ++j) {
            u64 pe = es.p[j];
            for (int e = 1; (u64)pe * es.p[j] <= n; ++e, pe *= es.p[j]) {
                rst += f(es.p[j], e) * calc(n / pe, j) + f(es.p[j], e + 1);
            }
        }
        return rst;
    }

    inline u64 operator()(u64 n_, u64 f_a0_k_) {
        n = n_;
        f_a0_k = f_a0_k_;

        // 分块
        sqrt_n = 0; while ((u64)sqrt_n * sqrt_n < n) ++sqrt_n;
        b_n = 0; for (u64 i = 1; i <= n; i = n / (n / i) + 1) b[++b_n] = n / i;

        // 处理辅助求和函数
        pre_calc();

        // 求和
        es.p[0] = 0, d0[b_n + 1] = 0;
        return calc(n, 0) + 1; // + 1 是那个甩单的 1 
    }
} mns;

int main() {
    // freopen("in.in", "r", stdin);

    int tc; scanf("%d", &tc);
    // int tc = 1;
    es(MAX_SQRT_N + 5); // 筛出质数
    while (tc--) {
        u64 n, f_a0_k; scanf("%llu%llu", &n, &f_a0_k);
        printf("%llu\n", mns(n, f_a0_k));
    }

    return 0;
}

要结束了啊。

NOIP 2018 394 分，当时无知的我还认为这个分数可以，殊不知强省们的选手早已在 500 分以外。不，其实我知道，只是我不愿意承认呐。3 年的时光被我荒废掉了，1 年的时间我依然没有紧紧抓住。到现在了，一切，都马上要结束了。

没有清华北大冬令营的邀请，对于我，如果想要通过竞赛的道路去到清华北大，剩下的，只有 NOI 金牌了啊。

但是，没有但是啊。自己的水平怎么可能会在接下来那仅仅 6 个月内赶上比我领先了太多太多了的人呢？

怎么会呢？

那就让一切结束了吧。

1 月 24 日的 CCF 冬令营，这会是我最后一次考试。在广二这个学校，第一次，也是最后一次了。

祝福，祝福跟我一路走来的同学们。

祝你们能在 2019 年的 NOI 的赛场上取得一个好的成绩，路上小心，加油！

感谢，感谢一路上支持我一步一步走过来的老师、家长们。

虽然没有让你们见到我在 NOI 赛场上的那一刻，但是我这长又短的 OI 生涯中，你们给予了我知识，最重要的还有温暖与陪伴。

愿我们来年有幸再会。

lookas2001

1 月 6 日 于广州

变化，这是我对今年 NOIP 的概括，从天津赛区的选址变为新校区，到 CCF 更新那个被无数选手诟病已久的“老爷机”，可以看出来 NOIP 的不断完善以及受重视程度不断提高。废话不多说，谈谈本次考试的想法吧。

Day 1

第一题铺设道路，一道简单的贪心，随便打个树状数组 30min A 掉切下一题（其实时间要比 30 分钟长）。

看到了第二题，艹，数学题，还是去年小凯的疑惑加强版。不过简单的分析一下可以发现如果一个数能被其他数表示，那么这个数字一定是没用的，否则是一定是有用的（“显然”），手玩了几组样例，发现思路正确，然后打了一个筛，1h A 掉完事切下一道题。这里的筛有一个坑，就像欧拉筛一样，必须做一个标记，否则复杂度无法保证那就妥妥的 T 了。

然后去厕所呼吸一下新鲜空气，大概 2.5h 过去了。

看第三题，读了两遍题发现是树形动态规划，可惜我的树形动态规划是上周学的，敲掉暴力，写个对拍，弄几组测试数据测试一下，交卷。

今年 Day 1 的题目看网上的说法是都撞题了，不过可惜我都没做过（zg dalao 两个月 A 掉 300 道题目 %%% 啊）。

Day 2

读了一遍题，发现第一题的数据特别神奇，是一个单环树，考虑断环上边然后枚举去做，这样复杂度已经 O(n^2) 了，可是还要求最小，所以考场上的想法就是每次都排一遍序，O(n^2logn) ，考虑到今年 CCF 换评测机，外加由于每次排序改变的东西并不会非常多，所以就这样了，没有细想。好在命大，最后拜托了我“优秀”的卡常技巧，居然卡过去了。具体来讲用 vector 存边的都 T 了…

第二题，艹，又是数学题，不过由于心太高，所以在这道题上犯了一个考场上一定不能犯的错误，就是硬抗，事实证明，要不是我福大命大，最后 30 分钟 T3 调出来了，否则就凉凉了，这道题目浪费了我足足 1 个小时，不过最后还是果断换题了，减少损失，最后一道题目敲出来了以后回来发现有几组白痴数据，手敲了一个表，交了上去，最后在基础的暴力分上只扣了 5 分，感谢 CCF 弱数据…

第三题，这是 NOI Plus 吧…不会，敲了一个暴力交了上去。

总结

总体来讲体验还算可以，但是之前犯的错，这次又犯了，时间规划真的非常非常非常重要啊！

另外感觉这次比赛自己的码风非常吃亏，因为我一直坚持的代码可读性原则导致我的代码普遍比别人长 2 倍以上，这个可能要改一下了，毕竟打的是竞争性的比赛，而不是长久维护的工程。

394，近 400 分的成绩对的起我一年的付出，我已经非常满意了。

NOI 2019 我们明年见！

图为 NOIP 2018 天津考场，天津大学北洋园校区。

午后，阳光射进自习室，温暖而不刺眼。与那些进队的物理化学同学们坐在一个地方，一同为这自己的目标奋斗，这大概是人生最好的时刻了吧。

但是，我跟他们不一样，我只有这一次机会了。成还是败，就在这一举了。

我不是一个普通的孩子，我一定会做出自己的事业。这是我一直告诉我自己的，过去是，现在是，将来更是。

加油，抓紧每一分时间，奋斗！

这是 lookas2001 写作计划的第一篇，同时也是 lookas2001 尝试系列中的一部分。

在 lookas2001 尝试系列中，我会了解并且学习各种我之前没有或者不敢尝试的能力，尽力的拓宽我的知识面，锻炼我的认知能力，并且为这个庞大的世界作出一些微小但也可能很伟大的改变。

6月1日，国际儿童节。这是我的第17次儿童节，对于我来说，这可能是我在成年以前过的倒数第二次儿童节了。很显然，我不再是当年那个清纯可爱的我了，但是我在想，为什么我不是了，有哪些变化，以及我得到了什么亦或是失去了什么。为了纪念我已经度过的童年并且即将逝去的青春，以及作为这个系列的开篇，为之后的探索提供一个方向。在这里，我写下这篇文章。

首先，回答开头提出的问题，我认为，最大的变化是：我失去了我一直引以为傲的好奇心。没错，不是其他，虽然我知道这个世界仍然很大，但是，慢慢的，我越来越懒得去探索世界，不再愿意迈出步子，走出我的 comfort zone。越来越固化的学习及生活，日复一日的面对着电脑，令人头疼的社交，这种事情令我感觉越来越无趣，正因如此，我的时间度过的时间变得越来越快，恍惚间，时间就过去了。这就如同一个会直立行走的僵尸，没有好奇的生活会变得令人生厌，疯狂。哦，我的上帝，这真的是一件令人可怕的事情。

如果说事物的发展是拜人类的智慧所赐，那么人类的智慧正是由好奇所赐。早在19世纪，马克思创造的马克思主义哲学中有这么一句话：“事物内部的矛盾是事物发展的源泉和动力。”现在看来，仍然有着很强大的参考意义，人正因为不了解自己不清楚的事物，才去进行的探索。作为世界发展的新生力量，好奇永远都是最重要的。如果需要为人类的能力排个序，那好奇绝对可以排入第一批次。正如维基上所说的那样：“好奇和人类各层面的发展都高度相关，有好奇才会引发学习的过程，以及想要了解知识及技能的欲望。”她强烈的推动着人类的发展，人类的发展离不开好奇。

我们耳熟能详的各位为人类科学事业在自然以及人文学科奉献出巨大贡献的大师们，没有不拥有着强大的好奇心的。举世界名校MIT的例子，这里的孩子们热爱恶作剧，其校方甚至为其恶作剧特意制作了一个恶作剧博物馆，这让常年接受要做一个乖宝宝的教育的我们无法理解这个恶作剧文化，但是与此同时，我们应该想到，这些制作恶作剧的孩子们为了制作一个吸引眼球的，创意奇特的恶作剧，挖空了多少心思，这正是好奇给他们提供的推动力。这些人成长为成人的结果就是为美国的持续的繁盛提供了不懈的动力，使美国至今为止仍然是世界上最强大的国家。

就像枯木、硬石一般，一个人失去了好奇意味着他失去了探索改变自身以及世界的能力，一个国家或者民族失去了好奇更会是一个国家政权更替或者是民族没落的标志。历史上有何其多的将军因为固化思维吃了败仗的亏，有多少国家因为不考虑新想法结果强盛没能持续几年就没落了，现在社会中又有多少人失去了探索的能力，碌碌无为，搬砖搬了半个辈子，到了人生的末尾的追悔莫及的。

在最后也祝愿每一个人能保持住自己探索世界的本能，持续不断的好奇，并且不放弃改变世界的努力。当然我也希望能阅读到这里的读者们，时刻反思，是否停下了发现的步伐，是否安于现状并且不愿改变，是否放弃了思考的能力。

儿童节快乐！

好奇心万岁！

完

http://acm.hdu.edu.cn/showproblem.php?pid=3016

算法设计

拿到题二话不说，先把这些木板按照其高从小到大排个序，然后我们给木板从下到上从1开始递增编号（我们认为最下面的地板编号为0），通过这样的一个步骤，显然，越高的木板序号越大。

根据题意，如果人在一个木板上，他只可以从这个木板的左端或者右端垂直下落。我们定义 d[i] 为当这个人到达第 i 个板的时候最大生命值。如果我们知道 d[i] 的值，我们就可以推出其左端或者右端下落到的板子相应的值。（d[j] = d[i] + 跳到 j 板上生命值的变化量）。这样，我们可以从上往下递推的求解。

但是我们如何知道这个人他在左端或者右端下落会落到哪里呢？我们可以对 x 轴根据点建立一棵线段树，然后从下往上根据木板对这个 x 轴“染色”（即对木板所覆盖的地方标记上自己的序号），这样的话，在往上推进的过程中，很方便就能求出一个木板左右端跳下去会跳到哪个板上。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 110000, L = 110000, INF = 0x7fffffff;

int n;

struct a_d {
    int h, l, r, v;
    int ld, rd; // left down to 
} a[N];

inline bool cmp(a_d a, a_d b) {
    return a.h < b.h;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * L];
node *memp;
node *root;

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1; 
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r);
    }
    return p;
}

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f = p->f;
        p->rc->f = p->f;
        p->f = 0;
    }
}

void change(node *p, int l, int r, int f) {
    if (l <= p->l && p->r <= r) {
        p->f = f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r, f);
    if (mid < r) change(p->rc, l, r, f);
}

int query(node *p, int i) {
    if (i == p->l && p->r == i) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int d[N]; 

inline int max(int a, int b) {
    if (a > b) return a; else return b;
}

int main() {
//  freopen("input.txt", "r", stdin);

    while(scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &a[i].h, &a[i].l, &a[i].r, &a[i].v);
        a[0].v = 0;

        std::sort(a + 1, a + n + 1, cmp);
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].l, a[i].r); printf("\n");

        memp = mem;
        root = init(0, 100010);
        for (int i = 1; i <= n; ++i) { 
//          printf("%d %d %d\n", i, a[i].l, a[i].r);
            a[i].ld = query(root, a[i].l); // 注意这里不 +1 -1
            a[i].rd = query(root, a[i].r);
            change(root, a[i].l, a[i].r, i);
        }
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].ld, a[i].rd);

        for (int i = 0; i <= n; ++i) d[i] = -INF;
        d[n] = 100 + a[n].v;
        for (int i = n; i; --i) {
            if (d[i] <= 0) continue;
            d[a[i].ld] = max(d[a[i].ld], d[i] + a[a[i].ld].v);
            d[a[i].rd] = max(d[a[i].rd], d[i] + a[a[i].rd].v);
        }

        if (d[0] > 0) printf("%d\n", d[0]); else printf("-1\n");
    }

    return 0;
}

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？

这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入

第一行：一个整数N，表示项链的长度。

第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。

第三行：一个整数M，表示HH询问的个数。

接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

N ≤ 50000，M ≤ 200000。

输出

M行，每行一个整数，依次表示询问对应的答案。

样例输入

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出

2
2
4

来源

SDOI 2009

在线评测

lydsy

vjudge

算法设计

看到题目，首先想了想所学的数据结构，当前还没有如此高级的数据结构可以求任意的一个区间内有多少种数字。那么我们试试能不能在确定一个端点的前提下，通过简单的数据结构得到结果。

这道题目我们需要离线处理，将所有的查询根据右节点从小到大排序，使其变得有序后进行操作。

我们定义一个变量 k 为当前推进（或者说枚举）到的右节点，定义一棵线段树，第 j 个节点的含义为 j-k 内不同的数字个数

我们定义一个数组 last 数组，第 i 个元素为 第 i 个贝壳序号 在 贝壳序列中 上一次出现的位置。

我们可以发现，如果我们推进到了一个新的 k，很明显 1 ~ last[k] 到 k 这些段中一定是存在 第 k 个贝壳序号，而在 last[k] + 1 ~ k 到 k 这些段中是不存在的。那反映到线段树中 last[i] + 1 ~ k 所有节点都应该 + 1。

没听懂？没关系，可以看看下面的代码。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

//using namespace std;

const int N = 55000, M = 220000, MAX = 1100000;

int n, m, a[N];

int last[N];
int idx[MAX]; // 本来是 index 但是与头文件中的函数冲突了 

struct q_d {
    int l, r, id;
} q[M];

int result[M];

inline bool cmp(q_d a, q_d b) {
    return a.r < b.r;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root;

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1;
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r); 
    }

    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
} 

int query(node *p, int i) {
    if (p->l == p->r) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d", &n);
    memset(idx, 0, sizeof idx);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = idx[a[i]];
        idx[a[i]] = i;
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1, cmp);
//  
//  for (int i = 1; i <= m; ++i) printf("%d %d\n", q[i].l, q[i].r);

    int j = 1;
    memp = mem;
    root = init(1, n);
    for (int i = 1; i <= n; ++i) {
        change(root, last[i] + 1, i); 
        for (; q[j].r == i && j <= m; ++j) {
            result[q[j].id] = query(root, q[j].l);
        }
    }

    for(int i = 1; i <= m; ++i) printf("%d\n", result[i]);

    return 0;
}