提供一种新的思路。 首先把题意转化为用尽量少的一操作使序列不降，且首项非负。 显然有一个贪心是说从后往前考虑，如果当前数比后一个数大，就不断减 $D$ 直至恰好不大于后一个数。暴力做是平方的。 我们考虑把询问挂在左端点，从右往左做扫描线。扫到位置 $l$ 时，我们对 $r \in [l,n]$ 维护对 $[l,r]$…

在讨论《区间加区间最长上升子序列可做吗》回复：

应该是不可以的。 静态排列区间 lis 是 [这个](https://www.luogu.com.cn/problem/P2075)。

在讨论《求助思路》回复：

[楼房重建](https://www.luogu.com.cn/problem/P4198)

https://www.cnblogs.com/suxxsfe/p/15878024.html

- [题目链接](http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2255&pid=0) --- ### 法一 折半，转化为两个集合两两数之间 lcm 的和。转化过程复杂度为 $m^{\frac{n}{2}}$，实现不好可能会带个求 gcd 的 log。 之后便…

先考虑暴力怎么做。我们按照最小化字典序一般化的思路，从前往后依次贪心地使当前位置的值最小，即：若我们当前在确定 $a_i$，就找到最小的 $a_j$ 满足 $i \leq j \leq n,a_j-\min\limits_{k=i}^{j-1} \leq k,\max \limits_{k=i}^{j-1} -a_j…

在讨论《PA Mashup #2 赛后总结》回复：

@[pp_orange](luogu://user/224443) 这个 F 是不是 cf 上有[几乎一样的题](https://www.luogu.com.cn/problem/CF982F)啊，这题是 *2700。

考虑根号分治。我们把 $k$ 相同的询问放在一起考虑，分以下两种情况： ### case 1 $k$ 在序列 $a$ 中出现次数大于 $\sqrt n$。则这样的 $k$ 只有 $\sqrt n$ 种。此时我们对每个给定区间直接求出区间内 $k$ 的个数，查询直接就是区间 $\max$。由于需要初始化 $\sqrt n…

在文章《题解：P11675 [USACO25JAN] Photo Op G》发表评论：

你说的对

### 前言 好像大家都是同一个难写做法，这里分享我一个赛时的简单做法。 ### 题解 一个初步结论是： - 路线一定形如 $(X,0) \rightarrow (x_i,0) \rightarrow (0,y_i) \rightarrow (0,Y) $ 。 这是因为我们绕路的目的是避开一些 $(x_i,0) \ri…

在讨论《不明白为什么 WA》回复：

@[Ascnbeta](luogu://user/767561) set 去重的问题，你的小于关系重载会把值相同的认为成相同。

在讨论《求助站外题》回复：

$f_{i,j}$ 表示 $1 \sim i$ 能否分为 $j$ 段，把第二维提到外层做三遍一维的 dp。 dp 转移考虑枚举回文中心 $r$，令其最长回文半径是 $d$，转移就是 $f_{r+1,\dots,r+d} \gets f_{r-1,\dots,r-d}$。把序列划分为 $\dfrac{n}{64}$ 段，…

- [原题链接。](https://www.luogu.com.cn/problem/P11444) --- 套路地，我们考虑求出 $f_{l,r}$ 表示把区间 $[l,r]$ **删完**能得到的最大贡献。之后我们再做一个简单的线性 dp 就能求出操作区间 $[1,n]$（可以不删完）能得到的最大贡献。 在删除区间…

对于一条合法路径，如果我们在身上有金币的情况下，走过了一个我们最终没有捡金币的格子，那我们不捡起之前的那一枚金币，而是在该格子捡起金币显然是一种不劣的策略。 故捡金币的格子显然是路径的一段后缀。这启示我们倒过来考虑，把问题转化为：初始从某边界格子携带一定量金币出发，每走到一个可以走且没丢过金币的格子就把金币丢弃，能否最…

在讨论《求问一道树上问题》回复：

@[born_to_sun](luogu://user/1030875) $2^{\frac{k}{2}}n \log n$ 咋做啊？

在讨论《建议升紫》回复：

我认为这题唯一的难点在于**相信这个 $O(n^8/n^9)$ 的做法能过**。

在讨论《论 O(n^8) 5s 过 30》回复：

我 n^9 1s 过了。

## T1 #### 题意 给定 $m$ 个限制 $(tp,l,r)$，其中： - $tp=0$，要求区间 $[l,r]$ 严格递增。 - $tp=1$，要求区间 $[l,r]$ 严格递减。 构造一个长度为 $n$ 的排列 $p$，满足尽量多的限制。输出任意一个合法的排列 $p$ 即可。 $n,m \leq 10^6$…

在讨论《建议评紫》回复：

很难不支持，我场上其它两题加起来花的时间都没这题多。

在讨论《为什么没有题解？》回复：

@[Cells](luogu://user/556908) 根据质数的稠密性， $\le r$ 最大的质数在 $r - \ln r$ 这个级别，这个数肯定和 $l$ 互质，所以答案至少是 $r-l- \ln r$ 这个级别。你直接枚举前一百个数个数和后一百个数更新答案就行。

## 题意 给定 $n$ 个数字串，进行 $k$ 次操作，每次操作在所有数位中任选两个不同位置交换，允许两次操作选择的位置完全相同。求 $k$ 次操作之后，对于所有可能的操作序列，最终数字串乘积的和，结果对 $10^9+7$ 取模。 对于 $100 \%$ 的数据，$1\leq n\leq 100,1\leq k\le…

在讨论《codeforces 改名规则》回复：

https://codeforces.com/blog/entry/137562 Could you please read the English by yourself？@[tornado01](luogu://user/716013)

### 一 有上界的插板法，即： $n$ 个物品分成 $m$ 份，每份小于 $k$ 个的方案数。 容斥，钦定 $i$ 份一定不小于 $k$ 个，于是我们先给它们选 $k$ 个，然后每一份无论钦定还是没钦定都转化为无限制，可以得到方案数： $$Ans=\sum\limits_{i=0}^{m}(-1)^i{n-ik-1…

在讨论《这种题咋想的啊》回复：

@[IgalltaLover](luogu://user/740260) https://www.luogu.com.cn/article/nfy71dg0

怎么都是神秘结论。来个正常贪心。 我们考虑倒过来，将原序列变为全 $0$。 先对原序列 $A$ 进行一遍差分得到差分序列 $A'$。注意到环上一次区间减 $1$ 操作对应到差分序列 $A'$ 上可能为以下两种： - $A'_{i} \gets A'_{i}-1,A'_j \gets A'_j+1(1 \leq i us…

- [原题链接](https://www.luogu.com.cn/problem/AT_arc153_e)。 --- 怎么都是区间 dp，怎么都是网格图。这里是一个更自然的想法。 对于这一类双端队列插入队首/队尾的问题，一个经典转化是：**新序列 $Y$ 是由老序列 $X$ 选择一个子序列沿一号元素翻折得到的**。…

 如图，请问为啥 ak 了金组之后没有晋级按钮（Promote me)啊？

在讨论《预测一下》回复：

别水了

在讨论《幽默大样例》回复：

完蛋，这么说我的代码根本没有测。

在讨论《建议降绿》回复：

我t1七十分钟，t2十分钟