ABC F 求调
  • 板块学术版
  • 楼主lottle1212__
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/18 22:15
  • 上次更新2024/5/19 09:50:10
查看原帖
ABC F 求调
1062683
lottle1212__楼主2024/5/18 22:15

赛后对拍了也拍不出问题 QwQ

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, g[N], d[N], p[N], s[N];
struct node { int h, id; bool operator < (const node &k) const { return h > k.h; } } f[N];
int rd() {
	int res = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	return f ? -res : res;
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
	int T = rd();
	while (T --) {
		n = rd();
		for (int i = 1; i <= n; ++ i) f[i].h = rd(), f[i].id = i, g[i] = d[i] = p[i] = s[i] = 0;
		int tot = 0, cnt = 0;
		for (int i = 1; i <= n; ++ i) {
			int l = 0, r = tot + 1;
			while (l + 1 < r) {
				int mid = l + r >> 1;
				if (g[mid] < f[i].h) l = mid;
				else r = mid;
			}
			if (l == tot) ++ tot;
			g[l + 1] = f[i].h, d[i] = l + 1;
		}
		sort(f + 1, f + n + 1);
		for (int i = 1; i <= n; ++ i)
			if (d[f[i].id] == tot || f[i].id < p[d[f[i].id] + 1])
				s[f[i].id] = true, ++ cnt, p[d[f[i].id]] = max(p[d[f[i].id]], f[i].id);
		cout << cnt << '\n';
		for (int i = 1; i <= n; ++ i)
			if (s[i])
				cout << i << ' ';
		cout << '\n';
	}
	return 0;
}
2024/5/18 22:15
加载中...