poj 线段树

应该说是线段树里面的最裸的那种了吧。题意：给你一段线段，分成单位长度，开始时每段的颜色都为 1 ，然后两种操作，一种：C A B K，是从A 开始到 B 这段距离用 K 来染色。另一种 P A B，询问从A 到 B一共有多少种颜色。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <queue>
  5 #include <stack>
  6 #include <algorithm>
  7 #include <math.h>
  8 #define N 100010
  9 #define M 10
 10 #define _clr(a,val) (memset(a,val,sizeof(a)))
 11 
 12 using namespace std;
 13 
 14 int n,num,sum;
 15 int mark[40];
 16 int ans;
 17 struct node
 18 {
 19     int l;
 20     int r;
 21     int c;
 22 }le[N * 3];
 23 void build(int s,int e,int d)
 24 {
 25     le[d].l = s;
 26     le[d].r = e;
 27     if(s == e) return ;
 28     int mid = (s + e) / 2;
 29     build(s,mid,d * 2);
 30     build(mid + 1,e,d * 2 + 1);
 31 }
 32 void insert(int s,int e,int d,int co)
 33 {
 34     if(le[d].l == s && le[d].r == e)
 35     {
 36         le[d].c = co;
 37     }
 38     else
 39     {
 40         int mid = (le[d].r + le[d].l) / 2;
 41         if(le[d].c > 0){le[d * 2].c = le[d * 2 + 1].c = le[d].c; le[d].c = -1;}
 42         if(e <= mid) insert(s,e,d * 2,co);
 43         else if(s > mid) insert(s,e,d * 2 + 1,co);
 44         else
 45         {
 46             insert(s, mid, d * 2, co);
 47             insert(mid + 1, e, d * 2 + 1,co);
 48         }
 49     }
 50 }
 51 void countree(int s,int e,int d)
 52 {
 53     if(le[d].c > 0)
 54     {
 55         mark[le[d].c] = 1;
 56     }
 57     else
 58     {
 59         int mid = (le[d].l + le[d].r) / 2;
 60         if(e <= mid) countree(s,e,d * 2);
 61         else if(s > mid) countree(s,e,d * 2 + 1);
 62         else
 63         {
 64             countree(s,mid,d * 2);
 65             countree(mid + 1, e,d * 2 + 1);
 66         }
 67     }
 68 }
 69 int main()
 70 {
 71     int i,j;
 72     char ch;
 73     int x,y,z;
 74     //freopen("data.txt","r",stdin);
 75     while(scanf("%d%d%d",&n,&num,&sum) != EOF)
 76     {
 77         //getchar();
 78         build(1,n,1);
 79         le[1].c = 1;
 80         while(sum--)
 81         {
 82             getchar();
 83             scanf("%c",&ch);
 84             if(ch == 'C')
 85             {
 86                 scanf("%d%d%d",&x,&y,&z);
 87                 if(x > y)
 88                 {
 89                     int tem = x;
 90                     x = y;
 91                     y = tem;
 92                 }
 93                 insert(x,y,1,z);
 94             }
 95             else if(ch == 'P')
 96             {
 97                 scanf("%d%d",&x,&y);
 98                 if(x > y)
 99                 {
100                     int tem = x;
101                     x = y;
102                     y = tem;
103                 }
104                 _clr(mark,0);
105                 ans = 0;
106                 countree(x,y,1);
107                 for(i = 1; i <= num; i++)
108                 {
109                     if(mark[i])
110                     {
111                         ans++;
112                     }
113                 }
114 
115                 printf("%d\n",ans);
116             }
117         }
118     }
119     return 0;
120 }

题目：http://poj.org/problem?id=2528

题意：给出一段距离，然后给你n行数，每行是从 A 到 B 这段距离涂抹一种颜色，问到最后，这段距离可以看见多少种不同的颜色。

