LOJ6062「2017 山东一轮集训 Day2」Pair [Hall定理/线段树]

Author Avatar
ajcxsu 2018年09月18日
  • 100 次阅读

最近机房都交不上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://acxblog.site/archives/sol-loj-6062.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。