蒲公英的约定 题解
题意回顾
给定平行志愿招生规则下每个人的报名志愿和中考分数，支持以下操作：
- 减少一个学校的招生名额若干，求出有多少个学生的录取结果改变。
人数、学校数、操作数均不超过
分析
记人数、学校数、操作数、分数档位数和志愿的量级均为
考虑一次志愿录取计算的时间复杂度为
考虑如果直接用数据结构维护这个问题的话，很难操作，但是操作只是有减少名额，容易发现每个人录取的志愿位次必然越来越靠后。故我们只需要在对数时间内完成一个人志愿录取位次靠后的处理即可。
我们发现这个过程类似于一棵树上的搜索，对于减少名额的学校需要踢出分数靠后的学生；而对于这些学生的志愿录取位次向后推移可能会导致其他学校部分分数靠后的学生被踢出。所以实现学校踢出学生函数和学生找学校即可，注意每个学生影响范围必然是分数比他更低的学生所以每次要找到分数最高的录取结果需要改变的学生开始操作。
注意以下实现细节：
- 维护每个人目前考虑到的志愿位次；
- 在目前录取结果改变的学生中每次要找到的是分数最高的学生找到新的录取结果；
- 一个实现技巧是维护目前学校录取的分数线，若学生分数高于或等于分数线即可进入学校。（因为每次从高分学生开始找学生录取结果改变情况所以分数线更高的学校必然是已经被更新完分数线了）
- 代码注释中该维护的内容维护全。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 3e5 + 5;
const int M = 1e6 + 5;
int n, m, q;
int t[N];//总录取名额
vector<int> g[N];//志愿列表
int o[N];//中考分数
set<int> scl[N];//学校分数段集合*
int tot[N];//学校录取人员总数*
struct node {
int sc, ps;//分数及录取结果
node(int scx, int psx) {
sc = scx, ps = psx;
}
};
bool operator<(node p1, node p2) {
return (p1.sc == p2.sc) ? (p1.ps < p2.ps) : (p1.sc > p2.sc);
}
map<node, int> id;//对应录取人员组编号
vector<int> res[M];//录取人员集合*
int cur[N];//志愿论次编号*
vector<int> tmp[M];
int avi[N];
set<node> se;
void enter(int x, int k);
void FindSchool(int x) {
for(int i = cur[x]; i < g[x].size(); i++) {
cur[x] = i + 1;
int school = g[x][i];
bool ok = false;
ok |= t[school] > tot[school];
if(scl[school].size() > 0) ok |= o[x] >= *(scl[school].begin());
if(ok) {
enter(x, school);
return;
}
}
}
void kick(int x) {
set<int>::iterator it = scl[x].begin();
while(it != scl[x].end()) {
int score = *it;
int idx = id[node(score, x)];
if(tot[x] - res[idx].size() < t[x]) {
break;
}
tot[x] -= res[idx].size();
se.insert(node(score, x));
it++;
}
if(it != scl[x].begin()) scl[x].erase(scl[x].begin(), it);
}
void enter(int x, int k) {
scl[k].insert(o[x]);
res[id[node(o[x], k)]].push_back(x);
tot[k]++;
kick(k);
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= m; i++) scanf("%d", &t[i]), avi[i] = (bool)t[i];
int u, v;
for(int i = 1; i <= n; i++) {
scanf("%d", &u);
for(int j = 1; j <= u; j++) {
scanf("%d", &v);
g[i].push_back(v);
}
scanf("%d", &o[i]);
tmp[o[i]].push_back(i);
}
int ct = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < g[i].size(); j++) {
if(id.find(node(o[i], g[i][j])) == id.end()) {
id[node(o[i], g[i][j])] = ++ct;
}
}
}
for(int i = M - 5; i >= 0; i--) {
for(int j = 0; j < tmp[i].size(); j++) {
int k = tmp[i][j];
for(int p = 0; p < g[k].size(); p++) {
int s = g[k][p];
cur[k] = p + 1;
if(avi[s]) {
enter(k, s);
if(tot[s] >= t[s]) avi[s] = 2, se.insert(node(s, 0));
break;
}
}
}
for(set<node>::iterator it = se.begin(); it != se.end(); it++) avi[it -> sc] = 0;
se.clear();
}
for(int qi = 1; qi <= q; qi++) {
scanf("%d%d", &u, &v);
t[u] -= v;
kick(u);
int ans = 0;
while(!se.empty()) {
set<node>::iterator it = se.begin();
int score = it -> sc;
while(it != se.end() && (it -> sc) == score) {
int idx = id[*it];
ans += res[idx].size();
for(int i = 0; i < res[idx].size(); i++) FindSchool(res[idx][i]);
res[idx].clear();
it++;
}
se.erase(se.begin(), it);
}
se.clear();
printf("%d\n", ans);
}
return 0;
}后记
每个六月，都是千千万万个中国人根据自己的所谓「