思路：其实题目倒也不难，就是题目给的数据需要离散化处理一下。把输入的点离散化后，建树，插入，询问

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define N  20010
  6 #define _clr(a,val) (memset(a,val,sizeof(a)))
  7 
  8 using namespace std;
  9 
 10 struct tree
 11 {
 12     int l;
 13     int r;
 14     int c;
 15 }tr[N * 4];
 16 struct node
 17 {
 18     int num;
 19     int il;
 20     int ind;
 21 }map[N * 2];
 22 int temp[N * 2][2];
 23 int mark[N];
 24 int cnt;
 25 int cmp(node a,node b)
 26 {
 27     return a.num < b.num;
 28 }
 29 void build(int s,int e,int d)
 30 {
 31     tr[d].l = s;
 32     tr[d].r = e;
 33     tr[d].c = -1;
 34     if(s == e) return ;
 35     int mid = (s + e) / 2;
 36     build(s, mid, d * 2);
 37     build(mid + 1, e, d * 2 + 1);
 38 }
 39 void insert(int s,int e,int d,int co)
 40 {
 41     if(tr[d].l == s && tr[d].r == e)
 42     {
 43         tr[d].c = co;return;
 44     }
 45     if(tr[d].c > 0) {tr[d * 2].c = tr[d * 2 + 1].c = tr[d].c;tr[d].c = -1;}
 46     int mid = (tr[d].l + tr[d].r) / 2;
 47     if(e <= mid) insert(s,e,d * 2,co);
 48     else if(s > mid) insert(s,e,d * 2 + 1,co);
 49     else
 50     {
 51         insert(s,mid,d * 2,co);
 52         insert(mid + 1,e,d * 2 + 1,co);
 53     }
 54 }
 55 void countree(int d)
 56 {
 57     if(tr[d].c != -1)
 58     {
 59         if( !mark[tr[d].c] )
 60         {
 61             mark[tr[d].c] = 1;
 62             cnt++;
 63         }
 64         return ;
 65     }
 66     countree(d * 2);
 67     countree(d * 2 + 1);
 68 }
 69 int main()
 70 {
 71     int i;
 72     int t,n;
 73     //freopen("data.txt","r",stdin);
 74     scanf("%d",&t);
 75     while(t--)
 76     {
 77         _clr(map,0);
 78         scanf("%d",&n);
 79         int tnum = 0;
 80         for(i = 0; i < n; i++)
 81         {
 82             scanf("%d%d",&temp[i][0],&temp[i][1]);
 83             map[tnum].num = temp[i][0];
 84             map[tnum].il = 1;
 85             map[tnum].ind = i;
 86             tnum++;
 87 
 88             map[tnum].num = temp[i][1];
 89             map[tnum].il = 0;
 90             map[tnum].ind = i;
 91             tnum ++;
 92         }
 93         sort(map,map + tnum,cmp);
 94         int tem = -1;
 95         int indx = 0;
 96         for(i = 0; i < tnum; i++)  // 离散化点
 97         {
 98             if(map[i].num != tem)
 99             {
100                 indx ++;
101                 tem = map[i].num;
102             }
103             if(map[i].il)
104             temp[map[i].ind][0] = indx;
105             else
106             temp[map[i].ind][1] = indx;
107         }
108         build(1,indx,1);
109         for(i = 0; i < n; i++)
110         {
111             insert(temp[i][0],temp[i][1],1,i + 1);
112         }
113         _clr(mark,0);
114         cnt = 0;
115         countree(1);
116         cout<<cnt<<endl;
117     }
118     return 0;
119 }

题目：http://poj.org/problem?id=2828

题意：一队人买票，给出第 i 个人站在 a 的后面，拥有的价值量为 b ，给出n行数据，问最后这些人的价值量顺序

思路：要说用线段树那段倒不难，关键是想出这个要倒着往线段树里插数据，因为不管这些人怎么站，最后一个人的位置是固定，然后推出倒数第二个人，依次往前推，所以要倒这插入数据

View Code

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #define N 200010
 6 #define _clr(a,val) (memset(a,val,sizeof(a)))
 7 
 8 using namespace std;
 9 
10 struct node
11 {
12     int l;
13     int r;
14     int num;
15 }tr[N * 4];
16 int mark[N];
17 int val[N],pla[N];
18 void build(int s,int e,int d)
19 {
20     tr[d].l = s;
21     tr[d].r = e;
22     tr[d].num = (e - s + 1);  // 此区间站的人数
23     if(s == e) return;
24     int mid = (s + e) / 2;
25     build(s, mid, d * 2);
26     build(mid + 1, e, d * 2 + 1);
27 }
28 void insert(int d,int i)
29 {
30     tr[d].num--;  
31     if(tr[d].l == tr[d].r)
32     mark[tr[d].l] = val[i];
33     else
34     {
35         if(tr[d * 2].num > pla[i])  // 左边站的人数足够，去左孩子查找
36         insert(d * 2,i);
37         else   // 否则去右孩子查找
38         {
39             pla[i] -= tr[d * 2].num;  // 去掉左孩子上的人数
40             insert(d * 2 + 1,i);
41         }
42     }
43 }
44 int main()
45 {
46     int i,n;
47     //freopen("data.txt","r",stdin);
48     while(scanf("%d",&n) != EOF)
49     {
50         _clr(val,0);
51         _clr(pla,0);
52         _clr(mark,0);
53         for(i = 1; i <= n; i++)
54         scanf("%d%d",&pla[i],&val[i]);
55         build(1,n,1);
56         for(i = n; i >= 1; i--)
57         {
58             insert(1,i);
59         }
60         for(i = 1;i < n; i++)
61         printf("%d ",mark[i]);
62         printf("%d\n",mark[n]);
63     }
64     return 0;
65 }