线段树学习笔记

神牛传送门：

http://www.notonlysuccess.com/index.php/segment-tree-complete/

再加一个（风格是notonlysuccess的风格，写的很骚...）：

http://www.cnblogs.com/wuyiqi/tag/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%92%8C%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

线段树学习全记录：

代码风格：notonlysuccess

+++单点操作

poj--2828 Buy Tickets（线段树功能：单点更新）

题意：人们一个一个的来排队并插队，按人到来的顺序给出每个人插队的位置（插在第几个人后面），并告知每个人的id号，输出最终队伍的情况。

分析：可以用线段树，从最后来的一个人开始向来得更早的人遍历，这样pos（插在第几个人后面）的意义就变成了，前面有多少个空位。线段树上每个节点中存储的是当前时刻，该区间有多少空位。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #define lson l,m,rt<<1
 6 #define rson m+1,r,rt<<1|1
 7 
 8 using namespace std;
 9 
10 #define MAXN 200005
11 
12 //sum表示这个区间有多少个空位
13 
14 int sum[MAXN<<2];    //原数据量扩大4倍用int数组建树
15 int pos[MAXN],val[MAXN],ans[MAXN];
16 
17 void build(int l,int r,int rt)
18 {
19     sum[rt]=r-l+1;//初始化时空位数
20     if(l==r)   
21         return;
22       int m = (l+r)>>1;
23     build(lson);  //递归建左子树
24     build(rson);//递归建右子树
25 }
26 
27 int id;
28 //每次更新即将找到前面敲好p个空位
29 void update(int p,int l,int r,int rt)
30 {
31     sum[rt]--;//更新到l-->r这段时必然将占有原来的一个空位
32 
33     if (l==r)    //已经到最底端
34     {
35         id=l;//此时l前面敲好有p个空位
36         return ;
37     }
38     int m = (l + r) >> 1;
39     if (p<sum[rt<<1])       //左边的空位有多余p个空位
40         update(p ,lson);
41     else    
42     {
43         p-=sum[rt<<1];//减去左边的空位总数，假如：p=3，sum[rt<<1]=1,则递归调用右子树时的p值应该更新为2。
44         update(p , rson);
45     }
46 }
47 
48 int main()
49 {
50     int N;
51     while(scanf("%d",&N)!=EOF)
52     {
53         build(1,N,1);
54         for(int i=1;i<=N;i++)
55         {
56             ans[i]=0;
57             scanf("%d%d",&pos[i],&val[i]);
58         }
59 
60         for(int i=N;i>0;i--)
61         {
62             update(pos[i],1,N,1);
63             ans[id]=val[i];
64         }
65             
66         for(int i=1;i<=N;i++)
67         {
68             if(i==1)
69                 printf("%d",ans[i]);
70             else
71                 printf(" %d",ans[i]);
72         }
73 
74         printf("\n");
75     }
76     return 0;
77 }

hdu 1166 敌兵布阵（线段树功能:update:单点增减 query:区间求和）

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 #define ls rt<<1
 8 #define rs rt<<1|1
 9 #define lson l,m,ls
10 #define rson m+1,r,rs
11 #define mid (l+r)>>1
12 
13 #define MAXN  55555
14 
15 int sum[MAXN<<2];    //原数据量扩大4倍用int数组建树
16 
17 void PushUp(int rt)
18 {
19   sum[rt] = sum[ls] + sum[rs];
20 }
21 
22 void build(int l,int r,int rt)
23 {
24   if(l==r)    //叶子节点，返回
25   {
26     scanf("%d",&sum[rt]); //直接在这里输入建树
27     return;
28   }
29   int m = mid;
30   build(lson);  //递归建左子树
31   build(rson);//递归建右子树
32   PushUp(rt);
33 }
34 //update
35 void update(int p,int add,int l,int r,int rt)
36 {
37     if (l==r)    //节点区间[l,r]被目标区间[L,R]包含
38     {
39         sum[rt] += add;
40         return ;
41     }
42     int m = (l + r) >> 1;
43     if (p<= m)       //左孩子包含有需要的信息
44         update(p , add , lson);
45     else      //右孩子包含有需要的信息
46         update(p , add , rson);
47     PushUp(rt);     //sum[rt] = sum[rt<<1] + sum[rt<<1|1];
48 }
49 
50 int query(int L,int R,int l,int r,int rt)
51 {
52   if (L <= l && r <= R)    //节点区间[l,r]被目标区间[L,R]包含
53   {
54     return sum[rt];
55   }
56   int m = mid;
57   int ret = 0;
58   if (L <= m)       //左孩子包含有需要的信息
59     ret += query(L , R , lson);
60   if (m < R)        //右孩子包含有需要的信息
61     ret += query(L , R , rson);
62   return ret;
63 }
64 
65 int main()
66 {
67     int T,n,set=1;
68     scanf("%d",&T);
69     while(T--)
70     {
71         printf("Case %d:\n",set++);
72         scanf("%d",&n);
73         build(1 , n , 1);
74         char op[10];
75         while(scanf("%s",&op)==1)
76         {
77             if(op[0]=='E')
78                 break;
79             int a,b;
80             scanf("%d%d",&a,&b);
81             if(op[0]=='A')
82                 update(a , b , 1 , n , 1);
83             else if(op[0]=='S')
84                 update(a,-b,1,n,1);
85             else if(op[0]='Q')
86                 printf("%d\n",query(a , b , 1 , n , 1));
87         }
88     }
89     return 0;
90 }

