WTF2022 Day2 C
lsj2009
·
·
题解
Preface
模拟赛搬了这个题，场上只想出了 \mathcal{O}(n^2) 的做法，赛后补了发现这也太牛了！！
网上的各种题解包括模拟赛的题解可能都写简略了，这里写个详细点的。
Description
给定 n 个二元组 (a_i,b_i) 和 m，将其两两匹配满足任意匹配 (i,j) 有 a_i\ne a_j 且 b_i+b_j\le m。
使得有匹配的 i 的 b_i 和最大。
## Solution
### Part 1
首先你很容易建图得到一个 **一般图最大权匹配** 的模型，如果我们真要暴力去做，那肯定是个 **不断寻找增广路** 的过程（其实可以注意到的是增广路长度 $\le 2$，这样子你可以获得一个 $\mathcal{O}(n^2)/\mathcal{O}(n^3)$ 的做法，但这和正解无关了）。
若我们称 $b_i\le \frac{m}{2}$ 的 $i$ 为 **小点**，其余为 **大点**。则匹配必然在小点与大点（称为小大），和小点内部（称为小型）进行，并且后者只要求 $a_i$ 不相同（下文称之为颜色）即可。
则我们有一个断言是：
- **若可以进行小大匹配，则必然进行而不会给小小匹配让路**。
证明的话考虑先拉出一个小大的匹配，这时候如果有一个 小小匹配想要加进来：
- 如果存在增广路则直接加入不会影响原有存在匹配的点的集合，故而直接加入即可。
- 否则此时若寻找一个交错路来更改匹配，**必然会有一个大点被删除**，然后该小点被加入，则这权值必然变小。
所以我们可以先进行所有小大匹配，然后再在处理小小匹配。
### Part 2
考虑如何找到 **参与小大匹配的大点集合 $C$**。
首先对于大点修改 $b_j$ 为 $m-b_j$，则 $b_i+b_j\le m$ 变为 $b_i\le b_j$。
此时将所有点按 $b$ 排序，然后从左往右扫描，在加入一个大点 $u$ 时考虑其是否在 $C$ 内。同理 Part 1 我们可以说明 **若存在增广路则 $u$ 在 $C$ 内**，否则不在。
但存在增广路很难判断，因为你要找出具体是咋匹配的，这难以做到很优，我们尝试计算匹配数。因为 **存在增广路即为二分图最大匹配数变大**。
根据 Hall 定理（大点为左部点）最大匹配数为 $|L|-\max\limits_{S\subseteq L}(|S|-|N(S)|)$。
由于往 $L$ 中加入 $u$ 时 $|L|$ 增大，若 $u\notin S$ 则无法说明最大匹配数不变；所以若我们想要去「攻击」$u$ 也就是说明其不在 $C$ 中，则 $u$ 需在 $S$ 中。
这时仅仅令 $S=\{u\}$ 就已经有 $N(S)$ 包含所有颜色和 $u$ 不相同的小点了。
不相同令人不是那么爽，考虑记 $H(S)=R\setminus N(S)$，则有最大匹配为 $|L|-\max\limits_{S\subseteq L}(|S|-(|R|-|H(S)|))=|L|+|R|-\max\limits_{S\subseteq L}(|S|+|H(S)|)$。
则 $H(S)$ 必然只有颜色和 $a_u$ 相同的小点。
进一步地，我们注意到 $H(S)$ 其实 **只和 $b$ 最大的，且颜色和 $a_u$ 不同的，在 $S$ 中的点 $v$ 有关**。
手摸一下，因为你会发现 $H(S)$ 中 **恰好留有 $b_i>b_v$ 且 $a_i=a_u$ 的 $i$**。且这时 $S$ 最大可以留有所有 $b$ 不到 $b_v$ 的点。
从左往右扫描的过程中容易做到 $\mathcal{O}(n)/\mathcal{O}(n\log{n})$ 对于每种颜色（一个集合 $S$ 的颜色就是 $a_u$）维护 $\max(|S|+|H(S)|)$。
则这样我们可以在 $\mathcal{O}(n)$ 复杂度内求出所有参与匹配的大点集合 $C$。
### Part 3
随后考虑在做完小大匹配后，**每种颜色的小点最少剩多少个**，记为 $f_i$（怎么算 $f$ 随后再说）；当然我们也可以获知到底有多少个小点是在小大匹配中没有用到的，记为 $x$。
找出 $y=\max f_i$。
我们断言：
- 若 $y\le \lfloor\frac{x}{2}\rfloor$：会有恰好 $x\bmod{2}$ 个小点无法匹配。
- 若 $y>\lfloor\frac{x}{2}\rfloor$：会有恰好 $y-(x-y)=2y-x$ 个小点无法匹配。
对于后者，我们有至多产生 $y-x$ 个匹配，则对于 $y$ 对应的颜色至少有 $2y-x$ 个点会被丢弃，丢掉后也就转到第一类情况。
对于第一类情况，当 $x\equiv 1\pmod{2}$ 时随便丢掉一个点归约到 $x\equiv 0\pmod{2}$ 的情况。则此时我们先随便拉出一种小大的匹配方案，记在这种情况下 **实际上第 $i$ 种颜色剩余小点个数为 $h_i$**：
- 若存在 $h_i\ge \frac{x}{2}$，则由于 $f_i\le \frac{x}{2}\le h_i$，我们必然可以不断寻找交错路将 $h_i$ 降到恰好 $\frac{x}{2}$，此时 **剩余 $\frac{x}{2}$ 个点全部与 $i$ 颜色点匹配即可**。
- 否则此时不存在某种颜色节点个数 $>\frac{x}{2}$，此时将所有节点依次放置为：
- $1\sim h_1$ 放置颜色为 $1$ 的点。
- $h_1+1\sim h_2$ 放置颜色为 $2$ 的点。
- ...
- $x-h_n+1\sim x$ 放置颜色为 $n$ 的点。
- 则取断点 $\frac{x}{2}$，**将 $i,i+\frac{x}{2}$ 配对即可**，其中 $i\le \frac{x}{2}$。
则我们现在问题变为：有一个可能作为删除点的序列，你需要在其中恰好删除 $k$ 个，使得仍然存在合法匹配并且删除权值最小。
这里其实就很简单了，只要一个点不是必须在匹配中的，他就可以被删除，倒着跑一遍 Part 1 即可（**左部点为的所有可能删除的小点**，右部点为所有大点），若加入一个小点后最大匹配不变，则其可以被删除。
对于所有可以被删除的点取 $b$ 前 $k$ 小的即可。
最后是如何求 $f$，题解讲了个（可能没咋讲）高妙 $\mathcal{O}(n)$ 做法，可惜我没看懂，故而只能暴力：
- 使得某种颜色剩余最少，即为尽可能多的匹配，并且我是尽可能多的匹配，所以 **不会影响匹配的存在性**，所以只需要考虑所有 $i$ 颜色的小点和所有大点尽可能匹配，由 $b$ 从大到小扫小点，使用堆（因为每次著需要取出 $b$ 最大的点）维护大点（每次处理 $i$ **不重新建堆**，做完把删掉的点再 push 回去）容易做到 $\mathcal{O}(n\log{n})$。
综上，该问题在 $\mathcal{O}(n\log{n})$ 复杂度内得到了解决。
### Code
```cpp
#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("chat.in","r",stdin);
freopen("chat.out","w",stdout);
}
bool M1;
namespace IO {
char Is[(1<<21)+10],Os[(1<<21)+10];
int Ipt,Opt;
char gc() {
if(Ipt==1<<21)
Ipt=0;
if(!Ipt)
Is[fread(Is,1,1<<21,stdin)]=0;
return Is[Ipt++];
}
void flush() {
fwrite(Os,1,Opt,stdout);
Opt=0;
}
void pc(char x) {
if(Opt==1<<21)
flush();
Os[Opt++]=x;
}
int read() {
int x=0,f=1;
char ch=gc();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=gc();
}
while(ch<='9'&&ch>='0')
x=(x<<3)+(x<<1)+ch-'0',ch=gc();
return x*f;
}
}
using namespace IO;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
const int N=1e6+5;
struct info {
int c,x,op;
info() {
;
}
info(int a,int b,int _c) {
c=a; x=b; op=_c;
}
bool operator < (const info &tmp) const {
return x<tmp.x||(x==tmp.x&&op<tmp.op);
}
}; info a[N],b[N];
int res,g[N],d[N],sl,sr;
bool add(int c,int op) {
if(!op) {
chkmax(g[c],sl);
++sr;
++g[c];
return true;
} else {
int t=res;
chkmax(g[c],sl);
++sl;
++g[c];
res=min(res+1,sl-(g[c]-sr));
return t!=res;
}
}
priority_queue<PII> heap;
vector<int> vec0[N],vec1[N];
bool used[N];
vector<PII> tmp;
PII top() {
while(!heap.empty()&&used[heap.top().second]) {
tmp.push_back(heap.top());
heap.pop();
}
if(heap.empty())
return make_pair(-INF,0);
else
return heap.top();
}
void solve() {
int n=read(),m=read();
rep(i,1,n) {
int c=read(),x=read();
if(x<=m/2)
a[i]=info(c,x,0);
else
a[i]=info(c,m-x,1);
}
sort(a+1,a+n+1);
int len=0;
ll tot=0;
int c0=0,c1=0;
rep(i,1,n) {
if(add(a[i].c,a[i].op)) {
b[++len]=a[i];
if(!a[i].op) {
tot+=a[i].x;
++c0;
vec0[a[i].c].push_back(a[i].x);
} else {
tot+=m-a[i].x;
++c1;
vec1[a[i].c].push_back(i);
heap.push(make_pair(a[i].x,i));
}
}
}
int pos=0,x=0;
rep(i,1,n) {
tmp.clear();
int c=0;
for(auto x:vec1[i])
used[x]=true;
reverse(vec0[i].begin(),vec0[i].end());
for(auto x:vec0[i]) {
PII val=top();
if(val.first>=x) {
heap.pop();
tmp.push_back(val);
} else
++c;
}
for(auto x:vec1[i])
used[x]=false;
for(auto x:tmp)
heap.push(x);
if((c<<1)>c0-c1) {
pos=i;
x=(c<<1)-(c0-c1);
break;
}
}
if(!pos)
x=(c0-c1)&1;
sl=sr=res=0;
rep(i,1,n)
g[i]=0;
int tt=0;
per(i,len,1) {
if(b[i].op||(!pos||b[i].c==pos)) {
if(!add(b[i].c,!b[i].op))
d[++tt]=b[i].x;
}
}
reverse(d+1,d+tt+1);
rep(i,1,x)
tot-=d[i];
printf("%lld\n",tot);
}
bool M2;
// g++ chat.cpp -std=c++14 -Wall -O2 -o chat
signed main() {
// file_IO();
int testcase=1;
// scanf("%d",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
```