2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛66
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛66 [2020/06/27 17:44] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛66 [2020/08/01 10:15] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:牛客练习赛66被移动至2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛66 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| 给定一个长度为 $n$ 的全排列，问存在多少个闭区间满足区间左端点恰为次小值，区间右端点恰为次大值。 | 给定一个长度为 $n$ 的全排列，问存在多少个闭区间满足区间左端点恰为次小值，区间右端点恰为次大值。 | ||
| - | ==== 题解 ==== | + | ==== 题解 $1$ ==== |
| 用权值线段树维护每个结点作为区间右端点且恰为次大值的左端点选区范围和每个结点作为区间左端点且恰为次小值的右端点选区范围。 | 用权值线段树维护每个结点作为区间右端点且恰为次大值的左端点选区范围和每个结点作为区间左端点且恰为次小值的右端点选区范围。 | ||
| 行 17: | 行 17: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <iostream> | ||
| - | #include <vector> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <cmath> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| const int MAXN=1e6+5; | const int MAXN=1e6+5; | ||
| struct Tree{ | struct Tree{ | ||
| 行 146: | 行 129: | ||
| </hidden> | </hidden> | ||
| - | 另外，好像也可以用 $\text{set}$ 维护端点的合法范围，这里 $\text{copy}$ 了一份别人的代码。 | + | ==== 题解 $2$ ==== |
| + | |||
| + | 可以用 $\text{set}$ 维护端点的合法范围，按权值大小将每个数的下标插入 $\text{set}$，这里 $\text{copy}$ 了一份别人的代码。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛66.1593251054.txt.gz · 最后更改: 2020/06/27 17:44 由 jxm2001