hdu 1754 I hate it（线段树功能:update:单点修改 query:区间最值）

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define ls rt<<1
 9 #define rs rt<<1|1
10 #define lson l,m,ls
11 #define rson m+1,r,rs
12 #define mid (l+r)>>1
13 
14 #define MAXN 200005
15 #define Max(x,y) ((x)>(y)?(x):(y))
16 
17 int MAX[MAXN<<2];    //原数据量扩大4倍用int数组建树
18 
19 void PushUp(int rt)
20 {
21   MAX[rt] = Max(MAX[ls] , MAX[rs]);
22 }
23 
24 void build(int l,int r,int rt)
25 {
26   if(l==r)    //叶子节点，返回
27   {
28     scanf("%d",&MAX[rt]); //直接在这里输入建树
29     return;
30   }
31   int m = mid;
32   build(lson);  //递归建左子树
33   build(rson);//递归建右子树
34   PushUp(rt);
35 }
36 void update(int p,int q,int l,int r,int rt)
37 {
38     if (l==r)    //节点区间[l,r]被目标区间[L,R]包含
39     {
40         MAX[rt]= q;
41         return ;
42     }
43     int m = mid;
44     if (p<= m)       //左孩子包含有需要的信息
45         update(p , q , lson);
46     else      //右孩子包含有需要的信息
47         update(p , q , rson);
48     PushUp(rt);     //sum[rt] = sum[rt<<1] + sum[rt<<1|1];
49 }
50 
51 int query(int L,int R,int l,int r,int rt)
52 {
53   if (L <= l && r <= R)    //节点区间[l,r]被目标区间[L,R]包含
54   {
55     return MAX[rt];
56   }
57   int m = (l + r) >> 1;
58   int ret = 0;
59   if (L <= m)       //左孩子包含有需要的信息
60     ret = max(ret,query(L , R , lson));
61   if (m < R)        //右孩子包含有需要的信息
62     ret = max(ret,query(L , R , rson));
63   return ret;
64 }
65 
66 int main()
67 {
68     int T,n;
69     while(scanf("%d%d",&n,&T)==2)
70     {
71         build(1 , n , 1);
72         char op[10];
73         while(T--)
74         {
75             scanf("%s",&op);
76             int a,b;
77             scanf("%d%d",&a,&b);
78             if(op[0]=='U')
79                 update(a , b , 1 , n , 1);
80             else if(op[0]='Q')
81                 printf("%d\n",query(a , b , 1 , n , 1));
82         }
83     }
84     return 0;
85 }

hdu 1394/zoj 1484 Minimum Inversion Number （线段树功能:update:单点增减 query:区间求和）

题意:给一个长度为n的序列（n<=5000），由0~n-1的数字组成。每次把最左边的数挪到最右边形成一个新的序列。那么一共可以形成n个序列。求这n个序列里面最小的逆序数是多少。

分析：用数组a[0~n-1]来存原始数据。只需求出原始序列的逆序数sum，然后对于a[i](0<= i <n-1)，每挪一个，用sum减去挪之前它右边比它小的数的个数（也就是a[i]）、再用sum加上挪之后左边比它大的数的个数（也就是n-a[i]-1），就是挪了a[i]的逆序数了

ps：求逆序数可以用线段树，树状数组，归并排序等。这题也可以暴力。

