迷一样的欧拉序列的题。然后似乎只有岛君的题解能看啊233。 其实就是在欧拉序列上，两点u,v之间的距离=(dfb[u], dfe[v]]之间未匹配的括号数（左开右闭）。其中dfb表示左括号的位置，dfe表示右括号的位置。 然后就是写一个线段树去维护了。写得比较丑，把所有数对都记下来了。其实只用记和跟差就行了。然后要强制如果一端是空的那么这个点就不能作为端点。完了。 然后dfs这一步越写越短了，开心hhh。 于是代码巨长还巨丑还巨慢。

我的SAM第一题。按照惯例几乎是照着std抄的OVO。本来以为是要在SAM上DP，后来发现好像是并列的，于是比较开心。 SAM这个东西主要就是用来匹配子串用的。建法详见clj的课件，然后现在我还处于消化状态中。 SAM匹配多个串的话也比较好弄，直接在串末再加一个字符集里没有的元素就好了。 现在假设已经用SAM匹配出了第i个位置往左ml[i]个位置都是可以匹配的，那么可以二分一个答案，然后用单调队列来DP判断。写法比较简单，虽然我急着去写SAM所以这部分也是蒙过去的。 然后网上的2个std就有2种不同的答案还和我不一样。最后还是wd学长的代码靠谱orz。 现在我可以说我是写过SAM的人了哈哈。

很早之前就看过的题。一直被数据范围吓到，然后感觉也比较难写所以都没写。后来发现还是挺好的。 就重链dfs序维护一下每个位置的和，然后可持久化一下就完了。然后一个常数优化是如果这个点是在这次修改的时候建的，那么就直接覆盖而不是新建点。然后跑得就比较快了。

上课讲的神题。构造公式。本来用HTML写了一堆公式的。然后天杀的网就断了要我重新开然后就没了。很想骂人。那就不写了呗，自行翻课件或者yy。

比较基础的dp。不过因为权限的原因好像做的人不多。 首先肯定先泡便宜的茶再泡贵的茶。 然后记一下上一种茶是啥，连续泡了几次。 于是用f[i][j][k][l]表示泡了i个红茶，j个绿茶，上一种茶是k，连续泡了l次的最小花费。转移是O(1)的。然后后两个反正都要手拆开，所以干脆压下来了。 似乎很水的样子。

水水的cdq。久了不写练一下手。然后发现犯了一堆逗错。幸好没过样例不然就do big die了。

多年之前讲过的最小割。 比较好想啦。 把每一位拆开。然后单独跑一遍最小割。各种连边。然后以答案为高位，数字和为低位跑就行了。 好像也没说清楚怎么建图啊。 对于原图中已经确定的点，如果它是1，就从源连过来，否则连向汇。对于每一个未知的点，把所有边建出来。然后再向汇连个1的边来表示它如果选1的话就要产生贡献。然后就差不多了吧。脑补一下。

原来备案还没过。那之前是怎么成功访问的囧。 写了一晚上。教训还是之前那个，写之前要想清楚。写完再去改就很烦。自己yy了很久，虽然最初是听了mhy的一句提醒。好有危机感。 首先这个东西可以离线。之前一直在想在线怎么做然后也觉得没法做。 把询问按右端点排序之后问题就转化成了左端点在一个范围里的时候的最大子段。 然后用一个线段树表示从i到current right的时候的和，这个玩意可以直接区间加。然后再去维护这个东西的历史最大值。于是就变成了每个位置上接了一个add序列，要找它的前缀最大值。那么只需要存两个东西：当前的和以及当前的最大前缀和，就可以合并了。 然后线段树上维护两个add序列，分别是对整个线段的lazy tag of add和max value of son。就可写了。 然后好像跑得很慢啊TT。

自己出的题还要写题解。 就是化成可以二分的形式，然后发现是找凸壳上x=x0的时候的最大值的和，看它是否大于0。 于是就写呗。据说很难写。我觉得写起来还行啊。 其实主要是为了测试系统用的。

<div class="post_brief"><p> 题目名字好长。</p>   当年在考场上只会分块打表的题。   前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。   于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。   考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久）   然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。   然后还是没有原版跑得快。OTL。   #define PROC "shop" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 53; const int maxm = 509; const int mb = 253; dint l, r; int n, m, bs, a[maxn];...