感悟線段樹
其實線段樹的數據結構沒什么可說的,但是怎么用好它就有得說了。
具體的來說就是:
首先就是有段關系了,這個是第一位的。
接著就是有大小關系了,這個是第二位的。
再者就是數據量大,這個是次要的。
只要滿足了這三個條件,就是用線段樹的時候了。
如何理解段呢?比如說讓你統計小于200的數據有多少個。這個就是段了。
至于大小就是小于200的200了。
(1)1 3 2 4 5 63 563 23 46 56 23 455 …… 888 這個例子是落在888以前的。
(2)當然還是段中段,這個就不解釋了。
下面來貼出一道相關的題目。
http://acm.swust.edu.cn/oj/contest/29/825/
View Code
#include "iostream"
#include "cstdio"
#include "cstring"
#include "string"
#include "algorithm"
using namespace std;
#define Maxn 100005
struct Animals
{
int s, v;
bool Flag;
};
Animals RT[Maxn*2];
bool Cmp(Animals a, Animals b)
{
return (a.s<b.s);
}
struct Node
{
int Left, Right, Sum;
};
Node Tree[Maxn*4];
void BTree(int x, int y, int p)
{
Tree[p].Left = x;
Tree[p].Right = y;
Tree[p].Sum = 0;
if(x<y)
{
int Mid = (x+y)/2;
BTree(x, Mid, p<<1); //2*p
BTree(Mid+1, y, p<<1|1); //2*p+1 //mid+1哈,不然stack overflow
}
}
void Add(int x, int p)
{
if(Tree[p].Left==Tree[p].Right && Tree[p].Left==x)
{
Tree[p].Sum=(Tree[p].Sum+1)%2012;
return;
}
int Mid=(Tree[p].Left+Tree[p].Right)/2;
if(x<=Mid) Add(x, p<<1);
else Add(x, p<<1|1);
Tree[p].Sum = (Tree[p<<1].Sum+Tree[p<<1|1].Sum)%2012;
}
long long Query(int x, int y, int p)
{
if(Tree[p].Left==x && Tree[p].Right==y) return Tree[p].Sum;
int Mid = (Tree[p].Left+Tree[p].Right)/2;
if(y<=Mid) return Query(x, y, p<<1);
else if(x>=Mid+1) return Query(x, y, p<<1|1);
else return (Query(x, Mid, p<<1)+Query(Mid+1, y, p<<1|1))%2012;
}
int N;
int main()
{
int Max=0;
while(scanf("%d", &N)!=EOF)
{
for(int i=0; i<N; i++)
{
scanf("%d%d", &RT[i].s, &RT[i].v);
RT[i].Flag = true;
Max = max(Max, RT[i].v);
}
for(int i=N; i<2*N; i++)
{
scanf("%d%d", &RT[i].s, &RT[i].v);
RT[i].Flag = false;
Max = max(Max, RT[i].v);
}
sort(RT, RT+2*N, Cmp);
BTree(1, Max, 1);
int Ans = 0;
for(int i=0; i<2*N; i++)
{
if(RT[i].Flag)
{
if(RT[i].v==Max) continue;
Ans=(Ans+Query(RT[i].v+1, Max, 1))%2012;
}
else Add(RT[i].v, 1);
}
printf("%d\n", Ans);
}
}
posted on 2012-03-31 22:44 More study needed. 閱讀(307) 評論(0) 收藏 舉報

浙公網安備 33010602011771號