View Code

 1 //线段树实现功能：求逆序数
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 #define lson l,m,rt<<1
 9 #define rson m+1,r,rt<<1|1
10 #define MAXN 5005
11 #define MIN(x,y) ((x)>(y)?(y):(x))
12 
13 int sum[MAXN<<2];
14 
15 void PushUp(int rt)
16 {
17     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
18 }
19 
20 void build(int l,int r,int rt)
21 {
22     sum[rt]=0;//sum表示该区间数字出现的个数，
23     if(l==r)
24         return;
25     int m=(r+l)>>1;
26     build(lson);
27     build(rson);
28 }
29 
30 void update(int p,int l,int r,int rt)
31 {
32     if(l==r)
33     {
34         sum[rt]++;
35         return;
36     }
37     int m = (l+r) >> 1;
38     if(p <= m )
39         update(p,lson);
40     else
41         update(p,rson);
42     PushUp(rt);
43 }
44 
45 int query(int L,int R,int l,int r,int rt)
46 {
47     if(L <= l && r <= R)//当前点代表的区间在要查找的区间之内
48         return sum[rt];
49     int m = (l + r) >> 1;
50     int ret = 0;
51     if(L <= m) //左边区间包含有要查询的点
52         ret += query(L, R, lson);
53     if(m < R)    //右边区间包含
54         ret += query(L, R, rson);
55     return ret;
56 }
57 
58 int n,x[MAXN];
59 
60 int main()
61 {
62     int i,j;
63     while(scanf("%d",&n)!=EOF)
64     {
65         build(0,n-1,1);
66         int sum=0;
67         for(i=0;i<n;i++)
68         {
69             scanf("%d",&x[i]);
70             //查询比x[i]大的数出现了多少个。
71             //即x[i]能产生的逆序对的个数
72             sum+=query(x[i],n-1,0,n-1,1);
73             //将x[i]更新入线段树中
74             update(x[i],0,n-1,1);
75         }
76 
77         int ans=sum;
78 
79         //！！对任意一列逆序数，设其中第一个为a
80         //则a之后比a小的数有0,1,...a-1即a个。(ps:因为是连续的前n个数求你逆序对...没看清题意..唉..)
81 //比a大的有(n-x[i]-1)个
82         for(i=0;i<n;i++)
83         {
84             sum = (sum - x[i]) + (n - x[i] -1);
85             ans = MIN(ans,sum);
86         }
87 
88         printf("%d\n",ans);
89     }
90     return 0;
91 }

hdu 2795 Billboard（线段树功能:update:无（包含在query（）里） query:区间最值）

题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子

分析:每次找到最大值的位子,然后减去L

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define ls rt<<1
 9 #define rs rt<<1|1
10 #define lson l,m,rt<<1
11 #define rson m+1,r,rt<<1|1
12 #define mid (l+r)>>1
13 
14 #define MAXN 200005
15 #define Max(x,y) ((x)>(y)?(x):(y))
16 
17 int MAX[MAXN<<2];    //原数据量扩大4倍用int数组建树
18 int h,w,n;
19 void PushUp(int rt)
20 {
21   MAX[rt] = Max(MAX[ls] , MAX[rs]);
22 }
23 void build(int l,int r,int rt)
24 {    
25     MAX[rt]=w; 
26     if(l==r)    //叶子节点，返回
27         return;
28     int m= (l+r)>>1;
29     build(lson);  //递归建左子树
30     build(rson);//递归建右子树
31 }
32 
33 int query(int x,int l,int r,int rt)
34 {
35     if(l==r) 
36     {
37          MAX[rt]-=x;
38          return l;
39     }
40     int m=mid;
41     int ret=0;
42     if(MAX[ls] >= x)       
43         ret= query(x, lson); 
44     else
45         ret= query(x, rson);
46     PushUp(rt);
47     return ret;
48 }
49 int main()
50 {
51     int x;
52     while(scanf("%d%d%d",&h,&w,&n)==3)
53     {
54         if(h>n)
55             h=n;
56         build(1, h, 1);
57         while(n--)
58         {
59             scanf("%d",&x);
60             if(x>MAX[1])
61                 printf("-1\n");
62             else
63                 printf("%d\n",query(x, 1, h, 1));
64         }
65     }
66     return 0;
67 }

poj 2182 hdu 2711 lost cows(线段树功能：update：单点更新区间空位数)

