gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2481(树状数组)
 1#include <cstdio>
 2#include <algorithm>
 3using namespace std;
 4
 5const int SIZE = 100005;
 6
 7struct RANGE
 8{
 9    int m_S, m_E;
10    int m_p;
11
12    bool operator < (const RANGE& other) const
13    {
14        if ( m_E != other.m_E )
15            return (m_E > other.m_E);
16        
17        return (m_S < other.m_S);
18    }
19}cow[SIZE];
20
21int N, result[SIZE], C[SIZE], max_N;
22
23int LowBit( const int & k )
24{
25    return (k & (-k));
26}
27
28void Modify(int num, int value)
29{
30    while ( num <= max_N )
31    {
32        C[num] += value;
33        num += LowBit(num);
34    }
35}
36
37int GetSum(int num)
38{
39    int sum = 0;
40    while ( num > 0 )
41    {
42        sum += C[num];
43        num -= LowBit(num);
44    }
45
46    return sum;
47}
48
49void Init()
50{
51    for ( int i = 0; i <= max_N; ++i )
52    {
53        C[i] = 0;
54    }
55}
56
57int main()
58{
59    int i;
60
61//    freopen("1.txt", "r", stdin);
62    while ( scanf("%d", &N), N != 0 )
63    {
64        max_N = 0;
65        for ( i = 0; i < N; ++i )
66        {
67            scanf("%d %d", &cow[i].m_S, &cow[i].m_E);
68            cow[i].m_S++, cow[i].m_E++;
69            cow[i].m_p = i;
70
71            if ( max_N < cow[i].m_E )
72                max_N = cow[i].m_E;
73        }
74        Init();
75
76        sort(cow, cow + N);
77
78        for ( i = 0; i < N; ++i )
79        {
80            if ( i != 0 && cow[i].m_S == cow[i - 1].m_S && cow[i].m_E == cow[i - 1].m_E )
81                result[cow[i].m_p] = result[cow[i - 1].m_p];
82            else
83                result[cow[i].m_p] = GetSum( cow[i].m_S );
84
85            Modify( cow[i].m_S, 1 );
86        }
87
88        for ( i = 0; i < N - 1; ++i )
89            printf("%d ", result[i]);
90        printf("%d\n", result[i]);
91    }
92    return 0;
93}
posted on 2009-04-11 16:50 巫 阅读(778) 评论(7)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: POJ 2481(树状数组)[未登录] 2010-05-30 21:48 Klion
你好，请问，对于您的这段代码
for ( i = 0; i < N; ++i )
79 {
80 if ( i != 0 && cow[i].m_S == cow[i - 1].m_S && cow[i].m_E == cow[i - 1].m_E )
81 result[cow[i].m_p] = result[cow[i - 1].m_p];
82 else
83 result[cow[i].m_p] = GetSum( cow[i].m_S );
84
85 Modify( cow[i].m_S, 1 );
86 }
我把其中的80行到84行改成如下的为什么不行呢？还请指教
result[cow[i].m_p]= GetSum(cow[i].m_s);
int j = i;
while(j > 0 && cow[j].m_s == cow[j-1].m_s && cc[j].m_e == cc[j].m_e)
j--;
result[cow[i].m_p]= result[cow[i].m_p] - (i-j);

  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 22:22 gzwzm06
我也不知道为什么，看不懂ls的代码，好像这样改，逻辑都变了  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 22:37 Klion
@gzwzm06
哦，我的代码好像改错了
应该是这样的
result[cow[i].m_p]= GetSum(cow[i].m_s);
int j = i;
while(j > 0 && cow[j].m_s == cow[j-1].m_s && cow[j].m_e == cow[j].m_e)
j--;
result[cow[i].m_p]= result[cow[i].m_p] - (i-j);
逻辑改了？不怎么懂，我的就是先对每个点GetSum一次，然后再在已经Modify过的数据中找和它相同的，然后再减去这些相同的。
  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 23:24 gzwzm06
&& cow[j].m_s == cow[j-1].m_s && “cow[j].m_e == cow[j].m_e“
为什么会两个相同一起比较呢？是不是cow[j].m_e == cow[j - 1].m_e呢？  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 23:28 Klion
@gzwzm06
两个相同一起比较也就是两个区间是一样的，起点和终点是相同的，和您的第80行比较的应该是一样的吧？  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 23:31 gzwzm06
你再检查下，cc[j].m_e == cc[j].m_e这个条件肯定是真的，没有意义吧  回复  更多评论
  

# re: POJ 2481(树状数组) 2010-05-30 23:39 Klion
@gzwzm06
哦，实在是不好意思，确实是那个地方，现在过了，谢谢了啊。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理