ascend
\(1\sim 4\)
注意到我们只关注当前填了几个数，已经有哪些数填了，上一个数填的是什么。
不难使用状态压缩 dp，设 \(f_{i,S,j}\) 表示填了 \(1\sim i\)，用了集合 \(S\) 里的数字，其中 \(p_i=j\)。
直接按照题目意思模拟即可，是 \(O(n^32^n)\) 的，但是一个状态合法必须满足 \(i=|S|\)，复杂度为 \(O(2^nn^2)\)，期望得分 \(20\)。
\(5\sim 7\)
不难发现，最终做贡献的是 \(w_i\) 而并非 \(p_i\)，其实可以只考虑他们之间的相对大小关系。
考虑如何生成一个排列，初始有一个 \(n=0\) 的空排列，每次插入一个 \(1\le x\le n+1\) 的 \(x\)，并将排列中 \(\ge x\) 的数加一，最终即可得到一个排列。
设 \(f_{i,j}\) 表示一个大小为 \(i\) 的排列，第 \(i\) 个插入的数字为 \(j\)，直接枚举上一个插入的数字 \(k\) 即可转移，复杂度为 \(O(n^3)\)，可以用前缀和优化到 \(O(n^2)\)。
\(8\sim 13\)
考虑拓展 A 性质做法，不难发现瓶颈在于我们在 dp 过程中维护的是相对大小（或者说排名），但是在 \(p_i\ne 0\) 的位置需要填的是确切的值。
题目实际上还给了一个关键的信息没有使用，即非 \(0\) 元素为单调递增。考虑重新设计一个状态，在保留排名的同时能表示某个位置填入的具体值。
设 \(p_{0}=n,p_{n+1}=n+1\)，就变成 \(n+2\) 的排列。
设 \(l_i\) 为 \(i\) 之前第一个不为 \(0\) 的数字。\(f_{i,j,k},g_{i,j,k}\) 表示 \(1\sim i\) 已经填入一些数字，其中 \(\le l_i\) 的数字已经确定，而 \(>l_i\) 的数字只维护排名，\(j\) 表示有 \(j\) 个 \(\le l_i\) 的数字没有被填入 \(1\sim i\)，\(f\) 这个状态表示 \(p_i\le l_i\)，\(j\) 个未用的数字中有 \(k\) 个数字 \(\le p_i\)。而 \(g\) 这个状态表示 \(p_i>l_i\)，且 \(p_i\) 在所有 \(p_i\) 在所有 \(>l_i\) 的数字中排名为 \(k\)。
感觉可能有一点绕，其实无论 \(f\) 还是 \(g\) 都是在维护 \(p_i\) 的排名，限制 \(p_i\) 在非 \(0\) 位置能取到具体的值则是通过 \(j=k\) 的状态来表示（\(f_{i,j,j}\) 即表示这个状态的 \(p_i\) 顶到了上界 \(l_i\)）。对于 \(l_i\) 在 \(i\) 向右移动的过程中发生改变的情况，实际上是将一些相对值关系确定的位置变成绝对关系确定，有点类似一个贡献延后计算。
实际上 \(f,g\) 两个 dp 数组是可以互相贡献的。
若 \(p_{i+1}\ne 0\)：填入 \(p_{i+1}\) 的数字可能 \(>l_i\) 或者 \(<l_i\)。\(f\to f,f\to g,g\to f,g\to g\) 四种转移都可以进行，\(f\to g,g\to f\) 无论前后两个数填的什么排名，大小关系一定。而 \(f\to f,g\to g\) 则在内部比较排名。
若 \(p_{i+1}=0\)：填入 \(p_{i+1}\) 的数字一定 \(>l_i\)，对于这一步，为了方便处理，先 \(f\to g',g\to g'\)（相当于填入大于 \(l_i\) 的数，转移方法和上面一样），然后 \(g'\) 转移到 \(f\)（这一步是让维护的信息类型相对从 \(l_i\to p_{i+1}\)）。具体的，枚举 \(p_{i+1}\) 在当前填入到 \(>l_i\) 的排名 \(r\)，然后把排名小于 \(r\) 的数字从相对确定为绝对，这些数字位于值域区间 \((l_i,p_{i+1})\)，直接用组合数去选择即可。
随着非 \(0\) 元素逐渐变大，维护的相对的值也在逐渐变大，确定的值域区间也在变大，最终填完整个序列。
前个部分的复杂度为 \(O(n^4)\)，后半部分的复杂度为 \(O(n^3)\)。
\(14\sim 20\)
瓶颈在于前半部分，可以前缀和优化，复杂度为 \(O(n^3)\)，组合数直接递推即可。
cake
Sub1
注意到查询次数多于值域。
可以放进去 \(100\) 个 \(1\)，此时 \(d\) 一定在最后一个位置。
每次选择前 \(w\) 个下标放入 \(S_1\)，最后一个下标放入 \(S_2\)，比较，找到第一个返回信息为 \(0\) 的位置即为所求。
Sub2
注意到询问次数为 \(1\)，为了区分三种结果，需要利用三种返回信息。
放进去 \(\{1,1\}\)，此时 \(d\) 一定在最后一个位置。
选择 \(S_1=\{0,1\},S_2=\{2\}\)。根据比较的返回信息讨论一下即可。
Sub3
值域变大了，不过注意到 \(\log_{2}(10^9)<30\)。
显然是和二进制或者二分相关，但是 \(d\) 在我们给定数列中的位置是不确定的。考虑构造一些 \(2\) 的次幂，先找出这个东西的位置，然后二分 \(d\) 的值。
构造这样一个数列，其中 \(s_0=1,s_{i}=2^{i-1}\)。
这个数列的一个特点在于 \(s_i=\sum_{j=0}^{i-1}s_j\)。而加入 \(d\) 后，如果 \(d\) 被插入到位置 \(x\)，\(s\) 从 \(x\) 后面都无法满足这个性质。
一个直观的想法是二分这个 \(x\)，然后就知道了每个位置的值是什么，直接二进制拆分去二分查询值即可，交互次数为 \(O(\log_2(\log_2(n))+\log_2(n))\)。
太蠢了，注意到求出 \(x\) 后，实际上只需要遍历前 \(x-1\) 个位置即可求出 \(d\) 的具体值，同理，实际上也可以直接倒着从 \(n\) 扫去找 \(x\)，这样交互次数就是 \(O(\log_{2}(n)+\text{eps})\)，这个 \(\text{eps}\) 很容易去掉，从 \(n-1\) 开始找即可。
Sub4
注意到 \(\log_{3}(2000)<7\)，结合 Sub2 应该是三分之类的东西。
注意到 \(W+200>3^7\)，非常的巧合，考虑传入 \(a\) 为数列 \(1\sim 3^7\)，然后求出 \(d\) 的位置 \(x\) 即可。
对于 \(i<x\) 的位置，满足 \(a_i=i\)，否则 \(a_i=i-1\)
考虑从高位到低位求出 \(d\) 三进制表示下这一位的大小。考虑最高位，查询第 \(3^6,2\times 3^6,3\times 3^6\) 这些位置。
若这一位为 \(0\)，返回信息为 \(3^6-1,2\times 3^6-1,3\times 3^6-1\)。
若这一位为 \(1\)，返回信息为 \(3^6,2\times 3^6-1,3\times 3^6-1\)。
若这一位为 \(2\)，返回信息为 \(3^6,2\times 3^6,3\times 3^6-1\)。
不难发现可以询问前两个之和和第三个之间的大小关系来区分这三种情况。
考虑递归求解子问题，已知 \(d\) 的三进制前缀为 \(r\)，查询 \(r+3^6,r+2\times 3^6,r+3\times 3^6\) 的大小，发现前面两个会多一个 \(r\)，直接用 \(3\) 的次幂抵消即可，可以证明当我们需要用到一个三的次幂 \(p\) 时这个 \(p\) 的位置一定小于 \(x\)。
gems
这个题，疑似涉及一些比较复杂的图论。
\(1\sim 7\)
最优方案一定是从 \(x\) 出发，然后向 \(a_l\) 走，走到第一个满足距离小于 \(d_l\) 的节点停下，然后 \(l\gets l+1\) 去收集剩下的宝石。
其实就是 \(x\to a_l\) 路径上倒数第 \(d_i\) 个节点，分类讨论转化为树上 \(k\) 级祖先问题。
预处理 \(to_{x,y}\) 表示从 \(x\) 出发，收集 \(y\) 宝石后在那个节点，直接 \(O(\log n)\) 即可计算，预处理复杂度为 \(O(nm\log n)\)。
查询直接模拟暴力，总复杂度为 \(O(nm\log n+qm)\)。
\(8\sim 10\)
被暴力冲过去了。
实际上就是在 \(to\) 上建立一个倍增数组即可，复杂度变成 \(O(nm\log n+q\log m)\)。
\(11\sim 25\)
好像也没有什么很有启发性的特殊性质。
前置理论：树上邻域。
在每个边上建立一个虚点 \(x\)，记 \(S(x,y)\) 表示距离 \(x\) 距离不超过 \(y\) 的点构成的点集，则对于两个邻域 \(S(x_1,y_1),S(x_2,y_2)\) 一定存在一个 \((x_3,y_3)\) 满足 \(S(x_3,y_3)=S(x_1,y_1)\cap S(x_2,y_2)\)。
设 \(dis(x,S)\) 表示 \(x\) 到一个邻域 \(S(a,d)\) 的最小距离，为 \(x,a\) 路径长度减去 \(d\) 和 \(0\) 取 \(max\)，且取到这个最小点的即为 \(x\to a\) 的路径上倒数 \(d\) 个点（因为有虚点，可能 \(d\) 需要微调一下）。
好的，注意到对于询问区间 \([l,r]\) 里两个相邻的邻域 \(S(a_i,d_i)\cap S(a_{i+1},d_{i+1})\ne \varnothing\)，则可以将这两个邻域替换成其交集。不影响答案。
问题，对于询问 \((x,l,r)\)，考虑求出最大的 \(p_l\) 满足 \(\cap_{i=l}^p S(a_i,d_i)\ne \varnothing\)，分类。
若 \(p_l\ge r\)：设 \(T=\cap_{i=l}^r S(a_i,d_i)\)，则从 \(x\to T\) 中的一个点即可，答案为 \(dis(x,T)\)。
若 \(p_l<r\)：设 \(T=\cap_{i=l}^p S(a_i,d_i)\)，则先从 \(x\to T\) 中的一个点，走最近的那个点，记为 \(nxt_l\)，并累加上 \(x\to nxt_l\) 的长度，然后 \(l\gets p+1,x\gets nxt_l\) 递归解决子问题。
瓶颈在于求 \(dis(x,S),nxt_l,p_l\)，考虑如何合并邻域，实际上根据第一条前置知识，可以 \(O(n)-O(1)\) 的 LCA 和 \(k\) 级祖先来 \(O(1)\) 合并。
然后倍增求出 \(st_{i,j}\) 表示 \([i,i+2^j-1]\) 内邻域之并，然后暴力跳倍增数组即可 \(O(\log n)\) 求出所有 \(nxt_l,p_l\)。
最后在 \(nxt_l,p_l\) 上建立倍增数组然后倍增跳即可。
复杂度为 \(O(n\log n+(m+q)\log m)\)。