https://www.acwing.com/problem/content/description/113/

有 $N$ 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 $N$ 头牛和每头牛开始吃草的时间 $A$ 以及结束吃草的时间 $B$，每头牛在 $[A,B]$ 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

$1≤N≤50000$

$1≤A,B≤1000000$

显然，这道题可以用优先队列来做（几乎所有题解都是这样做的）。

但是经过推理之后，不难发现，其实需要的牛栏数，就是被包含的线段数量最多的点被包含的线段的数量。

因此我们不难找到一种线段树做法：

以下是代码实现：

#include <bits/stdc++.h>
#define tpl t[p].l
#define tpr t[p].r
#define tpm t[p].maxn
#define tpa t[p].add
#define t2pl t[p*2].l
#define t2pr t[p*2].r
#define t2pm t[p*2].maxn
#define t2pa t[p*2].add
#define t2p1l t[p*2+1].l
#define t2p1r t[p*2+1].r
#define t2p1m t[p*2+1].maxn
#define t2p1a t[p*2+1].add
using namespace std;

struct tree
{
    int l;
    int r;
    int maxn;
    int add;
};

tree t[4004000];

void pushup(int p)
{
    tpm = max(t2pm, t2p1m);
}

void build(int p, int l, int r)
{
    tpl = l;
    tpr = r;
    if(l == r)
        return;
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}

void spread(int p)
{
    if(tpa)
    {
        t2pa += tpa;
        t2p1a += tpa;
        t2pm += tpa;
        t2p1m += tpa;
        tpa = 0;
    }
}

void change(int p, int l, int r)
{
    if(l <= tpl && tpr <= r)
    {
        tpm += 1;
        tpa += 1;
        return;
    }
    spread(p);
    int mid = (tpl + tpr) / 2;
    if(mid >= l)
        change(p * 2, l, r);
    if(mid < r)
        change(p * 2 + 1, l, r);
    pushup(p);
}

int n;

int main()
{
    cin >> n;
    build(1, 1, 1000000);
    for(int i = 1; i <= n; i = i + 1)
    {
        int l, r;
        cin >> l >> r;
        change(1, l, r);
    }
    cout << t[1].maxn;
    return 0;
}

经过评测，这个代码在实现计算牛栏数的时候确实没有问题，但是问题在于如何安排方案呢？