题意：1~n,表示从第二个数开始，这个数前面有多少个比自己小的数。求这个序列。

分析：从后往前插入线段树，线段树维护区间内空位的个数

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define ls rt<<1
 9 #define rs rt<<1|1
10 #define lson l,m,ls
11 #define rson m+1,r,rs
12 #define mid (l+r)>>1
13 
14 #define MAXN 8010
15 
16 int sum[MAXN<<2];
17 int ans[MAXN];
18 int num[MAXN];
19 
20 void build(int l,int r,int rt)
21 {
22     sum[rt]=r-l+1;
23     if(l==r) return;
24     int m=mid;
25     build(lson);
26     build(rson);
27 }
28 
29 void PushUp(int rt)
30 {
31     sum[rt] = sum[ls]+sum[rs];
32 }
33 
34 int k;
35 
36 void update(int p,int l,int r,int rt)
37 {
38     sum[rt]--;
39     if(l==r)
40     {
41         ans[k++]=l;
42         return ;
43     }
44     int m=mid;
45     if(p<=sum[ls])
46     {
47         //sum[rt<<1|1]--;
48         update(p,lson);
49     }
50     else if(p>sum[ls])
51     {
52         p-=sum[ls];
53         update(p,rson);
54     }
55 }
56 
57 
58 int main()
59 {
60     int n;
61     while(scanf("%d",&n) != EOF)
62     {
63         build(1,n,1);
64         for(int i=2;i<=n;i++)
65             scanf("%d",&num[i]);
66         k=0;
67         for(int i=n;i>=2;i--)
68             update(num[i]+1,1,n,1);
69         update(1,1,n,1);
70         for(int i=n-1;i>=0;i--)
71             printf("%d\n",ans[i]);
72     }
73     return 0;
74 }

+++成段操作（lazy_tag：就是每次更新的时候在最上层满足更新条件时就更新，而不继续更新儿子，直到查询到此父亲的时候再更新儿子）

hdu 1698 just a Hook（线段树功能:update:成段替换）

题意：给定一个长度为N(N <= 100000)的数列Si，紧接着Q(1 <= Q <= 100000)条操作，每条操作将[A, B]的区间颜色改成C（权值为C），颜色C最多三种，问最后所有数的权值总和。

分析：线段树的区间修改，还是利用lazy思想。线段树结点维护一个col域和一个sum域，col要么是-1表示当前结点有多种颜色，要么是颜色的编号，每次插入到完全覆盖时在该结点的col域上打上一个标记，表示当前颜色，计算当前结点的sum值。如果当前结点的颜色和插入的颜色相同，说明不必再往下插入了。如果没有完全覆盖，并且当前结点的颜色单一，那么直接将父亲的值传递给而两个儿子，还是同样的道理，之前的儿子如果有lazy标记，肯定是在当前标记之前，所以直接覆盖即可。最后通过两个儿子的权值计算当前子树的权值。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define lson l,m,rt<<1
 9 #define rson m+1,r,rt<<1|1
10 #define MAXN 100010
11 int sum[MAXN<<2];    //区间总的value
12 int col[MAXN<<2];    //lazy_tag 即每次染色后该区间的价值
13 
14 void PushUp(int rt)
15 {
16     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
17 }
18 
19 void PushDown(int rt,int m)//m是父亲区间长度
20 {
21     if(col[rt])//更新孩子
22     {
23         col[rt<<1]=col[rt];
24         col[rt<<1|1]=col[rt];
25         sum[rt<<1]=col[rt] * (m-(m>>1));
26         sum[rt<<1|1]=col[rt] *(m>>1);
27         col[rt]=0;
28     }
29 }
30 
31 void build(int l,int r,int rt)
32 {
33     col[rt]=0;
34       if(l==r)    //叶子节点，返回
35     {
36         sum[rt]=1;
37         return;
38     }
39       int m = (l+r)>>1;
40       build(lson);  //递归建左子树
41       build(rson);//递归建右子树
42       PushUp(rt);
43 }
44 //update
45 void update(int L,int R,int c,int l,int r,int rt)
46 {
47     if (L<= l && r<=R)    //节点区间[l,r]被目标区间[L,R]包含
48     {
49         col[rt]=c;
50         sum[rt]= c*(r-l+1);
51         return ;
52     }
53     PushDown(rt,r-l+1);
54     int m = (l+r)>>1;
55     if(L<=m)
56         update(L,R,c,lson);
57     if(m<R)
58         update(L,R,c,rson);
59     PushUp(rt);
60 }
61 
62 
63 int main()
64 {
65     int t,n,Q,a,b,c,set=1;
66     scanf("%d",&t);
67     while(t--)
68     {
69         scanf("%d",&n);
70         build(1,n,1);
71         scanf("%d",&Q);
72         while(Q--)
73         {
74             scanf("%d%d%d",&a,&b,&c);
75             update(a,b,c,1,n,1);
76         }
77 
78         printf("Case %d: The total value of the hook is %d.\n",set++,sum[1]);
79     }
80     return 0;
81 }

