题解

记当前查询的子数组为 $C_i$。

首先考虑 $O(nm\log m)$ 怎么做。

我们将 $B_i$ 从大到小排个序，然后对于 $C_i$ 从小到大排个序。这样最小的会和最大的匹配，第二小的会和第二大的匹配，……，显然是最优的。

现在思考如何优化。

注意到 $B_i$ 排完序后满足单调性，也就是 $C_i$ 如果能匹配前面的，那么后面的也能匹配到；而 $C_i$ 如果不能匹配后面的，则前面的也匹配不了。

我们可以记录每个 $B_i$ 能与多少个 $C_i$ 匹配。记匹配次数为 $P_i$。

显然如果满足对于所有 $i$，$P_i\ge i$，就一定可以匹配，否则一定不可以匹配。

证明：

如果存在至少一个 $P_i\lt i$。

显然，对于所有 $1\le j\le i$，$P_j\le P_i\lt i$。

如果我们找一个数 $A_j$ 匹配 $P_i$，则等价于将 $B_i$ 与 $A_j$ 删除。此时前面的 $B_{i-1}$ 有几种情况：

• 若 $P_{i-1}\lt P_i$，则 $P_{i-1}\le P_i-1\lt i-1$，问题依然存在；
• 若 $P_{i-1}=P_i$，则 $A_j$ 一定匹配 $B_{i-1}$，删除 $A_j$ 后 $P_{i-1}$ 的值 $-1$，此时 $P_{i-1}$ 小于原来的 $P_i$，回到上面的那个情况，问题依然存在。

依此类推，则可以证明存在 $P_i\lt i$ 时绝对不可以匹配。

而对于所有 $P_i\ge i$ 时，我们可以构造出一种方案：

首先将 $C_i$ 从小到大排序。此时 $C$ 也满足单调性，$B_i$ 可以和后面的匹配就一定可以和前面的匹配。显然此时 $B_1$ 能与 $C_1$ 匹配，$B_2$ 能与 $C_2$ 匹配，……，问题解决。

证毕。

我们可以使用线段树实现判断这一过程，我们可以先将初始的 $P_i$ 设为 $-i$，每次修改只需要找到第一个能匹配的 $B_i$，将 $P_i,P_{i+1},...,P_n$ 的值 $+1$，删除反向操作即可，然后判断 $\min P\ge 0$ 即可。

#include <bits/stdc++.h>
namespace cjdst{

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = std::min(tr[u << 1], tr[u << 1 | 1]);
		}
		void push_down(int u){
			tr[u << 1] += lazytag[u];
			tr[u << 1 | 1] += lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = -l;
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = 0x3f3f3f3f;
			if(right[u << 1] >= l) ans = std::min(ans, _query(u << 1, l, r));
			if(left[u << 1 | 1] <= r) ans = std::min(ans, _query(u << 1 | 1, l, r));
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};
	
	
	void solve(){
		int n, m, k;
		std::cin >> n >> m >> k;
		std::vector <int> a(n + 5, 0), b(m + 5, 0);
		for(int i = 1; i <= m; i++){
			std::cin >> b[i];
		}
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		std::sort(b.begin() + 1, b.begin() + m + 1);
		Segtree <int> tr(m);
		int ans = 0;
		for(int i = 1; i <= n; i++){
			int idx = std::lower_bound(b.begin() + 1, b.begin() + m + 1, k - a[i]) - b.begin();
			if(idx <= m){
				tr.modify(idx, m, 1);
			}
			if(i >= m){
				if(i > m){
					idx = std::lower_bound(b.begin() + 1, b.begin() + m + 1, k - a[i - m]) - b.begin();
					if(idx <= m){
						tr.modify(idx, m, -1);
					}
				}
				if(tr.query(1, m) >= 0) ans++;
			}
		}
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(n\log m)$。

---

冷知识，我一开始看的时候读错题了，我以为不可以任意重排。

如果题面是这样的话，能不能做呢？显然是可以的。

我常常追忆过去。

和这个的思路一样，先将 $B_i$ 排序，然后将 $A_i$ 排序，并记录它们原来的下标。

此时开个生命瞬间定格在脑海我将背后的时间裁剪折叠蜷曲揉捻成天上朵朵白云云朵之间亦有分别积云厚重而卷云飘渺生命里震撼的场景掠过我的思绪便一生无法忘怀，记录的是当前 $B_i$ 可以匹配哪些 $A_i$。显然因为 $B_i$ 是单调的，所以可以 $O(n)$ 修改。

接着用一个而更为普通平常的记忆在时间的冲刷下只留下些许残骸追忆宛如入梦太过清楚则无法愉悦自己的幻想过分模糊却又坠入虚无只有薄雾间的山水面纱下的女子那恰到好处的朦胧才能满足我对美的苛求追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友推倒又重建的街道种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上，记录以 $i$ 为起点是否可以匹配，这个很简单，将上面的曾经的日子无法重来我只不过是一个过客但我仍然渴望在每一次追忆之旅中留下闲暇时间在一个场景前驻足在岁月的朦胧里瞭望过去的自己感受尽可能多的甜蜜美好的时光曾流过我的身体我便心满意足过去已经凝固我带着回忆向前只是时常疏于保管回忆也在改变着各自的形态这给我的追忆旅程带来些许挑战右移所在的位置位，然后按位与即可。

时间复杂度 $O(\frac{nm}{我该在哪里停留？我问我自己})$。