题解：CF1179C Serge and Dining Room

· · 题解

这是我们提高组练习题单的一题。

我们设 D(x) 等于“钱不少于 x 的学生数”减去“价格不少于 x 的菜数”。

那么显然，D(x)<0 表示 x 以上的菜学生买不完，至少剩一盘。答案就是所有真实菜价里满足 D(x)<0 的最大那个；没有就输出 -1。

学生排队顺序不影响这个最高剩价。因为当两个学生交换，若本来学生 A 在学生 B 前，且 A 所持有的钱数少于 B 所持有的钱数。

若 B 能买到比 A 所持有的钱数更贵的菜品，那么交换顺序互不影响，否则，若 A、B 所购买的菜品两人都可以买，那么交换顺序后一定也是都可以买，且一定买原来的菜品。

因此我们就证明了学生顺序与答案无关这件事。

现在我们考虑如何维护这个函数值。

考虑用线段树维护。对于一盘价格 c 的菜，我们让所有 x\le c 的 D(x) 减 1；一个带 c 元的学生，让所有 x \le c 的 D(x) 加 1。

查询时看整棵树的最小值：如果最小值都不小于 0，说明没有任何阈值缺学生，没剩菜，输出 -1；否则优先往右子树走，找到最右边 D(x)<0 的位置。

当不存在以我们计算出的最右边的满足条件的 x 为菜品价格时，我们需找到不大于 x 的最大真实菜价，同时需要保证 D(x)<0。

修改是简单的，我们只需去除旧的贡献，再加上新的贡献即可。维护方式同上。

时间复杂度为 O((N+M+Q)\log V)，可以通过。因为良心的题目把 V 控制在了 [1,10^6]，所以不用离散化。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int MX = 1e6;
const int INF = 1e9;
int n,m,q;
int a[N],b[N];
int cnt[N];
namespace SEG{
    int t[4 * N],tag[4 * N];
    inline void addtag(int p,int d){
        tag[p] += d;
        t[p] += d;
    }
    inline void pushdown(int p){
        if(tag[p]){
            addtag(p * 2,tag[p]);
            addtag(p * 2 + 1,tag[p]);
            tag[p] = 0;
        }
    }
    void change(int p,int l,int r,int lx,int rx,int d){
        if(l >= lx && r <= rx){
            addtag(p,d);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(p);
        if(mid >= lx) change(p * 2,l,mid,lx,rx,d);
        if(mid + 1 <= rx) change(p * 2 + 1,mid + 1,r,lx,rx,d);
        t[p] = max(t[p * 2],t[p * 2 + 1]);
    }
    int ask(int p,int l,int r){
        if(l == r) return l;
        pushdown(p);
        int mid = (l + r) >> 1;
        if(t[p * 2 + 1] > 0) return ask(p * 2 + 1,mid + 1,r);
        if(t[p * 2] > 0) return ask(p * 2,l,mid);
        return -1;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    SEG::change(1,1,MX,1,MX,-INF);
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(cnt[a[i]] == 0) SEG::change(1,1,MX,a[i],a[i],+INF);
        cnt[a[i]]++;
        SEG::change(1,1,MX,1,a[i],1);
    }
    for(int i = 1;i <= m;++i){
        cin >> b[i];
        SEG::change(1,1,MX,1,b[i],-1);
    }
    cin >> q;
    while(q--){
        int op,x,y;
        cin >> op >> x >> y;
        if(op == 1){
            int old = a[x];
            SEG::change(1,1,MX,1,old,-1);
            cnt[old]--;
            if(cnt[old] == 0) SEG::change(1,1,MX,old,old,-INF);
            SEG::change(1,1,MX,1,y,1);
            if(cnt[y] == 0) SEG::change(1,1,MX,y,y,INF);
            cnt[y]++;
            a[x] = y;
        }
        else{
            SEG::change(1,1,MX,1,b[x],1);
            b[x] = y;
            SEG::change(1,1,MX,1,b[x],-1);
        }
        cout << SEG::ask(1,1,MX) << '\n';
    }
    return 0;
}