[??记录]AT2372 [AGC013F] Two Faced Cards
command_block
2021-04-29 15:58:38
**题意** : 给出 $n$ 个二元组，记为集合 $X$。和 $n+1$ 个整数，记为集合 $Y$。
有 $q$ 个**相互独立**的操作。
每次会向 $X$ 中加入一个二元组，然后你需要：
1. 对 $X$ 中每一个二元组选定一个元素作为这个二元组的值，产生新集合 $X'$
2. 将 $X',Y$ 中元素两两匹配（此时 $|X'|=|Y|=n+1$）。$u\in X'$ 能匹配 $v\in Y$ 当且仅当 $u\leq v$。
3. 如果匹配成功，获得的分数等于：第 1 步中，取第一个数作为值的二元组数量。
对于每个操作，求最大匹配分数，或指出无解。
$n,q\leq 10^5$ ，时限$\texttt{2s}$。
------------
首先将所有数关于 $Y$ 离散化，这样值域就变为 $1\sim n+1$。
先不考虑操作。若给定 $X,Y$ ，如何求出最大分数。
对于二元组 $(x_1,x_2)$ ，若 $x_1\leq x_2$ ，则必选 $x_1$ 。
对于剩下的二元组，按照 $x_1$ 排序，不难发现最优方案一定翻一个后缀，逐个判定即可。
- 如何判定序列 $\{a_{1\sim n}\}$ 在任意排列后能否满足 $a_i\leq b_i$ ？
利用辅助数组 $o$ ，对于 $a_i$ ，将 $o[1\sim a]$ 减一。
对于 $b_i$ ，将 $o[1\sim b_i]$ 加一。
若 $o$ 全部非负，则存在合法方案。
- 于是，若将一个 $x_1<x_2$ 的 $(x_1,x_2)$ 翻面，则相当于将 $o(x_2,x_1]$ 加一。
现在考虑操作。
对于一个新加入的二元组 $(x_1,x_2)$ ，可以选择 $x_1$ 或者 $x_2$ ，影响是将 $o$ 的一个前缀 $-1$。
- 我们将问题转化为了 ：
给出 $o$ 数组，和若干个区间。
每次再（独立地）进行一次前缀减，问至少选多少个区间加一可以使得整个数组非负。或指出无解。
设这次单独的前缀减为 $[1,t]$ ，对于每个 $t$ 分别求出答案。
先求 $t=0$ 的答案。
从后往前查看 $o$ 中的元素，若遇到 $<0$ 的，则选取一个右端点大于等于它，且左端点尽量小的区间。这可以用堆来实现。
然后从小到大依次求 $t=1\sim n+1$ 的答案。
当 $t$ 增大时，$o[t]$ 会减一，若这之后 $o[t]<0$ ，则选择一个左端点小于等于它，且右端点尽量大的区间。这也用堆实现。
- 正确性理解 ： 容易发现上述贪心得到的方案中，任意去掉一个区间，都会导致不合法。
区间加可以用差分实现。
复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define MaxN 100500
using namespace std;
const int INF=1000000000;
int n,m,qt,x1[MaxN],x2[MaxN],y[MaxN],
s[MaxN],s2[MaxN],o[MaxN],ans[MaxN];
struct Data{int l,r;bool vis;}b[MaxN];
vector<int> gl[MaxN],gr[MaxN];
priority_queue<Pr> q;
int main()
{
scanf("%d",&n);n++;
for (int i=1;i<n;i++)
scanf("%d%d",&x1[i],&x2[i]);
for (int i=1;i<=n;i++){
scanf("%d",&y[i]);
o[i]=n-i+1;
}
sort(y+1,y+n+1);
for (int i=1;i<n;i++){
x1[i]=lower_bound(y+1,y+n+1,x1[i])-y;
x2[i]=lower_bound(y+1,y+n+1,x2[i])-y;
s[x1[i]]--;
if (x1[i]>x2[i])
b[++m]=(Data){x2[i]+1,x1[i]};
}
for (int i=n+1;i;i--)o[i]+=(s[i]+=s[i+1]);
for (int i=1;i<=m;i++){
gl[b[i].l].pb(i);
gr[b[i].r].pb(i);
}
bool fl=0;int sav=0;
for (int i=1;i<=n+1;i++)s[i]=0;
for (int i=n+1;i;i--){
s[i]+=s[i+1];
for (int j=0;j<gr[i].size();j++)
q.push(mp(-b[gr[i][j]].l,gr[i][j]));
while (o[i]+s[i]<0){
if (q.empty()){fl=1;break;}
int p=q.top().sec;q.pop();
b[p].vis=1;sav++;
s[i]++;s[b[p].l-1]--;
s2[b[p].r]++;s2[i]--;
}o[i]+=s[i];
}
for (int i=n+1;i;i--)o[i]+=(s2[i]+=s2[i+1]);
for (int i=1;i<=n+1;i++)s[i]=0;
while(!q.empty())q.pop();
for (int i=1;i<=n+1;i++){
s[i]+=s[i-1];
for (int j=0;j<gl[i].size();j++)
q.push(mp(b[gl[i][j]].r,gl[i][j]));
while (o[i]+s[i]<=0){
if (q.empty()){fl=1;break;}
int p=q.top().sec;q.pop();
if (b[p].vis)continue;
b[p].vis=1;sav++;
s[i]++;s[b[p].r+1]--;
}o[i]+=s[i];
ans[i]=fl ? INF : sav;
}ans[n+1]=INF;
scanf("%d",&qt);
for (int i=1,tx,ty;i<=qt;i++){
scanf("%d%d",&tx,&ty);
tx=lower_bound(y+1,y+n+1,tx)-y;
ty=lower_bound(y+1,y+n+1,ty)-y;
printf("%d\n",max(-1,n-min(ans[tx],ans[ty]+1)));
}return 0;
}
```