原题链接：http://poj.org/problem?id=2481
题意：求区间真子集个数。
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<vector> #include<cstring> #include<queue> #include<stack> #include<algorithm> #include<cmath> #include<string> #include<stdio.h> #define INF 1000000000 #define eps 0.0001 using namespace std; struct Cow { int s, e; int index; bool operator<(Cow cow)const { if (e == cow.e) return s < cow.s; return e > cow.e; } }; int n; Cow cow[100010]; int c[100010]; int ans[100010]; int maxE; int lowbit(int x) { return x&(-x); } void update(int x) { while (x <= maxE) { c[x]++; x += lowbit(x); } } int sum(int x) { int ans = 0; while (x >= 1) { ans += c[x]; x -= lowbit(x); } return ans; } int main() { while (~scanf("%d", &n) && n) { maxE = 0; memset(c, 0, sizeof(c)); for (int i = 1; i <= n; i++) { scanf("%d%d", &cow[i].s, &cow[i].e); cow[i].s++;//树状数组起始不为0，加一 cow[i].index = i; maxE = max(maxE, cow[i].e); } sort(cow + 1, cow + n + 1); for (int i = 1; i <= n; i++) { if (cow[i].s == cow[i - 1].s&&cow[i].e == cow[i - 1].e)//区间重合 ans[cow[i].index] = ans[cow[i - 1].index]; else ans[cow[i].index] = sum(cow[i].s); update(cow[i].s); } for (int i = 1; i < n; i++) printf("%d ", ans[i]); printf("%d\n", ans[n]); } return 0; }