poj 3468 A Simple Problem with Integers(线段树功能：update:成段增减 query:区间求和)

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 
  6 using namespace std;
  7 
  8 #define ls rt<<1
  9 #define rs rt<<1|1
 10 #define lson l,m,rt<<1
 11 #define rson m+1,r,rt<<1|1
 12 #define mid (l+r)>>1
 13 
 14 #define MAXN 100100
 15 long long  sum[MAXN<<2];    //原数据量扩大4倍用int数组建树
 16 long long  add[MAXN<<2];
 17 
 18 void PushUp(int rt)
 19 {
 20     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 21 }
 22 
 23 void PushDown(int rt,int m)//m是父亲区间长度
 24 {
 25     if(add[rt])
 26     {
 27         add[ls]+=add[rt];
 28         add[rs]+=add[rt];
 29         sum[ls]+=add[rt] * (m-(m>>1));
 30         sum[rs]+=add[rt] *(m>>1);
 31         add[rt]=0;
 32     }
 33 }
 34 
 35 void build(int l,int r,int rt)
 36 {
 37     add[rt]=0;
 38       if(l==r)    //叶子节点，返回
 39       {
 40            scanf("%lld",&sum[rt]); //直接在这里输入建树
 41         return;
 42       }
 43       int m = mid;
 44       build(lson);  //递归建左子树
 45       build(rson);//递归建右子树
 46       PushUp(rt);
 47 }
 48 //update
 49 void update(int L,int R,int c,int l,int r,int rt)
 50 {
 51     if (L<= l && r<=R)    //节点区间[l,r]被目标区间[L,R]包含
 52     {
 53         add[rt]+=(long long)c;
 54         sum[rt]+= (long long )c*(r-l+1);
 55         return ;
 56     }
 57     PushDown(rt,r-l+1);
 58     int m = mid;
 59     if(L<=m)
 60         update(L,R,c,lson);
 61     if(m<R)
 62         update(L,R,c,rson);
 63     PushUp(rt);
 64 }
 65 
 66 long long  query(int L,int R,int l,int r,int rt)
 67 {
 68      if (L <= l && r <= R)    //节点区间[l,r]被目标区间[L,R]包含
 69       {
 70             return sum[rt];
 71      }
 72     PushDown(rt,r-l+1);
 73      int m = mid;
 74      long long  ret = 0;
 75      if (L <= m)       //左孩子包含有需要的信息
 76            ret +=query(L , R , lson);
 77       if (m < R)        //右孩子包含有需要的信息
 78            ret +=query(L , R , rson);
 79      return ret;
 80 }
 81 
 82 
 83 int main()
 84 {
 85     int N,Q;
 86     scanf("%d%d",&N,&Q);
 87     build(1,N,1);
 88     int a,b,d;
 89     char c[2];
 90     for(int i=0;i<Q;i++)
 91     {
 92         scanf("%s",&c);
 93         if(c[0]=='Q')
 94         {    
 95             scanf("%d%d",&a,&b);
 96             printf("%lld\n",query(a,b,1,N,1));
 97         }
 98         else
 99         {
100             scanf("%d%d%d",&a,&b,&d);
101             update(a,b,d,1,N,1);
102         }    
103     }
104     return 0;
105 }

poj 2528 Mayor's posters（线段树功能：uodate:成段替换）

