## LIS
#优先队列 #序列dp
首先注意到每次从 $i$ 跳到 $j$ 其中的 $j$ 都会是最小的一个，因此不难维护一个优先队列，按照 $a_i$ 从小到大排序，附加维护编号 $i$。从前往后依次遍历每一个元素 $a_i$，规定优先队列里面维护的是所有 $a_j$ $(j<i)$ 的还没有进行没有转移的元素，此时我们在优先队列头依次取出若干个满足 $a_j<a_i$ 的元素，进行 $j\rightarrow i$ 的转移。那么问题来了，如何进行转移呢？
维护两个值 $f_1(i)$ 和 $f_2(i)$，分别表示以 $i$ 为结尾的转移序列的数量和总和，那么很显然 ${} f_1(i)=\sum\limits_{j\rightarrow i}f_1(j) {}$，而我们要转移到 $i$ 时 $j$ 的每一个序列都会在末尾增加一个元素，因此 ${} f_2(i)=\sum\limits_{j\rightarrow i}(f_1(j)+f_2(j)) {}$。初始时 $f_1(i),f_2(i) \leftarrow 1$。
现在我们已经算出了所有的 $f_1$ 和 $f_2$，该如何统计答案呢？实际上，我们可以在转移的途中顺便统计答案。对于 $j\rightarrow i$ 的转移，如果 $F(l,r)$ 中的 $r$ 正好 $\in [j,i)$，那么这个状态实际上是转移不了的，这时候就可以对 $j$ 统计答案了，$ans \leftarrow (i-j)*f_2(j)$。时间复杂度 $O(n \log_2 n)$。
对于最后无法继续转移但是没有被 $r$ 限制的状态，我们可以添加一个哨兵 $a_{n+1}=+\infty$，这样遍历到 $i=n+1$ 时就会全部转移。
```cpp
#include <iostream>
#include <queue>
using namespace std;
using LL = long long;
const LL kMaxN = 4e5 + 5;
LL a[kMaxN], f[kMaxN], dp[kMaxN], t, n, ans;
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
a[n + 1] = 1e18;
f[1] = dp[1] = 1;
for (; q.size(); q.pop()) { }
q.emplace(a[1], 1);
ans = 0;
for (LL i = 2; i <= n + 1; i++) {
f[i] = dp[i] = 1;
for (; q.size() && q.top().first < a[i]; q.pop()) {
f[i] += f[q.top().second];
dp[i] += dp[q.top().second] + f[q.top().second];
ans += (i - q.top().second) * dp[q.top().second];
}
q.emplace(a[i], i);
}
cout << ans << '\n';
}
return 0;
}
```
## 碰瓷
#序列dp
本题我的方法错误。
我最开始的方法是，枚举 $a$ 的每一个可能的起始点 $i \in [1,n]$，然后设计 dp 状态 $f_{j,k}$ 表示为 $a_{i\sim j}$ 可以与 $b_{1\sim k}$ 进行匹配，但是这个算法不仅转移困难，而且时间复杂度高达 $O(n^2m)$。
我成功地获得了 $0$ 分的好成绩的原因是我的转移过程写错了。具体而言，对于在 $b$ 中相同位置插入多个新元素的转移，我没有一个好的转移方式能够满足所有的可能。比如 $1$ 后面添加 $3$ 再添加 $1$ 这种。
## 旋律
#unknow
此题我采用的是暴力。
对于向前插入和向后插入的操作，我手动维护一个双端队列，分别用 $l$ 和 $r$ 表示队列的头和尾。为了防止一直往前面插入，我初始化 $l=r=10^6$，然后将数组大小初始化为 $2 \times 10^6$。
接下来考虑统计答案。观察样例，可以发现，如果我们选择前 $m$ 个数作为旋律，那么 $i \in (m,n]$ 的数都必须满足 $a_i=a_{i-m}$。因此我们使用 `vector` 的数组维护每一个 $i$，满足 $a_i=a_j(j<i)$，的 $i-j$ 的数量（即当前位置满足条件的所有的 $m$）。
然后进行倒叙枚举 $i$，使用一个表 $f$ 记录 $m$ 被"命中"的次数，将 $i$ 的我们之前记录过的所有满足条件的 $m$ 的值，对应的 $f_m$ 加上 $1$。如果有 $f_m$ 的值正好等于我们已经遍历过的元素数量（$r-i+1$），那么这个答案就是符合要求的。
我这个方法最坏时间复杂度高达 $O(n^3)$，因为虽然单次修改是 $O(n)$ 的，但是所有 `vector` 里面的元素数量最坏是 $O(n^2)$ 量级的（即所有字母都一样的情况），因此时间复杂度为 $O(n^3)$，只能通过 $40$ 分。
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int kMaxN = 2e6 + 5;
int f[kMaxN], n, l, r, ans;
char s[kMaxN], c;
vector<int> v[kMaxN];
void insertLeft(char c) {
s[--l] = c;
}
void insertRight(char c) {
s[++r] = c;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
l = 1e6, r = l - 1;
for (int i = 1, o; i <= n; i++) {
cin >> o >> c;
if (o == 1) {
insertLeft(c);
for (int i = l + 1; i <= r; i++) {
if (s[i] == c) {
v[i].push_back(i - l);
}
}
} else {
insertRight(c);
for (int i = l; i < r; i++) {
if (s[i] == c) {
v[r].push_back(r - i);
}
}
}
fill(f + 1, f + r - l + 1, 0);
ans = 1;
for (int i = r; i > l; i--) {
for (int j : v[i]) {
f[j]++;
}
ans += f[i - l] == r - i + 1;
}
cout << ans << '\n';
}
return 0;
}
```
## 非负
#unknow
这道题目我只骗了 $2$ 分，即 $a_i=(-1)^{i+1}$ 的情况。
对于这种情况，首先如果 $a_l$ 或 $a_r$ 等于 $-1$ 那 $[l,r]$ 肯定是不满足条件的，因为长度为 $1$ 的前缀和后缀不大于等于 $0$，此时我们直接 $l \leftarrow l+1$ 或 $r \leftarrow r-1$，这样因为 $a_i$ 是 $1,-1$ 交替出现，所以在我们操作之后 $a_l$ 和 $a_r$ 都是 $1$。
接下来，既然 $a_i$ 是 $1$ 和 $-1$ 交替出现了，那么前缀和后缀的值是 $1,0$ 交替出现的，满足条件，直接输出 $\max(0,r-l+1)$，成功获得 $2$ 分。
```cpp
#include <iostream>
#include <set>
using namespace std;
const int kMaxN = 5e5 + 5;
int a[kMaxN], p[kMaxN], dp[kMaxN], n, q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int o, p, l, r; q; q--) {
cin >> o;
if (o == 1) {
cin >> p;
a[p] = -a[p];
} else {
cin >> l >> r;
if (a[l] == -1) {
l++;
}
if (a[r] == -1) {
r--;
}
cout << max(0, r - l + 1) << '\n';
}
}
return 0;
}
```
## 总结
本次得分 $100+0+40+2=142$。
问题就是，第二题暴力写挂了，直接蒸发 $80$ 分；第四题最开始看错题了，写了一个小时之后才发现，后面就没有时间写正经暴力，连 $15$ 分的大爆搜也没写。
以后再次遇到像第二题这样的题目时，我应该更仔细地进行转移，避免犯同样的错误。同时稳住心态，多尝试不同的转移方式，因为我当时的状态设计和转移思路已经和正确的暴力 dp 一样了。下次再次遇到这种题目时，我应该更加冷静地思考，避免犯同样的错误，争取把该拿的分拿到手，之后再去写后面的题目。