poj 2481 - Cows(树状数组)

看的人家的思路，没有理解清楚，，，

结果一直改一直交，，wa了4次才交上，，，

注意: 为了使用树状数组，我们要按照e从大到小排序。但s要从小到大。（我开始的时候错在这里了）

代码如下：

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#include <set>

#include <map>

#define M 100005

#define INF 0x7fffffff

#define eps 1e-8

#define LL long long

#define LLU unsigned long long

#define lowbit(x) (x&-x)

using namespace std;

int c[M], r[M], s[M], e[M], ans[M], n, maxx;

void add(int x)

{

	for(int i = x; i <= maxx; i+=lowbit(i))

		c[i] += 1;

}

int sum(int x)

{

	int ret = 0;

	for(int i = x; i > 0; i-=lowbit(i))

		ret += c[i];

	return ret;

}

int comp(const int a, const int b) { return e[a]==e[b]?s[a]<s[b]:e[a]>e[b]; }

int main ()

{

	while(~scanf("%d", &n) && n)

	{

		memset(c,0,sizeof(c));

		maxx = -INF;

		for(int i = 1; i <= n; ++i)

		{

			scanf("%d%d", &s[i], &e[i]);

			maxx = max(maxx, e[i]);

			r[i] = i;

		}

		sort(r+1, r+1+n, comp);

		for(int i = 1; i <= n; ++i)

		{

			int d = r[i];

			if(i!=1&&s[d]==s[r[i-1]]&&e[d]==e[r[i-1]])

				ans[d] = ans[r[i-1]];

			else

				ans[d] = sum(s[d]+1);

			add(s[d]+1);

		}

		printf("%d", ans[1]);

		for(int i = 2; i <= n; ++i)

			printf(" %d", ans[i]);

		printf("\n");

	}

	return 0;

}

巴特西

poj 2481 - Cows(树状数组)

最新文章

热门文章