++离散化（notonlysuccess说的很详细）

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define ls rt<<1
  9 #define rs rt<<1|1
 10 #define lson l,m,rt<<1
 11 #define rson m+1,r,rt<<1|1
 12 #define mid (l+r)>>1
 13 
 14 #define MAXN 11111
 15 
 16 int col[MAXN<<4];
 17 bool hash[MAXN];
 18 int li[MAXN],ri[MAXN];
 19 int X[MAXN<<3];
 20 int cnt;
 21 
 22 void PushDown(int rt)
 23 {
 24     if(col[rt]!=-1)
 25     {
 26         col[ls] = col[rs] = col[rt];
 27         col[rt] = -1;
 28     }
 29 }
 30 void update(int L,int R,int c,int l,int r,int rt)
 31 {
 32     if(L<=l && r<=R)
 33     {
 34         col[rt]=c;
 35         return;
 36     }
 37     PushDown(rt);
 38     int m=mid;
 39     if(L<=m)
 40         update(L,R,c,lson);
 41     if(m<R)
 42         update(L,R,c,rson);
 43 }
 44 
 45 void query(int l,int r,int rt)
 46 {
 47     if(col[rt] != -1)
 48     {
 49         if(!hash[col[rt]]) cnt++;
 50         hash[col[rt]] = true;
 51         return;
 52     }
 53 
 54     if(l == r) return;
 55     int m = mid;
 56     query(lson);
 57     query(rson);
 58 }
 59 
 60 int Bin(int key,int n,int X[])
 61 {
 62     int l = 0,r = n-1;
 63     while(l<=r)
 64     {
 65         int m = (l+r)>>1;
 66         if(X[m]==key) return m;
 67         if(X[m] < key) 
 68             l=m+1;
 69         else
 70             r=m-1;
 71     }
 72     return -1;
 73 }
 74 
 75 int main()
 76 {
 77     int t,n;
 78     scanf("%d",&t);
 79     while(t--)
 80     {
 81         scanf("%d",&n);
 82         int nn=0;
 83 
 84         for(int i=0;i<n;i++)
 85         {
 86             scanf("%d%d",&li[i],&ri[i]);
 87             X[nn++]=li[i];
 88             X[nn++]=ri[i];
 89         }
 90         sort(X,X+nn);
 91         int m=1;
 92         for(int i=1;i<nn;i++)
 93             if(X[i]!=X[i-1])
 94                 X[m++]=X[i];
 95 
 96         for(int i=m-1;i>0;i--)
 97             if(X[i]!=X[i-1]+1)
 98                 X[m++]=X[i-1]+1;
 99         sort(X,X+m);
100 
101         memset(col,-1,sizeof(col));
102 
103         for(int i=0;i<n;i++)
104         {
105             int l=Bin(li[i],m,X);
106             int r=Bin(ri[i],m,X);
107             update(l,r,i,0,m,1);
108         }
109         cnt=0;
110         memset(hash,false,sizeof(hash));
111         query(0,m,1);
112 
113         printf("%d\n",cnt);
114     }
115     return 0;
116 }

poj 3225 Help with Intervals（线段树功能：update:成段替换,区间异或）

