😊😊😊😊😊😊😊😊😊✔✔✔✔✔✔✔✔✔👀👀👀👀👀👀👀👀👀😃😃😃😃😃😃😃😃🤦‍♂️🤦‍♂️🤦‍♂️🤦‍♂️🤦‍♂️🤦‍♂️🤦‍♂️ヾ(≧▽≦)oヾ(≧▽≦)oヾ(≧▽≦)oヾ(≧▽≦)oヾ(≧▽≦)oヾ(≧▽≦)oヾ(≧▽≦*)o℃¥£′㎜㏎㏄¤℉$₩″㎝㎎㏕₠°€¢㎡㎞㎏○₡₢₥₨₭₰￡₣₦₪₮₱￠≈＝≌＜≯[>﹙﹚﹛～∽﹢﹟‱%&×±﹜≠≡﹦≤＞≦]﹤﹥﹡／‰^#－≒≥≮^

?

❤❤❤❤❤❤❤❤❤❤❤

🎶🎶🎶🎶🎶🎶🎶🎶🎶🎶🎶🎶

$i_1 > i_3$，否则，我们可以将 $c_{i1}$ 和 $s_{i2}$ 从增广路径中删除，和最短增广路径矛盾；

$\rightarrow$ 反证，假设 $i_1 < i_3$，

1. ∵ $… \rightarrow c_{i1} \rightarrow s_{i2} \rightarrow c_{i3} \rightarrow …$

∴ $maxSPF[c_{i3}] \geqslant SPF[s_{i2}]$ ，同时 $minSPF[c_{i1}] \leqslant SPF[s_{i0}] \leqslant SPF[s_{i2}]$

1. ∵ $i_1 < i_3$

∴ $minSPF[c_{i3}] \leqslant minSPF[c_{i1}]$

∴ （综上画图可得） $minSPF[c_{i3}] \leqslant SPF[s_{i0}] \leqslant maxSPF[c_{i3}]$，因此我们可以将 $c_{i1}$ 和 $s_{i2}$ 从增广路径中删除，连接 $s_{i0}$ 和 $c_{i3}$，从而得到更短的增广路径，和上述的最短增广路径矛盾

为什么一定要降序，不能是升序

这里哨兵为什仫要设两个？只设置一个哨兵为什仫会出错？

能不能建图求二分图最大匹配？qwq

不能，复杂度高超了，匈牙利（nm）

能啊，dinic直接a了

dinic我记得二分图上跑是$m\sqrt m$ 的吧

为什么不可以从小到大排minspf，然后每次选择最小的spf呐

应该也是可以的，两种方法是对称的。

肯定是从小到大排$maxSPF$, 然后每次选择最小的$SPF$

啊对滴，之前手误了，从小到大排序的话要排$maxSPF$，然后每次选最小的$SPF$

其实从小到大排minspf,每次选择maxspf最小的(用堆维护)也是对的qwq，贪心思路大体上差不多，但严格证明就不知了qwq，code

解决了我的疑惑！谢谢！

funfact：精细实现可以做到O(n)

# TQL

强强强

这里为什么要设置哨兵？

这样写也可以：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int,int> PII;
const int N = 2510;

int n, m;
PII cows[N];

int main()
{
    cin >> n >> m;
    map<int, int> spfs;
    for (int i = 0; i < n; i ++ ) cin >> cows[i].first >> cows[i].second;
    for (int i = 0; i < m; i ++ )
    {
        int spf, cover;
        cin >> spf >> cover;
        spfs[spf] += cover; // 注意这里要写 +=，因为数据中存在spf值相同的防晒霜
    }
    sort(cows, cows + n);
    int res = 0;
    spfs[0] = 1e9;
    for (int i = n - 1; i >= 0; i -- )
    {
        auto spf = spfs.upper_bound(cows[i].second);
        spf --;
        if (spf->first >= cows[i].first)
        {
            res ++ ;
            if (--spf->second == 0)
                spfs.erase(spf);
        }
    }
    cout << res << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int c, l, t=0;
struct aabb{
    int mi, ma;
}aa[maxn];
struct ccdd{
    int s, c;
}bb[maxn];

bool sa(aabb x, aabb y){
    return x.mi<y.mi;
}
bool sb(ccdd x, ccdd y){
    return x.s<y.s;
}
int main(){
    scanf("%d%d", &c, &l);
    for(int i=0; i<c; i++)
        scanf("%d%d", &aa[i].mi, &aa[i].ma);
    for(int i=0; i<l; i++)
        scanf("%d%d", &bb[i].s, &bb[i].c);
    sort(aa,aa+c,sa);
    sort(bb,bb+l,sb);
    int i=0, j=0;
    while(i<c&&j<l){
        if(aa[i].mi<=bb[j].s&&aa[i].ma>=bb[j].s){
            if(bb[j].c>0) { t++; i++; bb[j].c--; }
            else { j++; }
        }
        if(bb[j].s>aa[i].ma) { i++; }
        if(bb[j].s<aa[i].mi) { j++; }
    }
    printf("%d", t);
    return 0;
}
    /*for(int i=0; i<c; i++)
        printf("%d %d\n", aa[i].mi, aa[i].ma);
    for(int i=0; i<l; i++)
        printf("%d %d\n", bb[i].s, bb[i].c);*/

求助大佬

迭代器是什么？

语法问题还是百度比较好。

您好大大，请问二分图为什么会超时呢？复杂度不是O(nm)吗？

最坏情况下 $m$ 是 $n^2$ 级别的，那么总时间复杂度就是 $n^3$ 了。

懂了，谢谢！

大佬，我这个代码哪里出了问题了呀

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=3500;
typedef pair<int,int>Pll;
Pll a[N];
map <int,int>b;
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i].first>>a[i].second;
    sort(a,a+n);
    for(int i=0,x,y;i<m;i++)
    {
        cin>>x>>y;
        b[x]+=y;
    }
    int ans=0;
       for(int i=0;i<n;i++)
        for(auto it=b.begin();it!=b.end();it++)
        if(it->first>=a[i].first&&it->first<=a[i].second&&it->second)
          {
              --it->second;
              ans++;
              break; 
          } 
        cout<<ans<<endl;
        return 0;
}

这个做法和上面证明的算法是反着的，因此要完全对称过来。只需要把排序改成以区间右端点为第一关键字即可。

明白了，谢谢大佬

这里设置哨兵有什么作用啊 hhh

auto spf = spfs.upper_bound(cows[i].second);这句话是在spfs中查找大于cows[i].second的最小元素，设置哨兵是为了让这条语句不返回空。

tql Orz

SPF: Sun Protection Factor

从右往左：
if (spf->first >= cows[i].first && spf->first <= cows[i].second) 这行可以简化成
if (spf->first >= cows[i].first)

对滴~

从左往右：

    sort(cows, cows + n, [](PII lhs, PII rhs) {
        if (lhs.second == rhs.second) {
            return lhs.first < rhs.first;
        }

        return lhs.second < rhs.second;
    });

    int res = 0;
    spfs[0] = spfs[1001] = n;
    for (int i = 0; i < n; i ++ )
    {
        auto it = spfs.lower_bound(cows[i].first);
        if (it->first <= cows[i].second)
        {
            res ++ ;
            if (--it->second == 0)
                spfs.erase(it);
        }
    }

棒！按右端点从小到大排序，从左往右扫描也是可以的

但是这个好像只能过部分用例