lookas2001

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;
}

http://codeforces.com/contest/833/problem/B

NOTICE

推荐在写这道题前看看 HH 的项链 解题报告（SDOI 2009 线段树 排序 离线处理）

算法设计

拿到题，3分钟，这是一道动态规划。写码，调试，提交，一气呵成，最后发现在第4个点超时。转过头来看，发现在处理每一个状态的时候套着一个循环，导致整体算法复杂度 O(n ^ 3) 遂放弃。

最近学习了线段树，然后再看这道题，发现了这道题在求不同数字的个数的时候进行了很多不必要的重复运算，可以用线段树解决。

由于本人的描述实在不行，具体解决方案请直接看下面代码以及其注释，先粗略看一遍全局变量的定义，然后再看一下main函数。

配合这张图食用更佳。

示例代码

#include <cstdio>
#include <cstring>

const int N = 38500; // 35000 * 1.1 

int n, k, a[N]; // 题目中提供的数据 

int last[N]; // 记录该位置的数上一次出现的位置，last[i] 代表 a[i] 位置上的数在 a 数组中上一次出现的位置，如果没有出现过，则为 0 
int index[N]; // 用于辅助建立 last 数组 

int d[N]; // 动态规划中用于保留结果的数组， d[i] 代表在一次切割中（阶段），最后一个切割点（或者说是最后一个箱子装的最后一个蛋糕的坐标）的结果 

struct node {
    int l, r;
    int f;
    int max;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root; // 线段树中第 i 个位置的数 为 上一个阶段 d[i] 以及 i + 1 ~ j 中不同数字的个数 的和，其中 j 为当前推进到的位置，详见下方解释 

inline void push_down(node *p) {
    if (p->f) {
        p->lc->max += p->f;
        p->lc->f += p->f; // mistake: 就像傻子一般，线段树这里给写错了 
        p->rc->max += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

inline void pull_up(node *p) {
    if (p->lc->max > p->rc->max) p->max = p->lc->max; else p->max = p->rc->max;
}

node *init(int a[], int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
        p->max = a[l];
    } else {
        int mid = (l + r) >> 1;
//      printf("%d %d %d\n", l, mid, r);
        p->lc = init(a, l, mid);
        p->rc = init(a, mid + 1, r);
        pull_up(p);
    }
    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->max;
        ++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);
    pull_up(p);
}

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

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    int max = 0, tmp;
    if (l <= mid) {
        max = query(p->lc, l, r);
    }
    if (mid < r) {
        tmp = query(p->rc, l, r);
        if (tmp > max) max = tmp;
    }
    pull_up(p); // mistake:这里的pull_up是不可或缺的 

    return max;
}
//
//void debug2() {
//  for (int i = 1; i <= n; ++i) printf("%d ", last[i]);
//  printf("\n\n");
//}
//
//void debug1() {
//  for (int i = 0; i <= n; ++i) printf("%d ", d[i]);
//  printf("\n");
//} 

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

    scanf("%d%d", &n, &k);
    memset(index, 0, sizeof index);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = index[a[i]]; // 读取输入的过程中同时填充一下 last 数组，last 数组的含义见上定义 
        index[a[i]] = i;
    }
//  
//  debug2();

    // 动态规划，为了能够对动态规划中的一个阶段中的不同状态下的求解能够快速进行，我们使用了递推，这样求解的顺序可以利用线段树进行优化 
    memset(d, 0, sizeof d); // 不难发现最开始的结果都是 0 的 
    for (int i = 1; i <= k; ++i) { // 阶段，即切割或者说是箱子的个数 
        memp = mem;
        root = init(d, 0, n); // 线段树是可以从 0 开始建立的，详见下方解释 
        for (int j = i; j <= n; ++j) { // 枚举当前阶段切割点的位置 
            // 诚然，我们对于每一个切割点而言，我们都可以跑一次如下的循环 
            /* 
            int max = 0, tmp;
            for (int k = i - 1; k <= j - 1; ++k) { // 很明显 i - 1 之前的是不可能满足题意的 
                tmp = last_d[k] + different_num_between(k, j);
                if (tmp > max) max = tmp;
            }
            */
            // 但是这样太慢了，我们发现，计算从 k 到 j 的有多少个不同的数字这个函数被调用了很多遍，并且发现貌似每次都进行了许多无用的计算
            // 我们建立一棵线段树，定义为当推进到 j 位置的时候，线段树中第 k 个数为从 k + 1（加一是为了初始化方便） 到 j 中不同数字的个数
            // 我们可以发现，last[j] + 1 到 j 中间是没有 a[j] 这个数的（一句废话）
            // 那也就是说，如果我们的进度推进到了 j 的话，对于所有的 在 last[j] + 1 ~ j 中的位置到 j 的不同数字种类应该会多出一个 j ，反映到数量上，就是个数 +1 
            // 映射到线段树的时候别忘了位置 -1 
            //  
            // 我们还可以发现，如果说按照上述定义，求最大值仍然需要扫描整个线段树，因为在原始的线段树上我们还需要增加上一个阶段的结果
            // 那么我们索性就在线段初始化的时候，将 d 数组作为线段树最开始的初始化用数组，这样求最大值就可以用线段树舒服的求出来了（当然线段树写错了当我没说） 
            // 
            // 被绕晕了？可以翻上去看看定义那里的注释，并且根据代码理解一下 
            change(root, last[j] + 1 - 1, j - 1); 
            d[j] = query(root, i - 1, j - 1); // mistake: 请注意，这里必须是 i - 1 而不是 i 
        }
//      debug1();
    }
//  
//  // 哦，我的老伙计，这一坨被注释的代码是彻头彻底的错误 
//  int max = 0;
//  for (int i = 1; i <= n; ++i) if (d[i] > max) max = d[i];
//  printf("%d", max);
//  for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
//  printf("%d", d[n]); 

    printf("%d", d[n]);

    return 0;
}