notonlysuccess说的也很详细

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define ls rt<<1
  9 #define rs rt<<1|1
 10 #define lson l,m,rt<<1
 11 #define rson m+1,r,rt<<1|1
 12 #define mid (l+r)>>1
 13 
 14 #define MAXN 140000
 15 bool hash[MAXN+1];
 16 int cover[MAXN<<2];
 17 int XOR[MAXN<<2];
 18 
 19 void FXOR(int rt)
 20 {
 21     if(cover[rt] != -1)//表示这个区间被覆盖
 22         cover[rt] ^= 1;
 23     else
 24         XOR[rt] ^= 1;
 25 }
 26 
 27 void PushDown(int rt)
 28 {
 29     if(cover[rt] != -1)//表示此区间被覆盖，故无论XOR标记是否存在，孩子都被覆盖
 30     {
 31         cover[ls] = cover[rs] = cover[rt];
 32         XOR[ls] = XOR[rs] =0;
 33         cover[rt] = -1;
 34     }
 35 
 36     if(XOR[rt])
 37     {
 38         FXOR(ls);
 39         FXOR(rs);
 40         XOR[rt]=0;
 41     }
 42 }
 43 
 44 void update(char op,int L,int R,int l,int r,int rt)
 45 {
 46     if(L <= l && r <=R)
 47     {
 48         if(op == 'U')
 49         {
 50             cover[rt]=1;
 51             XOR[rt]=0;
 52         }
 53         else if(op=='D')
 54         {
 55             cover[rt]=0;
 56             XOR[rt]=0;
 57         }
 58         else if(op=='C' || op=='S')
 59             FXOR(rt);
 60         return;
 61     }
 62 
 63     PushDown(rt);
 64     int m=mid;
 65     if(L<=m)
 66         update(op,L,R,lson);
 67     else if(op=='I' || op=='C')
 68         XOR[ls]=cover[ls] =0;
 69     if(m<R)
 70         update(op,L,R,rson);
 71     else if(op=='I' || op=='C')
 72         XOR[rs]=cover[rs]=0;
 73 }
 74 
 75 void query(int l,int r,int rt)
 76 {
 77     if(cover[rt]==1)
 78     {
 79         for(int i=l;i<=r;i++)
 80             hash[i]=1;
 81     }
 82     else if(!cover[rt])
 83         return ;
 84     if(l==r) return;
 85     PushDown(rt);
 86     int m=mid;
 87     query(lson);
 88     query(rson);
 89 }
 90 
 91 int main()
 92 {
 93     cover[1]=XOR[1]=0;
 94     char op,l,r;
 95     int a,b;
 96     while(scanf("%c %c%d,%d%c\n",&op,&l,&a,&b,&r)!=EOF)
 97     {
 98         a<<=1,b<<=1;
 99         if(l=='(')a++;
100         if(r==')')b--;
101         if(a>b)//
102         {
103             if(op=='C' || op=='I')
104                 cover[1]=XOR[1]=0;
105         }
106         else
107             update(op,a,b,0,MAXN,1);
108     }
109     query(0,MAXN,1);
110     bool flag =0;
111     int s=-1,e;
112     for(int i=0;i<=MAXN;i++)
113     {
114         if(hash[i])
115         {
116             if(s==-1)
117                 s=i;
118             e=i;
119         }
120         else
121         {
122             if(s != -1)
123             {
124                 if(flag)
125                     printf(" ");
126                 flag=true;
127                 printf("%c%d,%d%c",s&1?'(':'[',s>>1,(e+1)>>1,e&1?')':']');
128                 s=-1;
129             }
130         }
131     }
132     if(!flag)printf("empty set");
133     puts("");
134     return 0;
135 }

poj 1436 Horizontally Visible Segments(++++)

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 #define ls rt<<1
 11 #define rs rt<<1|1
 12 #define lson l,m,rt<<1
 13 #define rson m+1,r,rt<<1|1
 14 #define mid (l+r)>>1
 15 
 16 #define MAXN 8010
 17 
 18 int cover[MAXN<<4];
 19 int hash[MAXN<<1];
 20 vector<int> V[MAXN<<1];
 21 
 22 struct v_seg
 23 {
 24     int s,t;
 25     int x;
 26 }ss[MAXN];
 27 
 28 int cmp(v_seg a,v_seg b)
 29 {
 30     return a.x<b.x;
 31 }
 32 
 33 void PushDown(int rt)
 34 {
 35     if(cover[rt] != -1)
 36     {
 37         cover[ls]=cover[rs]=cover[rt];
 38         cover[rt] = -1;
 39     }
 40 }
 41 
 42 void update(int L,int R,int id,int l,int r,int rt)
 43 {
 44     if(L<=l && r<=R)
 45     {
 46         cover[rt]=id;
 47         return;
 48     }
 49     PushDown(rt);
 50     int m=mid;
 51     if(L<=m)
 52         update(L,R,id,lson);
 53     if(R>m)
 54         update(L,R,id,rson);
 55 }
 56 
 57 void query(int L,int R,int id,int l,int r,int rt)
 58 {
 59     if(cover[rt] != -1)
 60     {
 61         if(hash[cover[rt]] != id)
 62         {
 63             hash[cover[rt]]=id;
 64             V[cover[rt]].push_back(id);
 65         }
 66         return;
 67     }
 68     if(l==r) return;
 69     PushDown(rt);
 70     int m=mid;
 71     if(L<=m)
 72         query(L,R,id,lson);
 73     if(R>m)
 74         query(L,R,id,rson);
 75 }
 76 
 77 
 78 int main()
 79 {
 80     int t,n;
 81     scanf("%d",&t);
 82     while(t--)
 83     {
 84         scanf("%d",&n);
 85         memset(cover,-1,sizeof(cover));
 86         memset(hash,-1,sizeof(hash));
 87         for(int i=0;i<n;i++)
 88         {
 89             scanf("%d%d%d",&ss[i].s,&ss[i].t,&ss[i].x);
 90             ss[i].s<<=1;ss[i].t<<=1;V[i].clear();
 91         }
 92 
 93         sort(ss,ss+n,cmp);
 94 
 95         for(int i=0;i<n;i++)
 96         {
 97             query(ss[i].s,ss[i].t,i,0,MAXN<<1,1);
 98             update(ss[i].s,ss[i].t,i,0,MAXN<<1,1);
 99         }
100         int ans=0;
101         for(int i=0;i<n;i++)
102         {
103             for(int j=0;j<V[i].size();j++)
104             {
105                 int k=V[i][j];
106                 for(int p=0;p<V[i].size();p++)
107                     for(int q=0;q<V[k].size();q++)
108                         if(V[i][p] == V[k][q])
109                             ans++;
110             }
111         }
112 
113         printf("%d\n",ans);
114     }
115     return 0;
116 }

