题解：CF1179C Serge and Dining Room

jcs_pp · 2026-10-22 08:17:41 · 题解

我们先考虑无修改时怎么做，模拟一遍过程，这样可以帮助我们发现其中的性质，更快地想出解法。

通过模拟，我们发现，学生和菜的顺序并不重要，证明如下。

• 首先，菜本来就没有顺序。
• 然后我们考虑调换学生顺序会不会对答案产生影响，也就是对接下来剩下的菜有影响。
• 先考虑调换两个本来就有菜买的学生，这显然没有影响，可能出现的变化只是两个人互换了菜。
• 再考虑调换两个要离队的学生，这也没有影响，没菜买还是没影响。
• 考虑调换原本离队的人和买得到菜的人。对于一个学生原序号为 i，他要离队当且仅当他可以买的菜都被卖光了或本来他就什么都买不起。后者不用考虑，显然对结果无影响。我们用特殊学生 j 举例。j 在 i 之前，满足他买菜时只有一盘菜 k 满足 a_k < b_i，而他买了这道菜，所以我们可以得知，这是他能买的最大价值的菜，故也只有这一盘菜是 j 买得起的。所以将 i 与 j 调换顺序，从 j 买菜、i 离队转变为 i 买菜、j 离队，对结果没有影响。此类调换皆可同理类推，这类调换只会让离队的学生变化，不会对菜产生影响。

所以我们证明了，菜和学生的顺序不重要，但这又有什么用呢。这样，我们每次可以将学生和菜按 b_i 和 a_i 铺在数轴上，每次选出任意一个学生，向左找到第一个菜，与之匹配。

而实现此过程需要权值线段树。我们维护两个值，一个是此区间内的未匹配菜的个数，一个是此区间内未匹配的学生个数。每次查寻直接在线段树上二分，找到最有一个有未匹配的菜的区间，时间复杂度 O(n \log{n})。

:::info[Code]

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

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define repb(i, a, b) for(int i = (a); i >= (b); --i)

const int N = 300005;
const int MX = 1e6 + 5;

int n, m;
int a[N], b[N];

struct SEG_Tree{
    struct Node{
        int lx, rx; //此区间内的未匹配菜的个数，此区间内未匹配的学生个数
    }tr[MX << 2];
    #define ls (i << 1)
    #define rs (i << 1 | 1)
    inline void pushup(Node &fa, Node l, Node r){
        int m = min(l.lx, r.rx);
        fa.lx = l.lx + r.lx - m;
        fa.rx = l.rx + r.rx - m;
    }
    void mdf(int i, int L, int R, int p, int x){
        if(L == R){
            if(tr[i].lx == tr[i].rx){
                if(x == 1) tr[i].lx ++;
                else tr[i].rx ++;
            }
            else if(tr[i].lx) tr[i].lx += x;
            else tr[i].rx -= x;
            return;
        }
        int mid = L + R >> 1;
        if(p <= mid) mdf(ls, L, mid, p, x);
        else mdf(rs, mid + 1, R, p, x);
        pushup(tr[i], tr[ls], tr[rs]);
    }
    int qry(int i, int L, int R, int k){ //k: 后面一段区间中的未匹配学生，需要先匹配他们 
        if(!tr[i].lx) return -1;
        if(L == R) return L;
        int mid = L + R >> 1;
        if(tr[rs].lx > k) return qry(rs, mid + 1, R, k);
        else if(tr[ls].lx > k + tr[rs].rx - tr[rs].lx) return qry(ls, L, mid, k + tr[rs].rx - tr[rs].lx);
        else return -1;
    }
}seg;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n){
        cin >> a[i];
        seg.mdf(1, 1, MX, a[i], 1);
    }
    rep(i, 1, m){
        cin >> b[i];
        seg.mdf(1, 1, MX, b[i], -1);
    }
    int q;
    cin >> q;
    while(q--){
        int op, i, x;
        cin >> op >> i >> x;
        if(op == 1){
            seg.mdf(1, 1, MX, a[i], -1);
            seg.mdf(1, 1, MX, a[i] = x, 1);
        }
        else{
            seg.mdf(1, 1, MX, b[i], 1);
            seg.mdf(1, 1, MX, b[i] = x, -1);
        }
        cout << seg.qry(1, 1, MX, 0) << '\n';
    }

    return 0;
}

:::