B. 双调序列
题目描述
我们定义一个序列 \(X\) 是双调的当且仅当：
- \(\exist 1\le i\le N,满足 X_1<X_2<\dots<X_i>\dots>X_N\)。
求序列 \(A\) 有多少个子串是双调的。
思路
可以发现，一个序列 \(X\) 是双调的当且仅当 \(X_1\ne X_2\ne \dots\ne X_N\and[X_1>X_2]\le[X_2>X_3]\le \dots\le [X_{N-1}>X_{N}]\)。
使用双指针求解即可。
时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300001;
int n, a[MAXN];
ll ans;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 1, j = 1; i <= n; ++i) {
for(; j <= n && (j == i || a[j] != a[j - 1]) && (j <= i + 1 || (a[j - 1] > a[j]) >= (a[j - 2] > a[j - 1])); ++j) {
}
ans += j - i;
}
cout << ans;
return 0;
}
D. Adjust The Presentation (Easy Version)
题目描述
这是问题的简单版本。在两个版本中只有 \(q\) 的数据范围不同。在这个版本中 \(q=0\)。
有 \(N\) 个人按照 \(A_1,A_2,\dots,A_N\) 的顺序排成一排。
有 \(M\) 张幻灯片，每次你会让排头的人展示当前幻灯片，并切换到下一个幻灯片，接着把这个人插入到队列的任意位置。
给定序列 \(B_1,B_2,\dots,B_M\)，你要判断是否有一种方法使得幻灯片 \(i\) 被第 \(B_i\) 个人展示。
有 \(q\) 次操作，每次操作会修改 \(B_s\leftarrow t\)，并让你判断是否可行。
思路
这里显然有以下几种情况不合法：
- 第 \(A_i\) 个人没有播放过幻灯片，但 \(A_{i+1}\) 播放了。
- 第 \(A_i\) 个人第一次展示幻灯片的时间比 \(A_{i+1}\) 晚。
时空复杂度均为 \(O(N+M)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int t, n, m, q, a[MAXN], b[MAXN], pos[MAXN];
void Solve() {
cin >> n >> m >> q;
for(int i = 1, x; i <= n; ++i) {
cin >> x;
a[x] = i;
pos[i] = MAXN;
}
for(int i = 1, x; i <= m; ++i) {
cin >> b[i];
b[i] = a[b[i]];
if(!pos[b[i]]) {
pos[b[i]] = i;
}
}
S.clear();
for(int i = 1; i < n; ++i) {
if(pos[i] > pos[i + 1]) {
cout << "TIDAK\n";
return;
}
}
cout << "YA\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}
E. Adjust The Presentation (Hard Version)
题目描述
这是问题的简单版本。在两个版本中只有 \(q\) 的数据范围不同。在这个版本中 \(q\le2\cdot 10^5\)。
题目同上。
思路
通过上一题的思路，我们可以用 set \(s_i\) 记录下每个人 \(i\) 播放了哪些幻灯片，再用一个 set \(S\) 记录下不合法的 \(i\)。如果序列合法，则 \(S=\varnothing\)。
每次进行修改时，我们都把对应的 set 进行插入/删除，此时有两个 set 改变了，对对应的 \(x\) 再判断合法即可。
空间复杂度 \(O(N+M)\)，时间复杂度 \(O(N+M\log M+Q\log M)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int t, n, m, q, a[MAXN], b[MAXN];
set<int> s[MAXN], S;
void Solve() {
cin >> n >> m >> q;
for(int i = 1, x; i <= n; ++i) {
cin >> x;
a[x] = i;
s[i].clear();
}
for(int i = 1, x; i <= m; ++i) {
cin >> b[i];
b[i] = a[b[i]];
s[b[i]].insert(i);
}
S.clear();
for(int i = 1; i < n; ++i) {
if((s[i].empty() && !s[i + 1].empty()) || (!s[i].empty() && !s[i + 1].empty() && *s[i].begin() > *s[i + 1].begin())) {
S.insert(i);
}
}
cout << (S.empty() ? "YA\n" : "TIDAK\n");
for(int i = 1, p, x; i <= q; ++i) {
cin >> p >> x;
x = a[x];
int y = b[p];
s[b[p]].erase(p);
b[p] = x;
s[b[p]].insert(p);
if(x > 1) {
if(S.count(x - 1) && !((s[x - 1].empty() && !s[x].empty()) || (!s[x - 1].empty() && !s[x].empty() && *s[x - 1].begin() > *s[x].begin()))) {
S.erase(x - 1);
}
if(!S.count(x - 1) && ((s[x - 1].empty() && !s[x].empty()) || (!s[x - 1].empty() && !s[x].empty() && *s[x - 1].begin() > *s[x].begin()))) {
S.insert(x - 1);
}
}
if(x < n) {
if(S.count(x) && !((s[x].empty() && !s[x + 1].empty()) || (!s[x].empty() && !s[x + 1].empty() && *s[x].begin() > *s[x + 1].begin()))) {
S.erase(x);
}
if(!S.count(x) && ((s[x].empty() && !s[x + 1].empty()) || (!s[x].empty() && !s[x + 1].empty() && *s[x].begin() > *s[x + 1].begin()))) {
S.insert(x);
}
}
if(y > 1) {
if(S.count(y - 1) && !((s[y - 1].empty() && !s[y].empty()) || (!s[y - 1].empty() && !s[y].empty() && *s[y - 1].begin() > *s[y].begin()))) {
S.erase(y - 1);
}
if(!S.count(y - 1) && ((s[y - 1].empty() && !s[y].empty()) || (!s[y - 1].empty() && !s[y].empty() && *s[y - 1].begin() > *s[y].begin()))) {
S.insert(y - 1);
}
}
if(y < n) {
if(S.count(y) && !((s[y].empty() && !s[y + 1].empty()) || (!s[y].empty() && !s[y + 1].empty() && *s[y].begin() > *s[y + 1].begin()))) {
S.erase(y);
}
if(!S.count(y) && ((s[y].empty() && !s[y + 1].empty()) || (!s[y].empty() && !s[y + 1].empty() && *s[y].begin() > *s[y + 1].begin()))) {
S.insert(y);
}
}
cout << (S.empty() ? "YA\n" : "TIDAK\n");
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}