CF338E Optimize! （题解）
Leap_Frog
·
·
题解
P.S.
upd on 11.4，修改了一处 typo，然后对所有被我误导的人致歉
愿每场 div1.E 都能像这题一样 /wq
虽然很 sb，但是还是吃了两发罚时 /dk
第一发 a b 搞反，第二发数组开小。。。
所以 小跳蛙无药可救 /ruo /no
不吧，这题需要什么 Hall 定理吗？？（
Description.
翻译还算比较清楚。
不过注意匹配不需要按顺序，可以打乱顺序匹配。
Solution.
那么我们把每个 $b_j\rightarrow H-b_j$。
那么原题转化为了 $a_i\ge b_j$ 时它们匹配。
所以显然有一个贪心就是对 $\{b_i\}$ 和 $\{a_i\}$ 排序，
每次找出最小的元素，如果能匹配就匹配掉，否则就无解。
每次这样暴力匹配是 $O(len)$ 的，所以总复杂度 $O(len\times(n-len))$ 显然不能通过此题。
我们考虑在值域上搞事情，首先离散化。
然后我们在 $b_i$ 处 $+1$ 表示这边多了一个可以被匹配的数。
然后在 $a_i$ 处 $-1$ 表示这边消耗掉一个被匹配数。
那么每次能完全匹配的充要条件就是这个值域上有下式成立。
$$\forall x\in[1,n]\ ,\sum_{i=1}^xw_i\ge0$$
那么我们直接用线段树维护单点前缀和，区间前缀和的最小值。
然后查询全局最小值是否 $\ge0$ 即可。
然后这题就做完了，无耻求赞。
### Coding.
代码没什么好解释的了（（（
```cpp
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename t>inline void read(t &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}
struct node{int mn,fg;}T[1200005];
int n,m,H,a[150005],b[150005],tn[300005],ut;
inline void allc(int x,int w) {T[x].mn+=w,T[x].fg+=w;}
inline void pushdw(int x) {if(T[x].fg) allc(x<<1,T[x].fg),allc(x<<1|1,T[x].fg),T[x].fg=0;}
inline void pushup(int x) {T[x].mn=min(T[x<<1].mn,T[x<<1|1].mn);}
inline void modif(int x,int l,int r,int dl,int dr,int dw)
{//维护的前缀和，所以单点加变成了区间加
if(l>dr||dl>r) return;else if(dl<=l&&r<=dr) return allc(x,dw);else pushdw(x);
modif(x<<1,l,(l+r)>>1,dl,dr,dw),modif(x<<1|1,((l+r)>>1)+1,r,dl,dr,dw),pushup(x);
}
int main()
{
read(n),read(m),read(H);int cnt=0;
for(int i=1;i<=m;i++) read(b[i]),b[i]=H-b[i],tn[++ut]=b[i];
for(int i=1;i<=n;i++) read(a[i]),tn[++ut]=a[i];
sort(tn+1,tn+ut+1),ut=unique(tn+1,tn+ut+1)-tn-1;
for(int i=1;i<=m;i++) b[i]=lower_bound(tn+1,tn+ut+1,b[i])-tn;
for(int i=1;i<=n;i++) a[i]=lower_bound(tn+1,tn+ut+1,a[i])-tn;
for(int i=1;i<=m;i++) modif(1,1,ut,a[i],ut,-1),modif(1,1,ut,b[i],ut,1);
cnt+=T[1].mn>=0;for(int i=m+1;i<=n;i++) modif(1,1,ut,a[i-m],ut,1),modif(1,1,ut,a[i],ut,-1),cnt+=T[1].mn>=0;
return printf("%d\n",cnt),0;
}
```