202503021943 Cows

求一个区间是多少个区间的子区间Cows

title: 题目
农夫约翰的牛发现，他的田地里沿着山脊生长的三叶草（我们可以将其视为一维数字线）特别好。
 
农夫约翰有N头母牛（我们将母牛的编号从1到N）。每位农夫约翰的N头母牛都有她特别喜欢的三叶草范围（这些范围可能重叠）。范围由闭合间隔[S，E]定义。
 
但是有些母牛很强壮，有些却很弱。给定两个母牛：母牛i和母牛j，它们最喜欢的三叶草范围是[Si，Ei]和[Sj，Ej]。如果Si <= Sj并且Ej <= Ei并且Ei-Si> Ej-Sj，我们说母牛i比母牛j强。
 
对于每头母牛，有几头母牛比她强？农夫约翰需要您的帮助！
 
输入项
 
输入包含多个测试用例。
 
对于每个测试用例，第一行是整数N（1 <= N <= 10 ^ 5），它是母牛的数量。然后是N行，其第i行包含两个整数：S和E（0 <= S
 
输入的末尾包含单个0。
 
输出量
 
对于每个测试用例，输出一行包含n个以空格分隔的整数，其中第i个数字指定比母牛i强的母牛的数量。
 

title: input
3
1 2
0 3
3 4
0

title: output
1 0 0

title: 思路
 
就是求一个区间是多少个区间的子区间, 且不能相等。
区间问题自然先想到排序, 我们按照右端点从大到小排序, 对于任何一个区间 i :
`range[i].r >= range[i - 1].r` 那么只需要找到 `[1, i)` 之间 所有 `左端点 < range[i].l` 的区间数量, 就是该区间的子区间总数。
 
那么如何找到一个乱序数组中所有 <= x的数量呢？
注意到该题区间数值 <= $10^5$, 也就是说我们可以用一个bool数组来代表所有数。
然后使用线段树/树状数组来求这个和。
 
也可以再进行右端点的排序, 然后二分找到位置。
 
这里使用树状数组来实现这个操作。

title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int readInt()
{
    int t;
    scanf("%d", &t);
    return t;
}
 
//------- Coding Area ---------//
const int N = 1e5 + 10;
int n;
int t[N];
int res[N];
struct Range
{
    int l, r;
    int id;
 
} range[N];
 
inline bool cmp(const Range &a, const Range &b)
{
    if (a.r == b.r)
        return a.l < b.l;
    return a.r > b.r;
}
 
int lowbit(int x)
{
    return x & -x;
}
 
void add(int i)
{
    for (i; i <= n; i += lowbit(i))
        t[i] += 1;
}
 
int sum(int i)
{
    int sum = 0;
    for (i; i; i -= lowbit(i))
        sum += t[i];
    return sum;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while (cin >> n && n)
    {
        memset(t, 0, sizeof t);
        for (int i = 1; i <= n; i++)
        {
            cin >> range[i].l >> range[i].r;
            range[i].l += 1;
            range[i].r += 1;
            range[i].id = i;
        }
 
        sort(range + 1, range + 1 + n, cmp);
 
        for (int i = 1; i <= n; i++)
        {
            int j = range[i].id;
            if (i > 1 && range[i].l == range[i - 1].l && range[i].r == range[i - 1].r)
                res[j] = res[range[i - 1].id];
            else
                res[j] = sum(range[i].l);
            add(range[i].l);
        }
 
        for (int i = 1; i <= n; i++)
            cout << res[i] << " ";
        cout << "\n";
    }
 
    return 0;
}
~~~