我们考虑如果有一个 $2 \times 2$ 的子矩形，如果其中只有一个 `?`，并且它的填法是唯一的，我们就可以先填写它，我们称此过程为确定型填充。 很显然，我们可以一直执行确定性填充，直到不存在一个确定的子矩形。 这时，如果最终是有解的，我们随便填充一个 `?` 是可行的，因为填充任何一个 `?` 都不会导致任何一…

在讨论《询问map<string, int>复杂度》回复：

@[wangshengyue](luogu://user/1765131) 总复杂度和 $q$ 无关吗，雾。

在讨论《询问map<string, int>复杂度》回复：

@[zqrmon](luogu://user/1024331) 只调用了 `operator[]` he `count()`，没输出。

```cpp #include using namespace std; map a; int cnt; signed main() { int q; cin >> q; while (q--) { string s; cin >> s; a[s] = ++cnt; } return 0; } ``` 设输入的字符串总…

省流：单侧递归线段树+线段树二分，复杂度 $O(n\log n + q \log^2n)$。 我们在线段树上考虑维护： 区间最大值 $\max$，区间最小值 $\min$，**假想排序区间** $[ql, qr]$。 单点修改很好做，区间极值也很好维护，关键考虑如何合并子区间的**假想排序区间**信息。 记当前的点是…

在讨论《95pts 求条》回复：

@[Epitome](luogu://user/994729) Hack： .in ``` 1 114 ``` .ans ``` 1 ``` 所以只需要加特判 ```cpp if (n <= 2) { cout << n << '\n'; return 0; } ```

不妨设选出最强小队序列序列左端点 $l$ 和右端点 $r$，有 $a_l \le a_r$。 考虑枚举右端点 $r$，在 $r$ 左侧找到一个 $l$，对答案的贡献为： $$ g(l, r) = \max_{l a_r$，有： $$ g(l, r+1) \leftarrow g(l, r) + 1 $$ 所以，我们要进…

在讨论《关于如何将 sort 换成归并排序》回复：

@[MatchaNeko_nya](luogu://user/809765) 考虑 tmp 数组的排序规则就是按照 y 坐标升序。 你可以归并排序原数组，然后按顺序取出满足条件的点放入 tmp 数组。 所以是去排序原数组，然后取出 tmp 数组。并不是直接对 tmp 数组排序。

在修改点权时。 减贡献是：先递归，后修改。 加贡献是：先修改，后递归。 原因是靠考虑修改时需要用的是旧值还是值。 大概是像这样，不能把 `del()` 和 `add()` 写成一个函数。 ```cpp void del(int x) { int u = up[top[x]]; if (!u) return; auto…

## P5336 [THUSC 2016] 成绩单 考虑把代价拆分到每次分发：$a + b \times (y - x)^2$。其中 $x, y$ 分别为一次分发的最小值和最大值。 因为每次只能分发连续的一段，处理的区间只有包含和相离的关系，故可以使用区间 dp。 但是，这个题是一堆数的合并，并不能直接枚举断点直接做完…

在讨论《求助，只能过sub#3》回复：

- 应该且只能在本轮结束时清空桶数组（并非在开始）； - 因为本轮我们修改的桶，和查询的桶并不同； - 要保证每轮点分治桶数组都已经被清空。

rt，只能过subtask #3。 ```cpp #include using namespace std; const int N = 1e4+10, V = 1e7+10; vector > G[N]; vector a, b; // 询问的k bool ok[N], v[V]; // 点分树中的重心，桶数组 in…

我们注意到需要区间翻转，那大概率只能使用平衡树树了，这里我使用无旋 Treap。 这道题有一个棘手操作是查询区间出现的字母种类数，考虑到最多只有 $26$ 种字母，我们可以把出现过的字母状压到一起。 还有一个小问题就是如何求得原字母现在的排名。注意到，可以用平衡树的初始节点 $i\in[1,n]$ 来代表原字符串 $S…

## P4045 [JSOI2009] 密码 这道题考察 AC自动机。 关于多个字符串匹配可以考虑到 AC自动机 上跑 DP。 有几点注意： 1. 注意 Fail 树的祖先是已经跑过的子串。 2. 在记忆化的时候：区分 -1、0、1。尽量使用 `==` 号区分，不容易出错。 3. dfs 输出方案时要先保存在数组中，很…

```cpp #include using namespace std; const int N = 4e5; int a[N]; int root, tot = 2e5; int n, m; struct node { int l, r; int key; int book; int pri; // 大根堆 int…

在讨论《mxqz》回复：

你应该删掉倒数第四行`if(q<t)cout<<endl;`。

在讨论《莫名RE，求调试》回复：

@[Quantum_Graph](/user/541254) 本地不会，提交会

在讨论《莫名RE，求调试》回复：

@[Quantum_Graph](/user/541254) 谢谢，找出问题了：`input()` 函数的返回值应该是 `void`。

```cpp #include using namespace std; const int N = 5e5 + 10; const int R = 5e4 + 100; int head[N]; int step[N]; int vis[N]; pair p[N]; int n, m; int tot; struct…

```cpp #include #define int long long using namespace std; const int N = 1e5 + 10; pair > line[N*6]; // 原图边 bool vis[N*6]; int bcj[N]; // 并查集fa int fa[N][25]; /…

在讨论《对于排序细节的一个疑问》回复：

@[wjl_100930](/user/734249) 我们排序函数写的好像不太一样

在讨论《对于排序细节的一个疑问》回复：

@[WsW_](/user/349824) 感谢

在讨论《对于排序细节的一个疑问》回复：

这是两次提交记录： [88分 RE](https://www.luogu.com.cn/record/121379306) [100分 AC](https://www.luogu.com.cn/record/121384025)

下面的那个代码是 AC 的。 但如果我将排序函数的 “小于”变成“小于等于”,那么测试点 #12 会 RE。 不理解为什么会有这样的问题。 ```cpp #include using namespace std; const int N = 1005; int n; struct node { int a, b; in…

在讨论《68分求助，WA#1#4，码风较好，悬赏关注》回复：

数组开小了，此贴结。

在讨论《洛谷日报历年目录》回复：

[https://www.luogu.com.cn/blog/qss/shu-zhuang-shuo-zu](https://www.luogu.com.cn/blog/qss/shu-zhuang-shuo-zu)

不太清楚错在哪里，求助。 ```cpp #include using namespace std; const int N = 55; int a[N][N]; int n, m; int si, sj, ti, tj, dir; // WNES int dx[] = {0, -1, 0, 1}; int dy[] =…

在讨论《蒟蒻求助（悬谢）》回复：

@[魏蕴博](/user/800937) 你这样的方式是错误的，并没有把1~9都枚举到。

在讨论《题意不清》回复：

此题应该是如果其中一个矩阵的位置有 $-1$，那么另外一个矩阵对应位置也是 $-1$。

题目中说在**延时**的邻接矩阵中有 $-1$ 是没有连边，**丢失率**的邻接矩阵中有 $-1$ 是没有连边。那么如果同样两个点，会不会在两个矩阵中并不是同时出现 $-1$，如果有这种情况该如何处理。