P11208 『STA - R8』轮回疯狂

只执行操作一就是逆序对的个数，统计对于每一个 \(a_i\) 的逆序对个数为 \(b_i\)，然后模拟执行删除操作，如果删除操作比换位操作更优就更新答案。

复杂度 \(O(n \log n)\)

record

将最小的删除可以等价成往里加最大的数，倒着模拟即可。至于操作一，每次往数组 \(b\) 里加完后排序。因为一定可以通过直接删除 \(n-1\) 次使其有序，所以只要操作次数达到 \(n-1\) 直接 break

复杂度 \(O(n)\)

record

P11212 『STA - R8』挑战 Goldbach 猜想

这里提供两种非官解做法。

对于正整数 \(n\)，不超过 \(n\) 的素数个数大约有 \(\frac{n}{\ln n}\) 个。预处理筛素数随便写个筛就行，对于复杂度影响不大。考虑对于小于 \(n\) 枚举每一个素数。那么复杂度就是 \(O(\frac{n^2}{\ln n})\)。我们可以很轻松的将暴力打出来。但是交上去显然过不了。

考虑复杂度瓶颈，我们先忽略代码正确性，将取模运算随便换成别的运算交上去（或者本地测），运行时间甚至没有超过 \(2s\)。所以瓶颈在于取模运算。

将 \(n\) 个答案预处理出来，我们可以预处理出所有的答案记为 \(f_i\)，每询问一次 \(n\) 输出 \(f_n\) 即可。至于预处理时的优化取模，我们可以定义一个变量代表余数，跟随你的枚举而改变，当大小等于模数时重新变为 \(0\) 即可。可以通过。

code

如果不预处理在线计算的做，记忆化一下。开个数组记录已经出现过的答案。然后如果询问的值之前出现过直接输出，否则现场计算。在进行取模的时候，使用巴雷特快速取模算法进行优化。取模慢是因为做除法慢，算法原理大概就是将除法变成其运算加速。具体地，将除以任意数转化成乘一个数、除以一个 \(2^k\)。可能是细节处理的不太好，这个做法最慢的点跑了 \(3s\)。但也足以通过。

code

当然，出题人还友善的提醒了我们代码长度限制。显然是怕我们打表。不难发现，对于大部分答案，大概都是个三位数。计算一下发现对于超出洛谷代码限制我们可以打大概 \(13000\) 个数字。打个表存起来，对于大于 \(13000\) 的再在线暴力计算。代码太长就不放了。

P11209 『STA - R8』小熊游景点 II

太久没写 01-Trie 了人家说这个题正解是 01-Trie 甚至一时没反应过来。

01-Trie 板子题，\(a[i]\) 和 \(b[i]\) 一起存储即可。实现方式很多，让你的 01-Trie 长得奇怪一点多维护一些信息或开个 pair 啥的都是 OK 的。然后每次 query(k) 就是答案。

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 5e5 + 5;
const int M = 3e7 + 5;

int T, n, m;
int a[N], b[N];
int ch[M][2], cnt[M], tot;

void insert(int x, int k) 
{
	int p = 0;
	for (rint i = 30; i >= 0; i--) 
	{
		int t = x >> i & 1;
		if (k >> i & 1) 
		{
			if (!ch[p][t])  ch[p][t] = ++tot;
			if (!ch[p][!t]) ch[p][!t] = ++tot;
			cnt[ch[p][t]]++;
			p = ch[p][!t];
		} 
		else 
		{
			if (!ch[p][t]) ch[p][t] = ++tot;
			p = ch[p][t];
		}
	}
	cnt[p]++;
}

int query(int x) 
{
	int p = 0, res = 0;
	for (rint i = 30; i >= 0; i--)
	{
		int t = x >> i & 1;
		if (ch[p][t]) 
		{
			p = ch[p][t];
			res += cnt[p];
		} 
		else 
		{
			return res;
		}
	}
	return res;
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	cin >> T >> n >> m;
	for (rint i = 1; i <= n; i++) cin >> a[i];
	for (rint i = 1; i <= n; i++) cin >> b[i];
	for (rint i = 1; i <= n; i++) insert(a[i], b[i]);
	int last = 0;
	for (rint i = 1; i <= m; i++) 
	{
		int k;
		cin >> k;
		k ^= T * last;
		int ans = query(k);
		cout << ans << endl;
		last = ans;
	}
	return 0;
}

P11187 配对序列

令 \(f_{i,0/1}\) 表示以 \(a_i\) 结尾的偶/奇项的最长配对子序列长，目标 \(f_{i,0}\) 最大值。

转移方程显然：

复杂度 \(O(n^2)\)

考虑优化，这是一个非常典的线段树优化 dp 的转移方程。优化后复杂度 \(O(n \log n)\)

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 5e5 + 5;
const int inf = 5e5 + 5;

int n;
int a[N], f[N][2];
int g[N], ans;

struct Node 
{
	int v;
} t[N * 4];

#define ls p << 1
#define rs p << 1 | 1

void push_up(int p)
{
	t[p].v = max(t[ls].v, t[rs].v);
}

void change(int p, int l, int r, int x, int d) 
{
	if (l == r) 
	{
		t[p].v = d;
		return ;
	} 
	int mid = (l + r) >> 1;
	if (x <= mid) change(ls, l, mid, x, d);
	else change(rs, mid + 1, r, x, d);
	push_up(p);
}

int query(int p, int l, int r, int x, int y) 
{
	if (x <= l && r <= y) return t[p].v;
	int mid = (l + r) >> 1;
	int res = -inf;
	if (x <= mid) res = max(res, query(ls, l, mid, x, y));
	if (y > mid)  res = max(res, query(rs, mid + 1, r, x, y));
	return res;
}

signed main() 
{
	cin >> n;
	memset(g, -1, sizeof g);
	for (rint i = 1; i <= n; i++) 
	{
		cin >> a[i];
		f[i][1] = 1;
		if (a[i] != 1)   f[i][1] = max(f[i][1], query(1, 1, inf, 1, a[i] - 1) + 1);
		if (a[i] != inf) f[i][1] = max(f[i][1], query(1, 1, inf, a[i] + 1, inf) + 1);
		f[i][0] = g[a[i]] + 1;
		g[a[i]] = max(g[a[i]], f[i][1]);
		if (query(1, 1, inf, a[i], a[i]) < f[i][0]) change(1, 1, inf, a[i], f[i][0]);
		ans = max(ans, f[i][0]);
	}
	cout << ans << endl; 
	return 0;
}