poj 2481 Cows(树状数组||线段树)
题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）
思路：
下面是一年前用树状数组过掉的时候写的题解： 和 star那道题差不多。需要注意的是star那道题读入的时候已经排好了序，而这道题没有排序
由于答案是按照下表输出，排序的时候下标会被打乱，所以要存一下下表到结构体里。
另一个区别是，star那道题星星不会重复，就是说一个位置不会有多颗星星。
而这道题却可能，而且题目中说，如果区间的长度差为0（就是后面的那个不等式），那么不计数。
因为区间下标可能为0，但是树状数组的下表必须从1开始，所以下表要+1，但是由于下表可能有所重复，所以 不能用++,而是用+1
不然会增加多次（我就是这么w a了两次。。。）
树状数组ac代码：
1/*************************************************************************
2 > File Name: code/poj/2481.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月04日 星期二 02时06分05秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#define y0 abc111qqz
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define tm crazy111qqz
24#define lr dying111qqz
25using namespace std;
26#define REP(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef unsigned long long ULL;
29const int inf = 0x7fffffff;
30const int N=1E5+7;
31int n;
32int a[N],t[N];
33struct Q
34{
35 int s,e,id;
36}q[N];
37bool cmp (Q a,Q b)
38{
39 if (a.e>b.e) return true;
40 if (a.e==b.e&&a.s<b.s) return true;
41 return false;
42}
43int lowbit(int x)
44{
45 return x&(-x);
46}
47void update ( int x,int c)
48{
49 for ( int i = x ; i < N ; i = i + lowbit(i))
50 {
51 t[i] = t[i] + c;
52 }
53}
54int Sum ( int x)
55{
56 int res = 0;
57 for ( int i = x ; i >= 1 ; i = i - lowbit(i))
58 {
59 res = res + t[i];
60 }
61 return res;
62}
63int main()
64{
65 while (~scanf("%d",&n)&&n)
66 {
67 memset(t,0,sizeof(t));
68 memset(a,0,sizeof(a));
69 for ( int i = 0 ; i < n; i ++ )
70 {
71 scanf("%d %d",&q[i].s,&q[i].e);
72 q[i].id = i;
73 }
74 sort(q,q+n,cmp);
75 a[q[0].id] = 0; //0是最强的...
76 update(q[0].s+1,1);
77 for ( int i = 1 ; i < n ; i++)
78 {
79 if (q[i].e==q[i-1].e&&q[i].s==q[i-1].s)
80 {
81 a[q[i].id]=a[q[i-1].id]; // 完全一样，区间长度为0，不计数。
82 }
83 else
84 a[q[i].id] = Sum (q[i].s+1);
85 update(q[i].s+1,1);
86 }
87 for ( int i = 0 ; i < n-1 ; i++ )
88 cout<<a[i]<<" ";
89 cout<<a[n-1]<<endl;
90 }
91 return 0;
92}
当然这道题也可以用线段树做。
先对点进行排序，右端点降序为第一关键字，左端点升序为第二关键字。（不唯一）
这样做有一个什么好处呢？
我们在处理第i个区间的时候，第i个区间前面的区间的右端点，一定是不小于第i个区间的右端点的，
此时我们只需要找到使左端点也满足题意的区间，也就是第i个区间前面的区间中，左端点不大于第i个区间的左端点的区间。
如果我们每次处理一个区间，都将该区间的左端点插入到线段树中（这句话可能比较抽象，线段树记录的是以某点为根节点的子树所代表的区间中点的个数，插入以后某一点记录为1，否则为0.），那么当我们询问第i个区间漆面的区间中左端点不大于第i个区间的左端点的区间的时候，其实也就是查询从1（这道题左端点的下标是从0开始，不过个人比较喜欢从1）到第i个区间的左端点之间有多少个点。
此外还需要注意两个区间重合的情况，这种情况是不能算在内的，要特殊处理。
线段树ac代码：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年09月04日 星期日 13时44分09秒
4File Name :code/poj/r2481.cpp
5************************************************ */
6//之前这道题是用树状数组过的，这次写一个线段树版本
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E5+7;
33int tree[N<<2];//tree的含义很简单，表示的就是以节点i为根的子树所代表的区间中的点的个数。（由于初始没有点插入，所以初始化tree为0.
34int n ;
35int ans[N];
36struct node
37{
38 int l,r;
39 int id; //由于排序后打乱了顺序，所以要记录id.
40 bool operator < (node b)const
41 {
42 if (r!=b.r) return r>b.r;
43 return l<b.l;
44 }
45 bool operator == (node b)const
46 {
47 return l==b.l&&r==b.r;
48 }
49}a[N];
50void PushUp(int rt)
51{
52 tree[rt] = tree[rt<<1]+tree[rt<<1|1];
53}
54void update( int p,int l,int r,int rt)
55{
56 if (l==r)
57 {
58 tree[rt]++;
59 return ;
60 }
61 int m = (l+r)>>1;
62 if (p<=m) update(p,lson);
63 else update(p,rson);
64 PushUp(rt);
65}
66int query(int L,int R,int l,int r,int rt)
67{
68 if (L<=l&&r<=R)
69 return tree[rt];
70 int m = (l+r)>>1;
71 int ret = 0 ;
72 if (L<=m)
73 {
74 int res = query(L,R,lson);
75 ret = ret + res;
76 }
77 if (R>=m+1)
78 {
79 int res = query(L,R,rson);
80 ret = ret + res;
81 }
82 return ret;
83}
84int main()
85{
86 #ifndef ONLINE_JUDGE
87 freopen("code/in.txt","r",stdin);
88 #endif
89 while (~scanf("%d",&n))
90 {
91 if (n==0) break;
92 for ( int i = 1 ; i <= n ; i++)
93 {
94 scanf("%d%d",&a[i].l,&a[i].r);
95 a[i].l++;
96 a[i].r++; //index from 1 .
97 a[i].id = i;
98 }
99 sort(a+1,a+n+1);
100 ms(ans,0);
101 ms(tree,0);
102 for ( int i = 1 ; i <= n ; i++)
103 {
104 if (i>=2&&a[i]==a[i-1])
105 ans[a[i].id] = ans[a[i-1].id];
106 else ans[a[i].id] = query(1,a[i].l,1,1E5,1);
107 update(a[i].l,1,1E5,1);
108 }
109 for ( int i = 1 ; i <= n ; i++)
110 printf("%d%c",ans[i],i==n?'\n':' ');
111 }
112 #ifndef ONLINE_JUDGE
113 fclose(stdin);
114 #endif
115 return 0;
116}