题解：P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2

· · 题解

将 (A_i,B_i) 看为左部点，(C_i,D_i) 看为右部点，两个不同部分的点 (A_i,B_i),(C_j,D_j) 之间有一条边权为 [A_i=C_j] 的边，当且仅当 B_i\le D_j。那么本题就是求最大权二分图匹配。

直接做肯定不行，但是注意到边权只有 0 或 1，所以考虑贪心。

设从前往后扫左部点扫到了 (A_i,B_i)，我们贪心地找与 (A_i,B_i) 有边相连，边权为 1 且 D_j 最大的右部点 (C_j,D_j)。如果连上这条边后，这个二分图还存在完美匹配，那么就选择这条边。

不难发现，对于一个左部点 (A_i,B_i)，所有满足 j<i 的左部点 (A_j,B_j) 的边集是包含于 (A_i,B_i) 的，所以容易反证出以上的贪心是对的。

接着考虑判完美匹配，直接拿个线段树跑个 Hall 定理即可。

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

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int Maxn=2e5+5;
int n;
struct node{
    int c,p;
}a[Maxn],b[Maxn];
int c[Maxn];
struct Tree{
    int val,tag;
}t[Maxn<<2];
void build(int x,int l,int r){
    if(l==r)return void(t[x]={c[l]-l,0});
    int mid=l+r>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    t[x].val=min(t[x<<1].val,t[x<<1|1].val);
}
inline void add_(int x,int p){
    t[x].tag+=p;t[x].val+=p;
}
inline void spread(int x){
    add_(x<<1,t[x].tag);add_(x<<1|1,t[x].tag);
    t[x].tag=0;
}
void change(int x,int l,int r,int L,int R,int p){
    if(L>R)return;
    if(L<=l&&r<=R)return void(add_(x,p));
    int mid=l+r>>1;spread(x);
    if(mid>=L)change(x<<1,l,mid,L,R,p);
    if(mid<R)change(x<<1|1,mid+1,r,L,R,p);
    t[x].val=min(t[x<<1].val,t[x<<1|1].val);
}
int query(int x,int l,int r,int L,int R){
    if(L>R)return 114;
    if(L<=l&&r<=R)return t[x].val;
    int mid=l+r>>1,res=114;spread(x);
    if(mid>=L)res=query(x<<1,l,mid,L,R);
    if(res<1)return res;
    if(mid<R)return query(x<<1|1,mid+1,r,L,R);
    return 114;
}
set<int>s[Maxn];
int whe[Maxn];
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]={read(),read()};
    for(int i=1;i<=n;i++)b[i]={read(),read()};
    int p=1;
    for(int i=1;i<=n;i++){
        while(p<=n&&b[p].p>=a[i].p)whe[p]=i,p++;
        c[i]=p-1;
    }
    build(1,1,n);
    p=1;int ans=n;
    for(int i=1;i<=n;i++){
        while(p<=n&&b[p].p>=a[i].p)s[b[p].c].insert(p),p++;
        if(s[a[i].c].empty())continue;
        int id=(*s[a[i].c].rbegin());
        if(query(1,1,n,whe[id],i-1)>0){
            ans--;change(1,1,n,whe[id],i-1,-1);
            change(1,1,n,i,i,1000000000);
            s[a[i].c].erase(id);
        }
    }printf("%d\n",ans);
    return 0;
}