poj 1151(线段树+扫描线+离散化)

题意：给你n个矩形的坐标求矩形覆盖的总面积

浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个,sum代表该区间内被覆盖的线段的长度总和
这里线段树的一个结点并非是线段的一个端点,而是该端点和下一个端点间的线段

View Code

  1 //poj 1151 hdu 1542
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 #define ls rt<<1
 12 #define rs rt<<1|1
 13 
 14 #define MAXN 220
 15 
 16 struct seg
 17 {
 18     double l,r,h;//l代表线段的左端点,r是右端点,h是该线段高，即y值
 19     int s;//s==1表示是矩形下边，s==-1是上边
 20     seg(){}
 21     seg(double a,double b,double c,int d):l(a),r(b),h(c),s(d){}
 22     bool operator < (const seg & a)const
 23     {
 24         return h<a.h;
 25     }
 26 }ss[MAXN];
 27 double X[MAXN],sum[MAXN<<2];
 28 int cnt[MAXN<<2];
 29 
 30 void PushUp(int rt,int l,int r)
 31 {
 32     if(cnt[rt])
 33         sum[rt]=X[r+1]-X[l];
 34     else if(l==r)
 35         sum[rt]=0;
 36     else
 37         sum[rt]=sum[ls]+sum[rs];
 38 }
 39 
 40 void update(int L,int R,int c,int l,int r,int rt)
 41 {
 42     if(L<=l && r<=R)
 43     {
 44         cnt[rt]+=c;
 45         PushUp(rt,l,r);
 46         return;
 47     }
 48 
 49     int m=(l+r)>>1;
 50     if(L<=m)
 51         update(L,R,c,lson);
 52     if(m<R)
 53         update(L,R,c,rson);
 54     PushUp(rt,l,r);
 55 }
 56 
 57 int Bin(double key,int n,double X[])
 58 {
 59     int l=0,r=n-1;
 60     while(l<=r)
 61     {
 62         int m=(l+r)>>1;
 63         if(X[m] == key ) return m;
 64         else if(X[m] <key)
 65             l=m+1;
 66         else
 67             r=m-1;
 68     }
 69     return -1;
 70 }
 71 
 72 int main()
 73 {
 74     int n;
 75     int set=1;
 76     while(scanf("%d",&n) && n)
 77     {
 78         double x1,x2,y1,y2;
 79         int m=0;
 80         for(int i=0;i<n;i++)
 81         {
 82             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 83             X[m]=x1;
 84             ss[m++]=seg(x1,x2,y1,1);
 85             X[m]=x2;
 86             ss[m++]=seg(x1,x2,y2,-1);
 87         }
 88 
 89         sort(X,X+m);
 90         sort(ss,ss+m);
 91         
 92         int k=1;
 93         for(int i=1;i<m;i++)
 94             if(X[i] != X[i-1])
 95                 X[k++]=X[i];
 96         memset(cnt,0,sizeof(cnt));
 97         memset(sum,0,sizeof(sum));
 98         double ans=0;
 99 
100         for(int i=0;i<m-1;i++)
101         {
102             int l=Bin(ss[i].l,k,X);
103             int r=Bin(ss[i].r,k,X)-1;
104 
105             if(l<=r)
106                 update(l,r,ss[i].s,0,k-1,1);
107             ans+=sum[1]*(ss[i+1].h-ss[i].h);
108         }
109 
110  
111         printf("Test case #%d\nTotal explored area: %.2lf\n\n",set++,ans);
112     }
113     return 0;
114 }