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

Little_Cancel_Sunny · 2025-11-10 17:57:17 · 题解

P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2(Hall定理+线段树+贪心)

暴力

较为明显的是这是一个带权二分图匹配问题，可以用网络流的思想刻画一下，即对于 B_i\le D_j 存在一条边，边权为 A_i\ne C_j 最后连一个源汇就可以跑费用流了。

显然无法通过，我们需要更优秀的解法。

正解

我们可以证明，对于相同的一种颜色的 D_j 如果存在一个最大的 B_i 使得 B_i\le D_j 那么这种匹配一定不劣于其他匹配。

然而直接这样匹配显然是错的，因为你最后可能匹配不完，所以我们要考虑验证这个东西是否可以匹配，所以不难想到 Hall 定理。

但是枚举子集的复杂度我们也无法接受，考虑这个二分图是否存在某种性质，容易发现是存在的我们发现根据它所给出的从大到小的分数，对于一个分数它可以匹配的一定是一个前缀，所以对于一个前缀的匹配我们只需要判断它对应的位置是否全部能匹配上就可以了，因为它如果删除前面的数，匹配不变，加一个数匹配只可能使匹配变大，所以我们只需要判断 n 个前缀是否匹配上就好了。

具体做法就是维护这个式子 N(S)-S \ge 0，我们只需要一个区间加和区间最值的线段树即可。

然后就是说，具体来讲，做法是对 1\to pos_i 进行 +1 操作，对 1\to i 进行减 1 操作。

前者是好理解的，我们可以认为是 1\to pos_i 又多了一个匹配点。

如何理解后者，我们可以说明它们的最坏匹配如下：

即如果这个图连这种匹配都没有那么它一定是不合法的，所以我们认为后者就是把这种匹配抠出来，这样不会对后面造成影响，如果小于 0 那么说明前面有一个前缀不存在完备匹配，那么就不合法。

然后发现还是错的，因为如果每个都不能选，那么我们就会不断试错，复杂度就会变成 O(n^2 \log n)。

我们还要考虑枚举的顺序，我们需要考虑从小到大枚举被匹配的点，因为我们先枚举的点都不能与之前的点匹配，那么该点也一定不能那些点匹配，感性一点来讲就是，我们现在枚举的点一定比之前的点可以匹配上的点多，如果之前需要服务更少的点都不行，那么你现在要服务更多的点，也就更不可能了。

正常一点来讲，就是说我们之前枚举到的无法和我们之前的点匹配的点，它们的匹配点一定在更前面，否则仍旧无法匹配。

所以我们维护一个栈就可以做完了。

code

#include<bits/stdc++.h>
//吹き込んだそよ風が
//窓辺の花を揺らして
//仰ぐ今日の空は
//あの時描いた青だった
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define lson k<<1
#define rson k<<1|1
//写完写笔记

const int N=2e5+15;

struct node
{
    int bel;
    int p;
}x[N],y[N];
int p[N];
int n,ans=0;
struct segment_tree
{
    int minn;
    int lazy;
}t[N<<2];
stack<int> st[N];

bool cmp(node a,node b)
{
    return a.p>b.p;
}

void push_up(int k)
{
    t[k].minn=min(t[lson].minn,t[rson].minn);
}

void push_down(int k)
{
    if(!t[k].lazy) return;
    t[lson].lazy+=t[k].lazy;
    t[rson].lazy+=t[k].lazy;
    t[lson].minn+=t[k].lazy;
    t[rson].minn+=t[k].lazy;
    t[k].lazy=0;
}

void update(int k,int l,int r,int ln,int rn,int x)
{
    if(ln<=l&&r<=rn)
    {
        t[k].lazy+=x;
        t[k].minn+=x;
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(rn<=mid) update(lson,l,mid,ln,rn,x);
    else if(ln>mid) update(rson,mid+1,r,ln,rn,x);
    else update(lson,l,mid,ln,rn,x),update(rson,mid+1,r,ln,rn,x);
    push_up(k);
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i].bel>>x[i].p;
    for(int i=1;i<=n;i++)
        cin>>y[i].bel>>y[i].p;
    // sort(x+1,x+n+1,cmp);
    // sort(y+1,y+n+1,cmp);
    int now=1;
    // for(int i=1;i<=n;i++)
    //  cout<<x[i].p<<" ";
    // cout<<endl;
    // for(int i=1;i<=n;i++)
    //  cout<<y[i].p<<" ";
    // cout<<endl;
    for(int i=1;i<=n;i++)
    {
        while(now<=n&&x[i].p<=y[now].p)
            now++;
        p[i]=now-1;
    }
    // for(int i=1;i<=n;i++)
    //  cout<<p[i]<<" ";
    // cout<<endl;
    for(int i=1;i<=n;i++)
    {
        update(1,1,n,1,p[i],1);
        update(1,1,n,1,i,-1);
    }
    int loc=n;
    for(int i=n;i>=1;i--) 
    {
        while(loc>=1&&p[loc]>=i)
            st[x[loc].bel].push(loc),loc--;
        if(st[y[i].bel].empty()) 
        {
            ans++;
            continue;
        }
        int now=st[y[i].bel].top();
        update(1,1,n,1,p[now],-1);
        update(1,1,n,1,i,1);
        if(t[1].minn>=0) st[y[i].bel].pop();
        else 
        {
            ans++;
            while(!st[y[i].bel].empty())
                st[y[i].bel].pop();
            update(1,1,n,1,p[now],1);
            update(1,1,n,1,i,-1);
        }
    }
    cout<<ans<<endl;
    return 0;
}
//写完写笔记