这是另一个讲稿，第一个是 扫描线方向和dp转移结构。计划搞定之后给小朋友们讲。但是可能还要做大量的题才会有很多这方面的题扔进来（
收录了一些离奇题，在你做完之后才会去尝试分析复杂度。当然很多可能对提高组选手来说并不离奇（
sdptt2021 r2 day4 B. 今天
好像是dls的题?但是不知道原出处（
给\(n,m\)，求\((0,0)\)走到\((n,m)\)的单增下凸函数的曲线，最多经过多少格点。\(n,m\leq 3000\)。
呃你可能需要理解一下题意（
考虑它是光滑的没有什么用，我们把经过的格点连起来得到一条折线，根据这个折线肯定可以构造出一个光滑的，于是只需要考虑一条每经过一个格点都必须往上拐一下的折线。
直接dp，设\(dp(i,j)\)表示走到\((i,j)\)的答案，从小到大枚举一个向量，对全局进行一次转移。状态数是\(n^2\)，总复杂度是\(n^4\)。
打表观察一下，你发现答案很小，一会我们会证明它是\(n^{\frac{2}{3}}\)级别。这就很有趣，于是我们先维度交换一下。
注意到一个性质，如果我们要选一个很长的向量，只可能是短的都选完了。进一步，如果选了向量\((x,y)\)，那么所有\(x^\prime\leq x,y^\prime\leq y\)的\((x^\prime,y^\prime)\)也要选。这样看起来就有很多向量是完全选不到的。
可以进行一个简单的分析，注意到所有这些\((x^\prime,y^\prime)\)的\(x^\prime\)之和是\(x^2y\)级别，\(y^\prime\)之和是\(xy^2\)级别，有一个超过\(n\)就不能选，也就是\(xy\max(x,y)>n\)就不能选。这样的向量有多少呢?搜一搜你发现很少，于是就过了。
接下来我们分析这个个数。考虑钦点\(x>y\)，硬算。
\[\sum_{x=1}^\sqrt{n}\min(x,\frac{n}{x^2})\]注意到这个\(\min\)在\(x=\sqrt[3]{n}\)时切换。
-
当\(x>\sqrt[3]{n}\)，后者是\(\min\)，转成积分可得\(O(n^\frac{1}{6})\)。
-
当\(x<\sqrt[3]{n}\)，前者是\(\min\)，直接等差数列求和可得\(O(n^\frac{2}{3})\)。
那么最后就是\(n^\frac{2}{3}\)了。实际上显然可以看出来后者更大?反正这个界还挺好的（
于是因为向量只有\(n^\frac{2}{3}\)级别，答案也只有\(n^\frac{2}{3}\)级别。最后总复杂度只有\(O(n^\frac{7}{3})\)了，可以通过。
这个分析应该还比较套路，只是如果你没见过你可能不敢分析（
ppt中给出了奇怪的莫反的分析，好像避免了积分(然而观察也可以避免积分?)。
XVII Open Cup, GP of Romania B. Entanglement
给一个\(n\times m\)的矩阵和常数\(k\)，求有多少对长\(n,m\)，值域都在\([1,k]\)的序列\(a,b\)，满足矩阵中每个位置\((i,j)\)，和\(a_i,b_j\)中至少一个相等。\(n,m\leq 300\)。
考虑直接搜，考虑先确定\(a_1\)，如果它不等于第一行的某个数\(j\)，那么\(b_j\)必须是这个数。至于\(a_2\)，如果它不等于第二行的某个数\(j\)，并且\(b_j\)还没确定，那么\(b_j\)必须是这个数，否则要么不合法要么不用管。
考虑怎么求这个东西的复杂度，它是\(T(n,m)=T(n-1,0)+\sum_{x}T(n-1,c(x))+O(nm)\)，其中\(c(x)\)是\(x\)在这一行的出现次数，\(nm\)是我们确定一列之后需要把已经合法的标记上。
可以证明这个复杂度不超过\(n^2m\)。因为\(c\)的总和是\(O(m)\)，所以递归树上每一层\(m\)的总和是不变的，一共有\(n\)层，所以总共就是\(O(n^2m)\)。
上网搜一搜，你会发现Claris的blog上这个题留坑了（
JOISC 2017 Day3 B. Long Mansion
有\(n\)个房间排成一排，每个里面有若干把钥匙，相邻两个房间之间有一扇门，钥匙和门各有一个种类，拿着一把钥匙可以打开同种的门。多次给出\(x,y\)，问你一开始在房间\(x\)，可以任意移动并捡起所有经过的房间的钥匙，最后能不能到达房间\(y\)。\(n,q\leq 5\times 10^5\)，钥匙总数\(\leq 5\times 10^5\)。
考虑如果A可以到B，那么从B出发可以到的房间A都可以到。
然后考虑每个房间能到的都是一个区间。
于是这些房间被划分成了若干个scc，每个scc可以互相到达，而scc之间可以用若干条有向链来描述，每个scc连向左右可以到的第一个scc。然后在这上面就容易统计答案了。
为了但是你发现找到这些scc是困难的，于是我们换个想法。
考虑一个牛逼想法，如果允许\(n^2\)，我们直接记搜就行了。
强行缩减状态数，我们只保留每个房间能到的区间，然后对每个房间进行扩展，如果A可以走到B，那么就递归计算B可以走到的，然后把它并入A。如果在这个过程中B又可以走到A了，就形成了环，于是A和B能走到的范围是一样的，于是这个更新一定不优，我们不需要尝试用A更新B，直接返回就行了。
考虑一个牛逼方法来判断能不能走一步。我们对于每个房间求出要往左走，最右边至少需要到达哪个房间，也就是对于这个房间左边的门，右边第一把能开它的钥匙在哪。往右走也是一样的。
现在分析复杂度。考虑一个离奇的事情，每个门只会被左右最近的能走到它的房间各穿过一次，剩下的都被记忆化掉了，这显然很对。
但是总感觉还有哪里没有分析。想了想你发现，虽然每个门只会被左右的房间各穿过一次，剩下的都被记忆化掉了，但是取记忆化的结果也是有代价的。
不过注意到每个记忆化的结果也只会被取一次，因为如果\(i<j<k\)，\(j\)能到\(k\)，\(i\)也能到\(k\)，\(i\)就不会取\(k\)的结果了，在取\(j\)的结果的时候直接就吞过去了。可以用我们刚才说的那个scc来理解这个，scc之间是若干有向链，走一步相当于在上面路径压缩了一段。
于是总复杂度就是\(O(n)\)。非常牛逼（
JOISC 2017 Day4 A. Abduction 2
有一个\(h\times w\)的网格，每条横竖线都有一个权值(一共是\(h\)条横线，\(w\)条竖线)，权值互不相同。每一段的长度都是\(1\)。
你从某个交叉点，向着上下左右任意一个方向出发，每走到一个交叉点，如果你正沿着走的路的权值比另一个方向那条路的权值小，那么你必须拐弯，不过你可以选择往左还是往右拐；否则你必须直行。多次给出起点，求最多可以走多少步。\(h,w\leq 5\times 10^4,q\leq 100\)，5s，可以加强到\(q\leq 1000\)。
离奇题。
简单想法是记搜。
离奇性质是，记搜的时候，你只会搜到\(O(h+w)\)个不同状态，并且还不紧。于是套一个二分/根号平衡上去找下一个拐弯的地方，手写一个hash table来记忆化，就秒了。
接下来我们来看一看这个事情为什么这么合理。看我画图。但是如果你只是看到我的blog怎么办呢?你可以看一看官方题解的图，那个比我画的好（
总之就是，我们bfs的话，每一层只有最多四个状态，在这上面归纳就行了。你可以手动讨论一下，这不是特别复杂。
离奇的事情是，在多测下这个东西有更为出色的表现，我完全没看懂官方题解的分析，如果有兴趣你可以自己去看一看。