题解：P11787 「FAOI-R4」蒲公英的约定

沉石鱼惊旋 · 2025-02-23 14:46:43 · 题解

P11787 「FAOI-R4」蒲公英的约定

我们称『滑档』指一个学生由志愿 i 变为了志愿 j，且 i\lt j。『落榜』即为一个考生没有被任何学校录取。

发现一条性质：t_x 的减小只会导致更多的考生『滑档』。甚至于『落榜』。不会存在得到更好的志愿的情况。

这条性质联系生活实际不难看出，想必大家都没听说过某个学校减少招生结果本来没被这个学校录取的后来被录取了的这种事情。

或者感性理解一下这个招生的过程，首先 t_x 减小必然影响已经被 x 录取的分数最低的那一批学生。如果他们没被录取，就可能会『滑档』到自己的后面的志愿 y。然后分数比他低但是已经被 y 录取的考试也可能会因为人数原因而继续『滑档』。如果一个人志愿改变，只可能是自己目前最优秀的这个志愿被挤掉了。

那么看到此题中，我们设 cur_i 表示第 i 名学生目前被 a_{i,cur_i} 录取了。那么每进行一次操作，cur_i 单调不降。也就是说，q 次操作，cur_i 的总增量是 \mathcal O(\sum l) 级别的。那么我们就可以对每个询问暴力求出具体是哪些学生『滑档』甚至『落榜』了。

再次回忆这个 t_x 减小的过程。我们可以拟定一个分数线 L_x。所有被第 x 所学校录取，且严格低于 L_x 的学生就会『滑档』。

我们对每个学校维护什么分数的什么学生被这所学校录取了。每次 t_x 减小，找到第 t_x 大的分数 L_x。把严格小于 L_x 的学生记录为『滑档』。被『滑档』的学生按照分数排名，扔进自己下个志愿的学校 y 里。由于学校 y 可能会达到录取上限，我们再找出这所学校的分数线 L_y。把严格小于 L_y 的学生标记为『滑档』，加入分数排名，循环做这个：“标记『滑档』——拟定分数线——末位淘汰”的事情。

新的学生参与排名我们可以用堆简单实现。之后我们还需要支持每个学校快速查询第 k 大的分数，以及插入删除学生。可以使用平衡树维护。

我的代码里使用了 __gnu_pbds::tree 实现。可以通过 __gnu_pbds 简单写出一个考场可用的平衡树。其中红黑树 __gnu_pbds::rb_tree_tag 性能最佳。代码里用的就是红黑树。

https://www.luogu.com.cn/record/204321549

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
template <class T>
void write(T x)
{
    static int stk[30];
    if (x < 0)
        putchar('-'), x = -x;
    int top = 0;
    do
    {
        stk[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        putchar(stk[--top] + '0');
}
template <class T>
void write(T x, char lastChar) { write(x), putchar(lastChar); }
int n, m, q;
vector<int> a[300020];
int sc[300020];
int p[300020];
int cur[300020];
int t[300020];
int b[300020];
int fa[300020];
int F(int u) { return u ^ fa[u] ? fa[u] = F(fa[u]) : u; }
void U(int u, int v) { fa[F(u)] = F(v); }
int change;
// set<array<int, 2>> s[300020];
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> s[300020];
void doit(int f = 0)
{
    if (f)
    {
        map<int, int> done;
        set<pair<int, int>> q;
        auto add = [&](int f)
        {
            // cerr << f << ' ' << t[f] << '\n';
            // cerr << s[f].size() << '\n';
            if (s[f].size() <= t[f])
                return;
            if (!t[f])
            {
                while (!s[f].empty())
                    q.insert(*--s[f].end()), s[f].erase(--s[f].end());
                return;
            }
            int ln = (*s[f].find_by_order(t[f] - 1)).first;
            // cerr << "sz,ln: " << s[f].size() << ' ' << ln << '\n';
            // cerr << (*--s[f].end()).first << ' ' << (*--s[f].end()).second << '\n';
            while (!s[f].empty() && (*--s[f].end()).first > ln)
                q.insert(*--s[f].end()), s[f].erase(--s[f].end());
        };
        change = 0;
        add(f);
        while (!q.empty())
        {
            auto [sc, u] = *q.begin();
            q.erase(q.begin());
            cur[u]++;
            if (!done.count(u))
                done[u] = 1, change++;
            if (cur[u] == a[u].size())
                continue;
            s[a[u][cur[u]]].insert({sc, u});
            add(a[u][cur[u]]);
        }
        return;
    }
    change = 0;
    map<int, int> mp;
    int lst_p = 0;
    vector<int> vec;
    for (int i = 1; i <= n; i = F(i + 1))
    {
        int k = p[i];
        if (sc[k] != sc[lst_p])
        {
            for (auto [x, y] : mp)
                b[x] += y;
            mp.clear();
        }
        // cerr << k << ' ' << sc[k] << '\n';
        int lst = !f ? -1 : cur[k];
        for (int &j = cur[k]; j < a[k].size(); j++)
        {
            if (b[a[k][j]] < t[a[k][j]])
            {
                mp[a[k][j]]++;
                break;
            }
            else
            {
            }
        }
        // cerr << cur[k] << '\n';
        if (cur[k] == a[k].size())
            vec.emplace_back(i);
        change += cur[k] != lst;
        lst_p = k;
    }
    for (auto [x, y] : mp)
        b[x] += y;
    mp.clear();
    // cerr << "vec " << vec.size() << '\n';
    // for (int i : vec)
    //     cerr << i << ' ';
    // cerr << '\n';
    for (int i : vec)
        U(i, i + 1);
    for (int i = 1; i <= n; i++)
    {
        if (cur[i] < a[i].size())
            s[a[i][cur[i]]].insert({-sc[i], i});
    }
}
int main()
{
    read(n, m, q);
    for (int i = 1; i <= m; i++)
        read(t[i]);
    for (int i = 1; i <= n; i++)
    {
        int len;
        read(len);
        a[i].resize(len);
        for (int &j : a[i])
            read(j);
        read(sc[i]);
    }
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    fa[n + 1] = n + 1;
    sort(p + 1, p + n + 1, [&](int x, int y)
         { return sc[x] > sc[y]; });
    doit(0);
    // cout << change << '\n';
    // for (int i = 1; i <= n; i++)
    //     cout << (cur[i] == a[i].size() ? 0 : a[i][cur[i]]) << ' ';
    // cout << '\n';
    while (q--)
    {
        int x, v;
        read(x, v);
        // cerr << "sub: " << x << ' ' << v << '\n';
        t[x] -= v;
        // cerr << t[x] << '\n';
        doit(x);
        write(change, '\n');
        // for (int i = 1; i <= n; i++)
        //     cout << (cur[i] == a[i].size() ? 0 : a[i][cur[i]]) << ' ';
        // cout << '\n';
    }
    return 0;
}