A-最长公共子序列转最长上升子序列模板题

传送门

模板题我就不写了。

本文juejin：https://juejin.cn/post/7223779544367497277/

本文CSDN：https://blog.csdn.net/hans774882968/article/details/130257010

作者：hans774882968以及hans774882968以及hans774882968

B-单调栈+贪心，好题

这题我不会……看的题解：https://blog.csdn.net/weixin_33863087/article/details/85941548 。现有题解一个比一个抽象，因此我写了一篇极为通俗易懂的题解~

单调栈

首先考虑区间[l, r]是“障碍段”的充要条件：f[r] <= l && g[l] >= r && r-a[r] == l-a[l]。这里f[r]表示a[r]为最大值的最左侧端点，g[l]表示a[l]为最小值的最右侧端点。这两个都是经典的单调栈数组。这个充要条件的思想就是用单调栈的经典数组去束缚住整个区间。

为了满足r-a[r] == l-a[l]这个条件，我们考虑按照x-a[x]+n划分整个数组，按组来求解。不妨把值为x-a[x]+n的下标集合记为p数组。具体来说，我们希望求出res[i]表示以i为右端点的最短障碍段的左端点（你也可以换成与之对称的定义），不存在则res[i] = 0。设当前遍历到idx0 ∈ p，那么我们需要求出最大的idx1 ∈ p使得g[idx1] >= idx0 && f[idx0] <= idx1。我们仍然使用单调栈来解决这个问题：

由定义，g[idx0] >= idx0，即g[idx1] >= g[idx0]是比g[idx1] >= idx0更苛刻的条件，那么我们不妨在求解“单调栈经典数组”的过程中顺便解决这个问题：即求出LL数组，LL[i]表示i左侧离i最近且g[LL[i]] >= g[i]的下标（LL实际上不会出现在代码里，只是方便理解）。代码如下：

void solve (int u) {sl = 0;for (int v : G[u]) {// R数组对应g数组while (sl && R[sk[sl - 1]] < v) --sl;// 因为栈底的下标更小，所以在当前点不满足L[v] <= sk[sl - 1]时，栈现存的点肯定也不满足，于是res[v] = 0。于是一个完整的单调栈while循环可写成拆为2个循环的形式if (L[v] <= sk[sl - 1]) res[v] = sk[sl - 1];while (sl && R[sk[sl - 1]] <= R[v]) --sl;sk[sl++] = v;}
}

贪心

res只是每个右端点对应的候选解，最终的“障碍段”需要满足两两互不包含。怎么做？我们先证明一个性质：障碍段之间要么相互包含，要么不相交。反证法：设l1 < l2 < r1 < r2是两个相交的障碍段，则根据障碍段定义有：a[l1] 大于a[l1]小于a[l2] a[l2] 大于a[l2]小于a[r1] a[r1] 大于a[r1]小于a[r2] a[r2]。于是可以得到更短的障碍段[l1, l2] [r1, r2]。

所以去除相互包含的情况，相当于去除相交的情况，可以用贪心来做：

    int ans = 0;for (int i = 1, j = 0; i <= n; ++i) {if (!res[i]) continue;if (j >= res[i]) res[i] = 0;else j = res[i], ans++;}

完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1100000 + 5;int n, a[N], L[N], R[N], res[N];
int sk[N], sl = 0;
vector<int> G[N * 2];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void solve (int u) {sl = 0;for (int v : G[u]) {bool solved = false;while (sl && R[sk[sl - 1]] < v) --sl;if (L[v] <= sk[sl - 1]) res[v] = sk[sl - 1];while (sl && R[sk[sl - 1]] <= R[v]) --sl;sk[sl++] = v;}
}int main() {read (n);rep (i, 1, n) read (a[i]);sl = 0;rep (i, 1, n) {while (sl && a[sk[sl - 1]] <= a[i]) --sl;L[i] = sl ? sk[sl - 1] + 1 : 1;sk[sl++] = i;}sl = 0;dwn (i, n, 1) {while (sl && a[sk[sl - 1]] >= a[i]) --sl;R[i] = sl ? sk[sl - 1] - 1 : n;sk[sl++] = i;}rep (i, 1, n) G[a[i] - i + n].push_back (i);rep (i, 0, 2 * n) if (G[i].size() >= 2) solve (i);int ans = 0;for (int i = 1, j = 0; i <= n; ++i) {if (!res[i]) continue;if (j >= res[i]) res[i] = 0;else j = res[i], ans++;}printf ("%d\n", ans);rep (i, 1, n) if (res[i]) printf ("%d %d\n", res[i], i);return 0;
}

神犇代码赏析

下面来赏析一下这位神犇的代码（需要先AC才能看到）：https://www.luogu.com.cn/record/101728049

注释版源码：

#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (2000005)using namespace std;struct data {int x, y;
} ans[N];
struct edge {int nt, to;
} g[N];int head[N], lim1[N], lim2[N], st[N], a[N], p[N], n, num, tot, top, Ans;il int gi() {RG int x = 0, q = 1;RG char ch = getchar();while ( (ch < '0' || ch > '9') && ch != '-') ch = getchar();if (ch == '-') q = -1, ch = getchar();while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();return q * x;
}il void insert (RG int from, RG int to) {g[++num] = (edge) {head[from], to}, head[from] = num;return;
}
// 和我的做法一样
il void solve() {for (RG int i = 1; i <= tot; ++i) {while (top && lim1[st[top]] < p[i]) --top;if (top && lim2[p[i]] <= st[top]) ans[++Ans] = (data) {st[top], p[i]};while (top && lim1[st[top]] <= lim1[p[i]]) --top;st[++top] = p[i];}return;
}il int cmp (const data &a, const data &b) {if (a.x == b.x) return a.y < b.y;return a.x < b.x;
}int main() {
#ifndef ONLINE_JUDGEfreopen ("empodia.in", "r", stdin);freopen ("empodia.out", "w", stdout);
#endifn = gi();for (RG int i = 1; i <= n; ++i) a[i] = gi() + 1;for (RG int i = n; i; --i) insert (n + a[i] - i, i);// lim2对应我的L数组for (RG int i = 1; i <= n; ++i) {while (top && a[st[top]] < a[i]) --top;lim2[i] = st[top] + 1, st[++top] = i;}st[top = 0] = n + 1;// lim1对应我的R数组for (RG int i = n; i; --i) {while (top && a[st[top]] > a[i]) --top;lim1[i] = st[top] - 1, st[++top] = i;}// 链式前向星是倒着的，所以要先遍历一遍链表，反转回来……这种写法远不如我的vector数组的写法for (RG int i = 0, j; i <= (n << 1); ++i) {for (tot = top = 0, j = head[i]; j; j = g[j].nt) p[++tot] = g[j].to;if (tot >= 2) solve();}// 按左端点升序排序sort (ans + 1, ans + Ans + 1, cmp), top = 0;// 和我们的解法不一样，这里存储了所有区间，而不限定一个右端点只能保留一个左端点，所以需要一个单调栈来求出最终答案。for (RG int i = 1; i <= Ans; ++i) {while (top && ans[st[top]].y >= ans[i].y) --top;if (top && ans[st[top]].x == ans[i].x) continue;st[++top] = i;}// 最终保留在栈中的就是答案cout << top << endl;for (RG int i = 1; i <= top; ++i) printf ("%d %d\n", ans[st[i]].x, ans[st[i]].y);return 0;
}

