8.22小测总结 - 洛谷保存站

## 前言
今天是 tht 的生日，据说膜拜他可以 AK IOI。我试了，虽然没有 AK IOI，并且 tht 的生日也不在今天，但我 AC 了 kkkw 比赛的 T1-T3。所以大家快来膜拜 tht。

## T1 最小中位数
[AT_abc203_d](https://atcoder.jp/contests/abc203/tasks/abc203_d)

手玩几组样例容易发现，一个 $k \times k$ 矩阵的中位数 $\le x$ ，当且仅当矩阵中大于 $x$ 的元素个数 $\le \lfloor \frac{k^2}{k} \rfloor$。

那么可以用前缀和快速计算 $>x$ 的个数，如果存在一个子矩阵中 $1$ 的个数 $\le \lfloor \frac{k^2}{k} \rfloor$，那么这个答案就是可行的，$x$ 可以更小。

我们可以用二分答案枚举答案，然后 check 以上的条件即可。

时间复杂度为 $O(n^2 \log (\max A))$。

```cpp line-numbers
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,minn=INT_MAX,maxl=0,a[805][805],s[805][805];
bool check(int x) {
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			s[i][j]=(a[i][j]>x ? 1 : 0)+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	int t=k*k/2;
	for (int i=k;i<=n;i++)
		for (int j=k;j<=n;j++) {
			int cnt=s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k];
			if (cnt<=t) return true;
		}
	return false;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			cin>>a[i][j],minn=min(minn,a[i][j]),maxl=max(maxl,a[i][j]);
	int l=minn,r=maxl,ans=maxl;
	while (l<=r) {
		int mid=(l+r)/2;
		if (check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}
```

## T2 沿线充电与最少天数
[AT_arc060_c](https://atcoder.jp/contests/arc060/tasks/arc060_c)

倍增 + 贪心。

考虑预处理出每个充电站“一天内最远能到达”的站点，然后用倍增法快速跳转。

贪心策略：从起点出发，每次选择在一天内能到达的最远站点，这样天数最少。

暴力模拟每次跳跃，最坏 $O(n)$ 天，$O(n)$ 每次查询，会 TLE。

预处理 $b_{0,i}$，从第 $i$ 个站点出发，一天内最远能到达的站点编号。

$b_{j,i}$ 表示从 $i$ 出发，经过 $2^j$ 天后最远能到达的站点。

$b_{j,i} \gets b_{j-1,b_{j-1,i}}$，即先跳 $2^{j-1}$ 天到 $b_{j-1,i}$，再从那里跳 $2^{j-1}$ 天。

对于查询 $(x,y)$，假设 $x<y$，从 $x$ 出发，从高到低枚举 $2^j$，如果 $b_{j,cur}<y$，则跳 $2^j$ 步，累加天数。最后如果还没到 $y$，再跳一天。

时间复杂度：预处理 $O(nlogn)$，每次查询 $O(logn)$。

```cpp line-numbers
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,q,p=1,a[100005],b[20][100005]; // a: 坐标, b: 倍增数组
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	cin>>l;
	// 预处理 b[0][i]: 从i出发一天内最远能到的站点
	for (int i=1;i<=n;i++) {
		while (p<n && a[p+1]-a[i]<=l) // p是双指针，维护最远可达位置
			p++;
		b[0][i]=p;
	}
	// 倍增预处理
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++)
			b[j][i]=b[j-1][b[j-1][i]]; // 从i跳2^j天 = 从i跳2^(j-1)天，再从新位置跳2^(j-1)天
	cin>>q;
	while (q--) {
		int x,y;
		cin>>x>>y;
		if (x>y) swap(x,y); // 保证x是起点，y是终点
		int ans=0,cur=x; // ans: 天数, cur: 当前位置
		// 倍增跳跃
		for (int j=19;j>=0;j--)
			if (b[j][cur]<y) // 如果跳2^j天还不到y
				cur=b[j][cur],ans+=(1<<j); // 就跳
		if (cur<y) ans++; // 最后如果还没到，再跳一天
		cout<<ans<<'\n';
	}
	return 0;
}
```

## T3 树与查询
[P12698](https://www.luogu.com.cn/problem/P12698)

正在渲染内容...