Cows 树状数组

Cows

题目

农夫约翰的牛发现，他的田地里沿着山脊生长的三叶草（我们可以将其视为一维数字线）特别好。

农夫约翰有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强的母牛的数量。

input

3
1 2
0 3
3 4
0

output

1 0 0

思路

就是求一个区间是多少个区间的子区间, 且不能相等。
区间问题自然先想到排序, 我们按照右端点从大到小排序, 对于任何一个区间 i :
range[i].r >= range[i - 1].r 那么只需要找到 [1, i) 之间 所有 左端点 < range[i].l 的区间数量, 就是该区间的子区间总数。

那么如何找到一个乱序数组中所有 <= x的数量呢？
注意到该题区间数值 <= 1 0 5 10^5 105, 也就是说我们可以用一个bool数组来代表所有数。
然后使用线段树/树状数组来求这个和。

也可以再进行右端点的排序, 然后二分找到位置。

这里使用树状数组来实现这个操作。

代码

#include 
#include 
#include 
#include 
#include 
#include 
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];elseres[j] = sum(range[i].l);add(range[i].l);}for (int i = 1; i <= n; i++)cout << res[i] << " ";cout << "\n";}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！