题解：P3696 Bushiroad的偶像派对

· · 题解

思路来自同机房大巨佬，膜拜。

转化一下题意，有集合 A（中场人气值）和集合 B（终场人气值），每个数字有一个标号（场次），你要把相同标号的 A 和 B 中的数字一一匹配。如果无法完全匹配，那么可以修改 B 集合中数字的标号，求最小修改次数。
考虑贪心，能不改变的就先不改变。
但是如果实在匹配不到必须要修改的时候，我们需要快速找到别的集合中没有被匹配到的数字进行匹配。
因此我们使用一棵值域线段树（事先离散化，也可以动态开点），来记录所有待匹配的值。
每一次我们先在当前集合中寻找可以匹配的值，如果可以匹配那么把它从线段树中删除。否则答案 +1，并把它也拍到线段树上，打上 -1 的标记。
这个标记什么意思呢？就是说我这里有一个数字，它需要被匹配。我们不知道它和谁匹配，但反正它需要被匹配。
这样有一个好处，就是线段树中的前缀和代表了当前等待着被匹配的数的数量。如果当前前缀和 <0，那么就代表当前不仅没有剩余的数，还多出了一些集合 B 的数，这是不可以的。
于是我们转化一下，用值域线段树维护当前的前缀和。

首先把所有“中场值”塞进线段树中。
比如样例，离散化后是

3
3 4
2 2
1 1
1 6
3 5
3 3

那么我们把 1,2,4 加入到线段树中。由于维护前缀和，因此加入 i，时，是把 [i,tot] 都 +1。
同时在标号对应的 set 中记录。
然后遍历 B 集合（记当前的数字为 x）。
在查询之前，我们需要处理掉标号对应 set 中一些不可以参加匹配的点。什么意思呢？就是由于先前打上了 -1 标记，有些数已经和 -1 标记匹配了，现在就不可以和 x 匹配。怎么检查呢？很简单，每次暴力遍历该集合中每个数，并在线段树中删去它们，如果全局最小值 <0 那么证明它不可以再拿出来匹配。如果找到了一个可以拿出来匹配的就直接 break，这样就可以保证复杂度。
然后找到小于等于 x 的最大的数。如果找不到，就需要在线段树中打 -1 标记并计算贡献，否则就把那个被匹配到的数从 set 中弹出去（并从线段树中删除）。

这样就做完了。注意离散化数组开了 2 倍，所以线段树要开 8 倍。
有一些细节在注释中。

#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,lsh[400005],tot,ans;
int typa[200005],sa[200005];
int typb[200005],sb[200005];
multiset<int>num[200005];

long long mn[1600005],laz[1600005];
void down(int rt)
{
    mn[rt<<1]+=laz[rt],
    laz[rt<<1]+=laz[rt],
    mn[rt<<1|1]+=laz[rt],
    laz[rt<<1|1]+=laz[rt],
    laz[rt]=0;
}
void add(int rt,int l,int r,int ll,int rr,int num)
{
    if(rr<l||r<ll) return;
    if(ll<=l&&r<=rr){mn[rt]+=num,laz[rt]+=num;return;}
    down(rt),add(rt<<1,l,(l+r)/2,ll,rr,num),
    add(rt<<1|1,(l+r)/2+1,r,ll,rr,num);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void cle(int wh)
{
    while(!num[wh].empty())
    {
        int dq=*num[wh].begin();
        add(1,1,tot,dq,tot,-1);
        if(mn[1]>=0){add(1,1,tot,dq,tot,1);break;}
        add(1,1,tot,dq,tot,1);//查询后记得还原回去
        num[wh].erase(num[wh].find(dq));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&typa[i],&sa[i]),lsh[i]=sa[i];
    for(int i=1;i<=n;i++) scanf("%d%d",
    &typb[i],&sb[i]),lsh[i+n]=sb[i];
    sort(lsh+1,lsh+2*n+1),
    tot=unique(lsh+1,lsh+2*n+1)-lsh-1;
    for(int i=1;i<=n;i++) sa[i]=
    lower_bound(lsh+1,lsh+tot+1,sa[i])-lsh,
    num[typa[i]].insert(sa[i]),
    add(1,1,tot,sa[i],tot,1);
    for(int i=n;i>=1;i--)
//由于输入数据从大到小排序，因此要从后往前遍历
    {
        sb[i]=lower_bound(lsh+1,lsh+
        tot+1,sb[i])-lsh;cle(typb[i]);
        if(num[typb[i]].empty()||
        num[typb[i]].upper_bound(sb[i])
        ==num[typb[i]].begin())
        {ans++,add(1,1,tot,sb[i],tot,-1);continue;}
//在线段树上打-1标记
        auto dq=prev(num[typb[i]].upper_bound(sb[i]));
        add(1,1,tot,*dq,tot,-1),num[typb[i]].erase(dq);
//用“-1”标记代表从线段树中删除数字，同时从 set 中删除
    }printf("%d",ans);
}