本文共 1449 字,大约阅读时间需要 4 分钟。
给出N个区间,求大于改区间的数目
using namespace std;int c[N], ans[N];struct cow{ int id, l, r;}a[N];bool cmp(const cow &x, const cow &y) { if (x.r != y.r) return x.r > y.r; else return x.l < y.l;}int get_sum(int x) { int res = 0; while (x > 0) { res += c[x]; x -= lowbit(x); } return res;}void update(int x, int y, int val) { while (x <= y) { c[x] += val; x += lowbit(x); }}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout);#endif ios::sync_with_stdio(false); int n; while (cin >> n, n) { mem(ans, 0); mem(c, 0); for (int i = 0; i < n; ++i) { cin >> a[i].l >> a[i].r; a[i].id = i; } // 按照右区间降序排列 sort(a, a + n, cmp); // 第一个区间不会被包含,更新左区间 update(a[0].l + 1, a[0].r + 1, 1); for (int i = 1; i < n; ++i) { // 区间重叠 if (a[i].l == a[i - 1].l && a[i].r == a[i - 1].r) ans[a[i].id] = ans[a[i - 1].id]; else { ans[a[i].id] = get_sum(a[i].l + 1); } // 即使区间重叠也要更新一次 update(a[i].l + 1, a[i].r + 1, 1); } cout << ans[0]; for (int i = 1; i < n; ++i) { cout << " " << ans[i]; } cout << endl; } return 0;}
转载地址:http://tkprf.baihongyu.com/