C2. Adjust The Presentation (Hard Version)

原题

C2. Adjust The Presentation (Hard Version)

思路大概有了, 但是没有写出来, 给一个大佬加了注释后完整理解了, set确实妙, 没有想到能做一个set数组

代码

#include <bits/stdc++.h>
#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int n, m, q, ans, a[N], b[N], id[N], id2[N];//集合数组
set<int> s[N];void print() 
{if (ans) cout << "TIDAK\n";else cout << "YA\n";
}void solve(int TC) 
{
//	读入n,m,q, ans 是 0cin >> n >> m >> q, ans = 0;//	输入成员初始站位, id2 初始化为特别大, s 清空, 记录每一个数出现的位置F(i, 1, n) {cin >> a[i], id[a[i]] = i, id2[i] = inf, s[i].clear();}
//	输入一开始的展示顺序F(i, 1, m) {
//		第 i 个展示的是b[i]cin >> b[i];
//		往s里放b[i]是第 i 个s[b[i]].emplace(i);}//	从 m 到 i, 把展示的科幻片的位置存到 id2 中, 因为是倒序遍历的, 所以存下了第一次出现的位置, 没有出现过的则是 infdF(i, m, 1) id2[b[i]] = i;//	从头到尾遍历, 检测有多少个不合法的
//	a[i]存的是第 i 个成员的科幻片编号, id2 访问到这个科幻片编号第一次出现的位置, 如果当前这个科幻片的位置在下个的后面, 就说明这个的位置不合法F(i, 1, n - 1) if (id2[a[i]] > id2[a[i + 1]]) ans++;print();auto check = [](int pos) {int ret = 0, L = a[pos - 1], R = a[pos + 1], now = a[pos];
//		和左面比一下if (pos < n && id2[now] > id2[R]) ret++;
//		和右面比一下if (pos > 1 && id2[L] > id2[now]) ret++;return ret;};while (q--) {int x, y;cin >> x >> y;//		删掉了 xs[b[x]].erase(x);
//		放进来了 ys[y].emplace(x);for (int i : {b[x], y}) {
//			删掉原来的ans -= check(id[i]);
//			改成现在的if (s[i].empty()) id2[i] = inf;
//			第一个值, set里排好序了else id2[i] = *s[i].begin();
//			加上现在的ans += check(id[i]);}b[x] = y;print();}
}
signed main() 
{ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;for (int i = 1; i <= T; i ++) {solve(i);}return 0;
}