最近机房都交不上 LOJ 的题.. 很奇怪

Problem

https://loj.ac/problem/6062

Solution

考虑确定 $a$ 的一个区间，能匹配的元素连边。

考虑 $b$ 排序后，对于 $b_i>b_j$，一定有 $b_j$ 能连的 $a$ 是 $b_i$ 的子集。

那么显然若对于从小到大排序后每个 $b_i$ 向 $a$ 连的个数有 $\geq i$，则一定存在 $b$ 到 $a$ 的完备匹配。否则一定不存在。

线段树移动区间套二分维护即可。

Code

// Code by ajcxsu
// Problem: pair

#include<bits/stdc++.h>
using namespace std;

template<typename T> void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

#define ls x<<1
#define rs x<<1|1
const int N=1.5e5+10;
int a[N], b[N], mi[N*6], lazy[N*6], g[N];
void pud(int x) {
    if(!lazy[x]) return;
    lazy[ls]+=lazy[x], lazy[rs]+=lazy[x], mi[ls]+=lazy[x], mi[rs]+=lazy[x];
    lazy[x]=0;
}
void updata(int x, int l, int r, int xl, int xr, int w) {
    pud(x);
    if(xl<=l && r<=xr) { lazy[x]+=w; mi[x]+=w; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, w);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, w);
    mi[x]=min(mi[ls], mi[rs]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, h;
    gn(n), gn(m), gn(h);
    for(int i=1;i<=m;i++) gn(b[i]), updata(1, 1, m, i, i, -i);
    sort(b+1, b+1+m);
    for(int i=1;i<=n;i++) gn(a[i]);
    int ans=0;
    for(int i=1;i<=m;i++) {
        g[i]=lower_bound(b+1, b+1+m, h-a[i])-b;
        if(g[i]<=m) updata(1, 1, m, g[i], m, 1);
    }
    ans+=(mi[1]>=0);
    for(int i=m+1;i<=n;i++) {
        if(g[i-m]<=m) updata(1, 1, m, g[i-m], m, -1);
        g[i]=lower_bound(b+1, b+1+m, h-a[i])-b;
        if(g[i]<=m) updata(1, 1, m, g[i], m, 1);
        ans+=(mi[1]>=0);
    }
    printf("%d\n", ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-loj-6062.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