C-Atcoder_abc294_f-二分答案

传送门：https://atcoder.jp/contests/abc294/tasks/abc294_f

二分答案，转为统计问题：统计浓度>= mid的是否>= k个，true则l = mid，false则r = mid。

式子(a[i]+c[j])/(a[i]+b[i]+c[j]+d[j]) >= mid，我们希望把式子中的i和j分开，只有这样，我们才能“定一求二”。把i和j分开后：(1-mid)*a[i] - mid*b[i] >= (mid-1)*c[j] + m*d[j]。左侧在枚举i后即可记为定值val，右侧记为新数组cd[j]，可以预处理出来。于是只需要统计cd数组中小于等于val的个数，使用upper_bound - 1即可。

PS：幸好不卡精度……

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 5e4 + 5;int n, m, a[N], b[N], c[N], d[N];
LL k;
double cd[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}bool jdg (double mid) {rep (i, 1, m) cd[i] = (mid - 1) * c[i] + mid * d[i];sort (cd + 1, cd + m + 1);LL ans = 0;rep (i, 1, n) {double val = (1 - mid) * a[i] - mid * b[i];ans += upper_bound (cd + 1, cd + m + 1, val) - cd - 1;}return ans >= k;
}int main() {read (n, m, k);rep (i, 1, n) {read (a[i], b[i]);}rep (i, 1, m) {read (c[i], d[i]);}double l = 0, r = 1;while (r - l > 1e-11) {double mid = (l + r) / 2;if (jdg (mid) ) l = mid;else r = mid;}printf ("%.10lf\n", l * 100);return 0;
}

D-set或树状数组

两种做法都是基于同一个思想：拆位。即拆成26个01数组，c[j][i] = 1表示s[i] == 'a' + j。

set做法：维护26个set，s[i]维护'a' + i的所有出现下标。主要利用了set的有序性。操作1：set的删除操作。操作2：查询set[i].uppe_bound(l)或--set[i].lower_bound(r)。

树状数组做法：维护26个树状数组，两种操作，在枚举字母后，都转化为单点修改和区间求和。

set做法：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define lowbit(x) ((x) & (-(x)))const int N = 5e5 + 5;int n, q;
char st[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n);scanf ("%s", st + 1);set<int> s[26];re_ (i, 0, 26) s[i].insert (n + 1);rep (i, 1, n) {s[st[i] - 'a'].insert (i);}read (q);while (q--) {int op;read (op);if (op == 1) {int idx;char c[3];scanf ("%d%s", &idx, c);re_ (i, 0, 26) {if (s[i].count (idx) && 'a' + i != c[0]) {s[i].erase (idx);s[c[0] - 'a'].insert (idx);}}}if (op == 2) {int l, r;read (l, r);int ans = 0;re_ (i, 0, 26) {int nxt = *s[i].lower_bound (l);ans += (nxt <= r);}printf ("%d\n", ans);}}return 0;
}

树状数组做法：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define lowbit(x) ((x) & (-(x)))const int N = 5e5 + 5;int n, C[26][N], q;
char s[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void mdy (int C[], int x, int v) {for (; x <= n; x += lowbit (x) ) C[x] += v;
}int qry (int C[], int x) {int ans = 0;for (; x; x -= lowbit (x) ) ans += C[x];return ans;
}int main() {read (n);scanf ("%s", s + 1);rep (i, 1, n) {mdy (C[s[i] - 'a'], i, 1);}read (q);while (q--) {int op;read (op);if (op == 1) {int idx;char c[3];scanf ("%d%s", &idx, c);re_ (i, 0, 26) {int cnt = qry (C[i], idx) - qry (C[i], idx - 1);if (cnt == 1 && 'a' + i != c[0]) {mdy (C[i], idx, -1);mdy (C[c[0] - 'a'], idx, 1);break;}}}if (op == 2) {int l, r;read (l, r);int ans = 0;re_ (i, 0, 26) {int v = qry (C[i], r) - qry (C[i], l - 1);ans += (v > 0);}printf ("%d\n", ans);}}return 0;
}