【ACM/ICPC2013】线段树题目集合（一）

前言：前一段时间在网上找了一个线段树题目列表，我顺着做了一些，今天我把做过的整理一下。感觉自己对线段树了解的还不是很深，自己的算法能力还要加强。光练代码能力还是不够的，要多思考。向队友学习，向大牛学习。

ZOJ1610

题目大意：先后对线段涂色，最后统计每种颜色出现的段数，为0则不输出。

分析：以点建树，每个节点有一个标记col，初始为-1，表示未涂过色。涂色时，若完全覆盖，则col为颜色编号，若覆盖一部分，则先将标记下放到左右儿子节点，再将标号标记为-2，表示此节点被部分覆盖过。最后从根节点开始往下遍历，若遇到节点col>-1的，直接将区间l到r标记为true，若col为-1，则返回，若为-2，则分别到左右儿子遍历。

参考代码：

 1 //
 2 //  ZOJ1610.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-11.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 
15 const int maxn = 8000 + 10;
16 
17 struct node
18 {
19     int l,r,col;
20 }tree[maxn<<2];
21 
22 int n,le,ri,c,tmp,mark[maxn],color[maxn];
23 
24 void buildtree(int root,int l,int r)
25 {
26     tree[root].l = l;
27     tree[root].r = r;
28     tree[root].col = -1;
29     if (l < r)
30     {
31         buildtree(root<<1, l, (l+r)/2);
32         buildtree(root<<1|1, (l+r)/2+1, r);
33     }
34 }
35 
36 void update(int root,int l,int r,int c)
37 {
38     if (l <= tree[root].l && tree[root].r <= r)
39     {
40         tree[root].col = c;
41         return;
42     }
43     int mid = (tree[root].l+tree[root].r)/2;
44     if (tree[root].col > -2)
45     {
46         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
47         tree[root].col = -2;
48     }
49     if (l <= mid) update(root<<1, l, r, c);
50     if (mid < r) update(root<<1|1, l, r, c);
51 }
52 
53 void cnt(int root)
54 {
55     if (tree[root].col > -1)
56     {
57         for (int i = tree[root].l;i <= tree[root].r;i++)
58             mark[i] = tree[root].col;
59         return;
60     }
61     if (tree[root].col == -2)
62     {
63         cnt(root<<1);
64         cnt(root<<1|1);
65     }
66 }
67 
68 int main()
69 {
70     while (scanf("%d",&n)!=EOF)
71     {
72         buildtree(1,0,8000);
73         memset(mark,-1,sizeof(mark));
74         memset(color,0,sizeof(color));
75         while (n--)
76         {
77             scanf("%d%d%d",&le,&ri,&c);
78             update(1,le+1,ri,c);
79         }
80         cnt(1);
81         tmp = -1;
82         for (int i = 0;i <= 8000;i++)
83         {
84             if (tmp == mark[i]) continue;
85             tmp = mark[i];
86             if (tmp != -1) color[tmp]++;
87         }
88         for (int i = 0;i <= 8000;i++)
89             if (color[i])
90                 printf("%d %d
",i,color[i]);
91         printf("
");
92     }
93 }

View Code

POJ2777

题目大意：给两种操作，一种是对区间[a,b]涂色成c，一种是询问区间[a,b]之间不同颜色个数，在线的。由于给的区间直接是线段编号，所以以点建树，每个节点有一个标记col，初始都为颜色1。涂色时，若完全覆盖，则col为颜色编号，若覆盖一部分，则先将标记下放左右儿子，再将标号标记为-1，表示此节点被部分覆盖过。

查询时，

1、若给定区间覆盖当前节点区间，分两种情况：

1）当前区间col>0，则将col标为true；

2）当前区间col＝-1，则分别到左右儿子遍历；

2、若给定区间覆盖当前节点的部分区间，需要遍历左右儿子，那么如果当前区间col>0，需要将col标记下放到左右儿子，再对左右儿子进行查询。

参考代码：

  1 //
  2 //  POJ2777.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-12.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <string>
 13 #include <algorithm>
 14 
 15 using namespace std;
 16 
 17 const int maxn = 100000 + 10,maxt = 30 + 10;
 18 
 19 struct node
 20 {
 21     int l,r,col;
 22 }tree[maxn<<2];
 23 
 24 int n,t,m,le,ri,c,ans;
 25 char ch;
 26 bool vis[maxt];
 27 
 28 void buildtree(int root,int l,int r)
 29 {
 30     tree[root].l = l;
 31     tree[root].r = r;
 32     tree[root].col = 1;
 33     if (l < r)
 34     {
 35         buildtree(root<<1, l, (l+r)/2);
 36         buildtree(root<<1|1, (l+r)/2+1, r);
 37     }
 38 }
 39 
 40 void update(int root,int l,int r,int c)
 41 {
 42     if (l <= tree[root].l && tree[root].r <= r)
 43     {
 44         tree[root].col = c;
 45         return;
 46     }
 47     if (tree[root].col > 0)
 48     {
 49         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
 50         tree[root].col = -1;
 51     }
 52     int mid = (tree[root].l+tree[root].r)/2;
 53     if (l <= mid) update(root<<1, l, r, c);
 54     if (mid < r) update(root<<1|1, l, r, c);
 55 }
 56 
 57 void cnt(int root,int l,int r)
 58 {
 59     if (l <= tree[root].l && tree[root].r <= r)
 60     {
 61         if (tree[root].col > 0)
 62             vis[tree[root].col] = true;
 63         else
 64         {
 65             cnt(root<<1,l,r);
 66             cnt(root<<1|1,l,r);
 67         }
 68         return;
 69     }
 70     if (tree[root].col > 0)
 71         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
 72     
 73     int mid = (tree[root].l+tree[root].r)/2;
 74     if (l <= mid) cnt(root<<1,l,r);
 75     if (mid < r) cnt(root<<1|1,l,r);
 76 }
 77 
 78 int main()
 79 {
 80     scanf("%d%d%d",&n,&t,&m);
 81     buildtree(1,1,n);
 82     while (m--)
 83     {   
 84         scanf("%c%c",&ch,&ch);
 85         if (ch == 'C')
 86         {
 87             scanf("%d%d%d",&le,&ri,&c);
 88             if (le > ri) swap(le,ri);       
 89             update(1,le,ri,c);
 90         }
 91         else
 92         {
 93             scanf("%d%d",&le,&ri);
 94             if (le > ri) swap(le,ri);
 95             memset(vis,false,sizeof(vis));
 96             cnt(1,le,ri);                  
 97             ans = 0;
 98             for (int i = 1;i <= t;i++)
 99                 ans+=vis[i];
100             printf("%d
",ans);
101         }
102     }
103 }

View Code

HDU1754

题目大意：两种操作，一个是把编号为a的点的值改为b，一个是询问[a,b]中最大值是多少。

分析：这题比较简单，以点建树，建树过程中建到叶子节点时读入每个点的初始值。更新时，若当前节点是叶子节点，直接更新，若是内部节点，则先递归更新，再用左右儿子的值来更新自己。

参考代码：

 1 //
 2 //  HDU1754.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-12.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 
15 using namespace std;
16 
17 const int maxn = 200000 + 10;
18 
19 struct node
20 {
21     int l,r,maxs;
22 }tree[maxn<<2];
23 
24 int n,m,le,ri;
25 char ch;
26 
27 void buildtree(int root,int l,int r)
28 {
29     tree[root].l = l;
30     tree[root].r = r;
31     if (l == r)
32         scanf("%d",&tree[root].maxs);
33     else
34     {
35         buildtree(root<<1, l, (l+r)/2);
36         buildtree(root<<1|1, (l+r)/2+1, r);
37         tree[root].maxs = max(tree[root<<1].maxs,tree[root<<1|1].maxs);
38     }
39 }
40 
41 void update(int root,int pos,int c)
42 {
43     if (tree[root].l == tree[root].r)
44     {
45         tree[root].maxs = c;
46         return;
47     }
48     int mid = (tree[root].l+tree[root].r)/2;
49     if (pos <= mid) update(root<<1, pos, c);
50     else update(root<<1|1, pos, c);
51     tree[root].maxs = max(tree[root<<1].maxs,tree[root<<1|1].maxs);
52 }
53 
54 int getmax(int root,int l,int r)
55 {
56     if (l <= tree[root].l && tree[root].r <= r)
57         return tree[root].maxs;
58     int ans = 0,mid = (tree[root].l+tree[root].r)/2;
59     if (l <= mid) ans = max(ans,getmax(root<<1,l,r));
60     if (mid < r) ans = max(ans,getmax(root<<1|1,l,r));
61     return ans;
62 }
63 
64 int main()
65 {
66     while (scanf("%d%d",&n,&m)!=EOF)
67     {
68         buildtree(1,1,n);
69         while (m--)
70         {
71             scanf("%c%c%d%d",&ch,&ch,&le,&ri);
72             if (ch == 'Q')
73                 printf("%d
",getmax(1,le,ri));
74             else
75                 update(1,le,ri);
76         }
77     }
78 }

View Code

HDU1166

题目大意：和上一题类似，本题有三种操作，将编号a的值加b，将编号a的值减b（即加上-b），询问[a,b]和。

分析：以点建树，建树过程中遇到叶子节点读入初始值。更新时，首先将节点sum值加上b，若当前为叶子节点则返回，若为内部节点，则更新对应的左右儿子。询问时，若区间包含当前节点，则返回当前节点sum值，否则返回左儿子sum值＋右儿子sum值。

参考代码：

 1 //
 2 //  HDU1166.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-12.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 
15 using namespace std;
16 
17 const int maxn = 50000 + 10;
18 
19 struct node
20 {
21     int l,r,mid,sum;
22 }tree[maxn << 2];
23 
24 int t,n,le,ri;
25 char st[10];
26 
27 void buildtree(int root,int l,int r)
28 {
29     tree[root].l = l;
30     tree[root].r = r;
31     tree[root].mid = (l+r)/2;
32     if (l == r)
33     {
34         scanf("%d",&tree[root].sum);
35         return;
36     }
37     buildtree(root<<1, l, (l+r)/2);
38     buildtree(root<<1|1, (l+r)/2+1, r);
39     tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
40 }
41 
42 void update(int root,int p,int c)
43 {
44     tree[root].sum+=c;
45     if (tree[root].l == tree[root].r)
46         return;
47     if (p <= tree[root].mid) update(root<<1,p,c);
48     else update(root<<1|1,p,c);
49 }
50 
51 int getsum(int root,int l,int r)
52 {
53     if (l <= tree[root].l && tree[root].r <= r)
54         return tree[root].sum;
55     int ans = 0;
56     if (l <= tree[root].mid) ans += getsum(root<<1,l,r);
57     if (tree[root].mid < r) ans += getsum(root<<1|1,l,r);
58     return ans;
59 }
60 
61 int main()
62 {
63     scanf("%d",&t);
64     for (int o = 1;o <= t;o++)
65     {
66         printf("Case %d:
",o);
67         scanf("%d",&n);
68         if (n == 0) continue;
69         buildtree(1,1,n);
70         while (scanf("%s",st)!=EOF)
71         {
72             if (st[0] == 'E') break;
73             scanf("%d%d",&le,&ri);
74             if (st[0] == 'A')
75                 update(1,le,ri);
76             if (st[0] == 'S')
77                 update(1,le,-ri);
78             if (st[0] == 'Q')
79                 printf("%d
",getsum(1,le,ri));
80         }
81     }
82 }

View Code

HDU1698

题目大意：给定线段，初始值都为1，给定操作a,b,c，将[a,b]的值修改为c，c为1，2或3，最后询问线段所有数的和

分析：以点建树，初始标记col为1，更新时，若区间覆盖当前节点，则更新col为c，否则先将当前col下放到左右儿子，再标记为-1，表示当前节点被不止一种值覆盖。计算时，若当前节点col>0，则返回col＊节点区间长度，否则返回左儿子值＋右儿子值。

参考代码：

 1 //
 2 //  HDU1698.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-12.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 
15 using namespace std;
16 
17 const int maxn = 100000;
18 
19 struct node
20 {
21     int l,r,len,mid,col;
22 }tree[maxn << 2];
23 
24 int t,n,m,le,ri,c;
25 
26 void buildtree(int root,int l,int r)
27 {
28     tree[root].l = l;
29     tree[root].r = r;
30     tree[root].len = r-l+1;
31     tree[root].mid = (l+r)/2;
32     tree[root].col = 1;
33     if (l < r)
34     {
35         buildtree(root<<1,l,(l+r)/2);
36         buildtree(root<<1|1, (l+r)/2+1, r);
37     }
38 }
39 
40 void update(int root,int l,int r,int c)
41 {
42     if (l <= tree[root].l && tree[root].r <= r)
43     {
44         tree[root].col = c;
45         return;
46     }
47     if (tree[root].col > 0)
48     {
49         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
50         tree[root].col = -1;
51     }
52     if (l <= tree[root].mid) update(root<<1,l,r,c);
53     if (tree[root].mid < r) update(root<<1|1, l, r, c);
54 }
55 
56 int getsum(int root)
57 {
58     if (tree[root].col > 0)
59         return tree[root].col * tree[root].len;
60     int ans = 0;
61     ans += getsum(root<<1);
62     ans += getsum(root<<1|1);
63     return ans;
64 }
65 
66 int main()
67 {
68     scanf("%d",&t);
69     for (int o = 1;o <= t;o++)
70     {
71         scanf("%d%d",&n,&m);
72         buildtree(1,1,n);
73         while (m--)
74         {
75             scanf("%d%d%d",&le,&ri,&c);
76             update(1,le,ri,c);
77         }
78         printf("Case %d: The total value of the hook is %d.
",o,getsum(1));
79     }
80 }

View Code

POJ3468

题目大意：给一列数，两种操作，一种是将[a,b]每个值加上c，另一种是询问[a,b]和。

分析：经典的区间修改区间询问题。以点建树，维护两个标记，add和sum，分别记录当前节点累加过的值和当前节点覆盖区间的值的和。更新时，若区间覆盖当前节点，则更新add和sum，否则，先用当前节点add值更新左右儿子的add和sum，再分别对左右儿子更新，更新完后再将当前节点sum值更新为左右儿子sum值之和。

参考代码：

  1 //
  2 //  POJ3468.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-12.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <string>
 12 #include <cstring>
 13 #include <algorithm>
 14 
 15 using namespace std;
 16 
 17 const int maxn = 100000 + 10;
 18 
 19 struct node
 20 {
 21     int l,r,mid;
 22     long long len,add,sum;
 23 }tree[maxn<<2];
 24 
 25 int n,m,le,ri,c;
 26 char ch;
 27 
 28 void buildtree(int root,int l,int r)
 29 {
 30     tree[root].l = l;
 31     tree[root].r = r;
 32     tree[root].mid = (l+r)/2;
 33     tree[root].add = 0;
 34     tree[root].len = r-l+1;
 35     if (l == r)
 36     {
 37         scanf("%lld",&tree[root].sum);
 38         return;
 39     }
 40     buildtree(root<<1,l,(l+r)/2);
 41     buildtree(root<<1|1,(l+r)/2+1,r);
 42     tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
 43 }
 44 
 45 void update(int root,int l,int r,int c)
 46 {
 47     if (l <= tree[root].l && tree[root].r <= r)
 48     {
 49         tree[root].add += c;
 50         tree[root].sum += c*tree[root].len;
 51         return;
 52     }
 53     if (tree[root].add!=0)
 54     {
 55         tree[root<<1].add += tree[root].add;
 56         tree[root<<1].sum += tree[root].add*tree[root<<1].len;
 57         tree[root<<1|1].add += tree[root].add;
 58         tree[root<<1|1].sum += tree[root].add*tree[root<<1|1].len;
 59         tree[root].add = 0;
 60     }
 61     if (l <= tree[root].mid) update(root<<1,l,r,c);
 62     if (tree[root].mid < r) update(root<<1|1,l,r,c);
 63     tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
 64 }
 65 
 66 long long getsum(int root,int l,int r)
 67 {
 68     if (l <= tree[root].l && tree[root].r <= r)
 69         return tree[root].sum;
 70     if (tree[root].add!=0)
 71     {
 72         tree[root<<1].add += tree[root].add;
 73         tree[root<<1].sum += tree[root].add*tree[root<<1].len;
 74         tree[root<<1|1].add += tree[root].add;
 75         tree[root<<1|1].sum += tree[root].add*tree[root<<1|1].len;
 76         tree[root].add = 0;
 77     }
 78     long long ans = 0;
 79     if (l <= tree[root].mid) ans += getsum(root<<1,l,r);
 80     if (tree[root].mid < r) ans += getsum(root<<1|1,l,r);
 81     tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
 82     return ans;
 83 }
 84 
 85 int main()
 86 {
 87     scanf("%d%d",&n,&m);
 88     buildtree(1,1,n);
 89     while (m--)
 90     {
 91         scanf("%c%c%d%d",&ch,&ch,&le,&ri);
 92         if (ch == 'Q')
 93             printf("%lld
",getsum(1,le,ri));
 94         else
 95         {
 96             scanf("%d",&c);
 97             update(1,le,ri,c);
 98         }
 99     }
100 }

View Code

Ural 1019

题目大意：给一条线段，初始为白色，之后给一系列操作，将[a,b]涂为黑色或白色，最后统计出白色最长的一段，输出左右区间。

分析：由于区间特别大，所以先离散化。注意题目给的区间都是点，而涂的颜色是线段。所以不能以点建树，而是以区间建树，元区间为[a,a+1)。

整个线段初始为白色，所以在所有操作前加一条将整个区间涂为白色的操作。更新时，若区间覆盖当前节点区间，则更新col（白色为1，黑色为-1，被多种覆盖为0），否则将col下放到左右儿子，当前col更新为0，再更新左右儿子。查询时，若当前节点col为1，则将当前节点区间[l,r-1]改为true，为什么是r-1呢？因为我们要计算的是线段，也避免了原本不相邻离散化后相邻的情况出现。最后统计最长的为true的区间。

参考代码：

  1 //
  2 //  Ural1019.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-13.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <string>
 13 #include <algorithm>
 14 
 15 using namespace std;
 16 
 17 const int maxn = 10000 + 20,MAXX = 1000000000;
 18 
 19 struct node
 20 {
 21     int l,r,col;
 22 }tree[maxn<<2],data[maxn];
 23 
 24 struct node2
 25 {
 26     int p,num;
 27 }line[maxn<<1];
 28 
 29 int n,x,y,seg[maxn][3],cnt[maxn],top,tmp,ans,ansx,ansy;
 30 bool flag[maxn];
 31 char ch;
 32 
 33 bool cmp(const node2&p1,const node2&p2)
 34 {
 35     return p1.p < p2.p;
 36 }
 37 
 38 void buildtree(int root,int l,int r)
 39 {
 40     tree[root].l = l;
 41     tree[root].r = r;
 42     tree[root].col = 0;
 43     if (l+1<r)
 44     {
 45         buildtree(root<<1,l,(l+r)/2);
 46         buildtree(root<<1|1,(l+r)/2,r);
 47     }
 48 }
 49 
 50 void update(int root,int l,int r,int c)
 51 {
 52     if (l <= tree[root].l && tree[root].r <= r)
 53     {
 54         tree[root].col = c;
 55         return;
 56     }
 57     if (tree[root].col!=0)
 58     {
 59         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
 60         tree[root].col = 0;
 61     }
 62     int mid = (tree[root].l+tree[root].r)/2;
 63     if (l < mid) update(root<<1,l,r,c);
 64     if (mid < r) update(root<<1|1,l,r,c);
 65 }
 66 
 67 void paint(int root)
 68 {
 69     if (tree[root].col!=0)
 70     {
 71         if (tree[root].col == 1)
 72             for (int i = tree[root].l;i <= tree[root].r-1;i++)
 73                 flag[i] = true;
 74         return;
 75     }
 76     paint(root<<1);
 77     paint(root<<1|1);
 78 }
 79 
 80 int main()
 81 {
 82     scanf("%d",&n);
 83     memset(seg,0,sizeof(seg));
 84     memset(cnt,0,sizeof(cnt));
 85     for (int i = 1;i <= n;i++)
 86     {
 87         scanf("%d%d %c",&x,&y,&ch);
 88         seg[i][0] = x;
 89         seg[i][1] = y;
 90         if (ch == 'w') seg[i][2] = 1;
 91         else seg[i][2] = -1;
 92         line[i<<1].p = x;
 93         line[i<<1].num = -(i+1);
 94         line[i<<1|1].p = y;
 95         line[i<<1|1].num = i+1;
 96     }
 97     n++;
 98     seg[0][0] = 0;
 99     seg[0][1] = MAXX;
100     seg[0][2] = 1;
101     line[0].p = 0;
102     line[0].num = -1;
103     line[1].p = MAXX;
104     line[1].num = 1;
105     sort(line,line+n*2,cmp);
106     top = 1;
107     tmp = line[0].p;
108     cnt[1] = tmp;
109     for (int i = 0;i < 2*n;i++)
110     {
111         if (line[i].p!=tmp)
112         {
113             top++;
114             tmp = line[i].p;
115             cnt[top] = tmp;
116         }
117         if (line[i].num < 0)
118             seg[-line[i].num-1][0] = top;
119         else
120             seg[line[i].num-1][1] = top;
121     }
122     buildtree(1,1,top);
123     for (int i = 0;i < n;i++)
124         if (seg[i][0] != seg[i][1])
125             update(1,seg[i][0],seg[i][1],seg[i][2]);
126     memset(flag,false,sizeof(flag));
127     paint(1);
128     x = y = ans = 0;
129     for (int i = 1;i <= top;i++)
130     {
131         if (flag[i])
132             if (x == 0) x = i;
133         if (!flag[i])
134             if (x!=0)
135             {
136                 y = i;
137                 if (cnt[y]-cnt[x] > ans)
138                 {
139                     ans = cnt[y]-cnt[x];
140                     ansx = cnt[x];
141                     ansy = cnt[y];
142                 }
143                 x = y = 0;
144             }
145     } 
146     printf("%d %d
",ansx,ansy);
147 }

View Code

ZOJ2301

题目大意：跟上题差不多。这里不是涂线段而是涂小球，初始都为黑色。

分析：涂小球的时候给定的区间都是点，涂的也是点，为了避免原本不相邻离散化后却相邻的情况出现，我们把题目给定的区间的右端点+1，再以区间建树。最后输出结果时再把右区间-1即可。

参考代码：

  1 //
  2 //  ZOJ2301.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-13.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 
 10 #include <iostream>
 11 #include <cstdio>
 12 #include <cstring>
 13 #include <string>
 14 #include <algorithm>
 15 
 16 using namespace std;
 17 
 18 const int maxn = 20000 + 20;
 19 
 20 struct node
 21 {
 22     int l,r,col;
 23 }tree[maxn<<2],data[maxn];
 24 
 25 struct node2
 26 {
 27     int p,num;
 28 }line[maxn<<1];
 29 
 30 int n,x,y,seg[maxn][3],cnt[maxn],top,tmp,ans,ansx,ansy;
 31 bool flag[maxn];
 32 char ch;
 33 
 34 bool cmp(const node2&p1,const node2&p2)
 35 {
 36     return p1.p < p2.p;
 37 }
 38 
 39 void buildtree(int root,int l,int r)
 40 {
 41     tree[root].l = l;
 42     tree[root].r = r;
 43     tree[root].col = -1;
 44     if (l+1<r)
 45     {
 46         buildtree(root<<1,l,(l+r)/2);
 47         buildtree(root<<1|1,(l+r)/2,r);
 48     }
 49 }
 50 
 51 void update(int root,int l,int r,int c)
 52 {
 53     if (l <= tree[root].l && tree[root].r <= r)
 54     {
 55         tree[root].col = c;
 56         return;
 57     }
 58     if (tree[root].col!=0)
 59     {
 60         tree[root<<1].col = tree[root<<1|1].col = tree[root].col;
 61         tree[root].col = 0;
 62     }
 63     int mid = (tree[root].l+tree[root].r)/2;
 64     if (l < mid) update(root<<1,l,r,c);
 65     if (mid < r) update(root<<1|1,l,r,c);
 66 }
 67 
 68 void paint(int root)
 69 {
 70     if (tree[root].col!=0)
 71     {
 72         if (tree[root].col == 1)
 73             for (int i = tree[root].l;i <= tree[root].r-1;i++)
 74                 flag[i] = true;
 75         return;
 76     }
 77     paint(root<<1);
 78     paint(root<<1|1);
 79 }
 80 
 81 int main()
 82 {
 83     while(scanf("%d",&n)!=EOF)
 84     {
 85     memset(seg,0,sizeof(seg));
 86     memset(cnt,0,sizeof(cnt));
 87     for (int i = 0;i < n;i++)
 88     {
 89         scanf("%d%d %c",&x,&y,&ch);
 90         y++;
 91         seg[i][0] = x;
 92         seg[i][1] = y;
 93         if (ch == 'w') seg[i][2] = 1;
 94         else seg[i][2] = -1;
 95         line[i<<1].p = x;
 96         line[i<<1].num = -(i+1);
 97         line[i<<1|1].p = y;
 98         line[i<<1|1].num = i+1;
 99     }
100     sort(line,line+n*2,cmp);
101     top = 1;
102     tmp = line[0].p;
103     cnt[1] = tmp;
104     for (int i = 0;i < 2*n;i++)
105     {
106         if (line[i].p!=tmp)
107         {
108             top++;
109             tmp = line[i].p;
110             cnt[top] = tmp;
111         }
112         if (line[i].num < 0)
113             seg[-line[i].num-1][0] = top;
114         else
115             seg[line[i].num-1][1] = top;
116     }
117     buildtree(1,1,top);
118     for (int i = 0;i < n;i++)
119         update(1,seg[i][0],seg[i][1],seg[i][2]);
120     memset(flag,false,sizeof(flag));
121     paint(1);
122     x = y = ans = 0;
123     for (int i = 1;i <= top;i++)
124     {
125         if (flag[i])
126             if (x == 0) x = i;
127         if (!flag[i])
128             if (x!=0)
129             {
130                 y = i;
131                 if (cnt[y]-cnt[x] > ans)
132                 {
133                     ans = cnt[y]-cnt[x];
134                     ansx = cnt[x];
135                     ansy = cnt[y]-1;
136                 }
137                 x = y = 0;
138             }
139     }
140     if (ans == 0)
141         printf("Oh, my god
");
142     else
143         printf("%d %d
",ansx,ansy);
144     }
145 }

View Code

POJ3264

题目大意：给一列数，给一些询问，问[a,b]内最大值-最小值是多少

分析：比较简单的题目。以点建树，建树时，遇到叶子节点则读入，max = min = 读入值，否则用左右儿子的最大最小值来更新当前节点的最大最小值。查询就不多说了。

本题还有一种比较简便的RMQ做法，我用RMQ的ST算法也写了一遍，下面代码一起贴上。

参考代码1（线段树）：

 1 //
 2 //  POJ3264.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-14.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 #include <climits>
15 
16 using namespace std;
17 
18 const int maxn = 50000 + 10;
19 
20 struct node
21 {
22     int l,r,mid,m1,m2;
23 }tree[maxn<<2];
24 
25 int n,q,x,y,m1,m2;
26 
27 void buildtree(int root,int l,int r)
28 {
29     tree[root].l = l;
30     tree[root].r = r;
31     tree[root].mid = (l+r)/2;
32     if (l == r)
33     {
34         scanf("%d",&tree[root].m1);
35         tree[root].m2 = tree[root].m1;
36         return;
37     }
38     buildtree(root<<1,l,(l+r)/2);
39     buildtree(root<<1|1,(l+r)/2+1,r);
40     tree[root].m1 = max(tree[root<<1].m1,tree[root<<1|1].m1);
41     tree[root].m2 = min(tree[root<<1].m2,tree[root<<1|1].m2);
42 }
43 
44 int getmax(int root,int l,int r)
45 {
46     if (l <= tree[root].l && tree[root].r <= r)
47         return tree[root].m1;
48     int ans = 0;
49     if (l <= tree[root].mid) ans = max(ans,getmax(root<<1,l,r));
50     if (tree[root].mid < r) ans = max(ans,getmax(root<<1|1,l,r));
51     return ans;
52 }
53 
54 int getmin(int root,int l,int r)
55 {
56     if (l <= tree[root].l && tree[root].r <= r)
57         return tree[root].m2;
58     int ans = INT_MAX;
59     if (l <= tree[root].mid) ans = min(ans,getmin(root<<1,l,r));
60     if (tree[root].mid < r) ans = min(ans,getmin(root<<1|1,l,r));
61     return ans;
62 }
63 
64 int main()
65 {
66     scanf("%d%d",&n,&q);
67     buildtree(1,1,n);
68     while (q--)
69     {
70         scanf("%d%d",&x,&y);
71         m1 = getmax(1,x,y);
72         m2 = getmin(1,x,y);
73         printf("%d
",m1-m2);
74     }
75 }

View Code

参考代码2（RMQ）：

 1 //
 2 //  POJ3264(RMQ).cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-14.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 #include <cmath>
15 
16 using namespace std;
17 
18 const int maxn = 50000 + 10;
19 
20 int n,q,data[maxn],x,y,m1,m2,k,f1[maxn][20],f2[maxn][20];
21 
22 int main()
23 {
24     scanf("%d%d",&n,&q);
25     memset(f1,0,sizeof(f1));
26     memset(f2,0,sizeof(f2));
27     for (int i = 1;i <= n;i++)
28     {
29         scanf("%d",&f1[i][0]);
30         f2[i][0] = f1[i][0];
31     }
32     k = trunc(log(double(n))/log(double(2)));
33     for (int j = 1;j <= k;j++)
34         for (int i = 1;i <= n-(1<<j)+1;i++)
35         {
36             f1[i][j] = max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
37             f2[i][j] = min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
38         }
39     while (q--)
40     {
41         scanf("%d%d",&x,&y);
42         k = trunc(log(double(y-x+1))/log(double(2)));
43         m1 = max(f1[x][k],f1[y-(1<<k)+1][k]);
44         m2 = min(f2[x][k],f2[y-(1<<k)+1][k]);
45         printf("%d
",m1-m2);
46     }
47 }

View Code

POJ1151

题目大意：题意很简单，求矩形的面积并。

分析：对y坐标进行离散化，以区间建树。将矩形分成两个线段，设标记flag，flag＝1表示为左线段，flag＝-1表示为右线段。排序所有线段，从左到右插入。线段树每个节点有两个标记，cover和len，cover>0表示该节点对应y坐标范围仍然被覆盖，len表示该节点覆盖的y坐标的长度。更新时，若区间覆盖当前节点，则cover+=flag，更新当前节点的len，否则更新左右节点，再更新当前节点len。更新len时，若当前节点cover>0，则len为当前区间对应y的长度，否则len为左儿子len＋右儿子len。每插入一个线段，总面积+=根节点的len＊下一个线段和当前线段的x之差。

（我知道我说的很模糊，可能我理解的不太深刻吧，不能清楚的表达出来。。）

参考代码：

  1 //
  2 //  POJ1151(2).cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-16.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <string>
 13 #include <algorithm>
 14 #define FILL(a,b) memset(a,b,sizeof(a));
 15 
 16 using namespace std;
 17 
 18 const int maxn = 100 + 10;
 19 
 20 int n,o,tot,len,a,b;
 21 
 22 double y[maxn<<1],x1,y1,x2,y2,z,ans;
 23 
 24 struct LINE
 25 {
 26     double x,y1,y2;
 27     int flag;
 28     bool operator<(const LINE&p)const
 29     {
 30         return x<p.x;
 31     }
 32 }line[maxn<<1];
 33 
 34 struct node
 35 {
 36     int l,r,cover;
 37     double len;
 38 }tree[maxn<<4];
 39 
 40 void buildtree(int root,int l,int r)
 41 {
 42     tree[root].l = l;
 43     tree[root].r = r;
 44     tree[root].cover = tree[root].len = 0;
 45     if (l+1<r)
 46     {
 47         buildtree(root<<1, l, (l+r)/2);
 48         buildtree(root<<1|1, (l+r)/2, r);
 49     }
 50 }
 51 
 52 int findp(double x)
 53 {
 54     int l = 1,r = len,mid;
 55     while (l<r)
 56     {
 57         mid = (l+r)/2;
 58         if (y[mid] == x) return mid;
 59         if (y[mid]<x)l=mid+1;
 60         else r=mid;
 61     }
 62     return l;
 63 }
 64 
 65 void up(int root)
 66 {
 67     if (tree[root].cover>0)
 68     {
 69         tree[root].len = y[tree[root].r]-y[tree[root].l];
 70         return;
 71     }
 72     if (tree[root].l+1==tree[root].r)
 73     {
 74         tree[root].len = 0;
 75         return;
 76     }
 77     tree[root].len = tree[root<<1].len+tree[root<<1|1].len;
 78 }
 79 
 80 void update(int root,int l,int r,int flag)
 81 {
 82     if (l<=tree[root].l && tree[root].r <= r)
 83     {
 84         tree[root].cover += flag;
 85         up(root);
 86         return;
 87     }
 88     int mid = (tree[root].l+tree[root].r)/2;
 89     if (l<mid)
 90         update(root<<1,l,r,flag);
 91     if (mid<r)
 92         update(root<<1|1,l,r,flag);
 93     up(root);
 94     return;
 95 }
 96 
 97 int main()
 98 {
 99     o = 0;
100     while (scanf("%d",&n),n)
101     {
102         FILL(y,0);
103         tot = len = ans = 0;
104         for (int i = 1;i <= n;i++)
105         {
106             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
107             tot++;
108             y[tot] = y1;
109             line[tot].x = x1;
110             line[tot].y1 = y1;
111             line[tot].y2 = y2;
112             line[tot].flag = 1;
113             
114             tot++;
115             y[tot] = y2;
116             line[tot].x = x2;
117             line[tot].y1 = y1;
118             line[tot].y2 = y2;
119             line[tot].flag = -1;
120         }
121         len = 1;
122         sort(y+1,y+1+tot);
123         for (int i = 2;i <= tot;i++)
124             if (y[i]!=y[i-1])
125                 y[++len] = y[i];
126         sort(line+1,line+1+tot);
127         buildtree(1,1,len);
128         for (int i = 1;i < tot;i++)
129         {
130             a = findp(line[i].y1);
131             b = findp(line[i].y2);
132             update(1,a,b,line[i].flag);
133             ans += (line[i+1].x-line[i].x)*tree[1].len;
134         }
135         printf("Test case #%d
Total explored area: %.2f

",++o,ans);
136     }
137 }

View Code

POJ1177

题目大意：求区间周长并。

分析：本题和求面积并类似，但是稍微难一点。建树时，要维护5个标记，lb，rb表示该节点是否被覆盖，被覆盖则为1，否则为0；cnt表示该节点覆盖了几段分开的y，用于求解x长度计算的次数；len表示当前区间包含的y的长度；cover同上。离散化方式跟上题一样。先将第一条线段插入，计算出根节点的len和cnt，然后从第二条线段循环到最后一条，每次更新时，若区间覆盖当前节点，则cover+=flag，否则更新左右节点。同样，每次更新完后要更新当前节点的lb，rb，len，cnt。若cover>0，表示当前节点整个都被覆盖了，那么lb=rb=cnt=1，len为当前节点对应y的长度；否则lb为左儿子lb，rb为右儿子rb，cnt为左儿子cnt＋右儿子cnt，len为左儿子len＋右儿子len，若左儿子rb和右儿子lb均为1，则cnt-1，因为表示左右儿子区间在中间是连起来了，所以cnt多算了一个。最后算周长时和面积并差不多。

（貌似我说的更不清楚了。。）

参考代码：

  1 //
  2 //  POJ1177.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-16.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <string>
 13 #include <algorithm>
 14 #define FILL(a) memset(a,0,sizeof(a));
 15 #define lc root<<1
 16 #define rc root<<1|1
 17 
 18 using namespace std;
 19 
 20 const int maxn = 10000 + 10;
 21 
 22 class LINE{
 23 public:
 24     int x,y1,y2,flag;
 25     LINE(){};
 26     LINE(int a,int b,int c,int d):x(a),y1(b),y2(c),flag(d){}
 27     bool operator<(const LINE&p) const
 28     {
 29         if (x!=p.x)
 30             return x<p.x;
 31         return flag>p.flag;
 32     }
 33 }line[maxn];
 34 
 35 struct node
 36 {
 37     int l,r,lb,rb,cover,cnt,len;
 38 }tree[maxn<<2];
 39 
 40 int n,y[maxn],top,len,ans,x1,y1,x2,y2,tmplen,tmpcnt,a,b;
 41 
 42 int abs(int x)
 43 {
 44     return x<0?-x:x;
 45 }
 46 
 47 void build(int root,int l,int r)
 48 {
 49     tree[root].l = l;
 50     tree[root].r = r;
 51     tree[root].lb = tree[root].rb = tree[root].cover = tree[root].cnt = tree[root].len = 0;
 52     if (l+1<r)
 53     {
 54         build(lc,l,(l+r)/2);
 55         build(rc,(l+r)/2,r);
 56     }
 57 }
 58 
 59 void up(int root)
 60 {
 61     if (tree[root].cover>0)
 62     {
 63         tree[root].cnt = 1;
 64         tree[root].lb = tree[root].rb = 1;
 65         tree[root].len = y[tree[root].r]-y[tree[root].l];
 66         return;
 67     }
 68     if (tree[root].l+1==tree[root].r)
 69     {
 70         tree[root].len = tree[root].cnt = 0;
 71         tree[root].lb = tree[root].rb = 0;
 72         return;
 73     }
 74     tree[root].lb = tree[lc].lb;
 75     tree[root].rb = tree[rc].rb;
 76     tree[root].len = tree[lc].len+tree[rc].len;
 77     tree[root].cnt = tree[lc].cnt+tree[rc].cnt;
 78     if (tree[lc].rb&&tree[rc].lb)
 79         tree[root].cnt--;
 80 }
 81 
 82 void update(int root,int l,int r,int flag)
 83 {
 84     if (l <= tree[root].l && tree[root].r <= r)
 85     {
 86         tree[root].cover += flag;
 87         up(root);
 88         return;
 89     }
 90     if (l < tree[lc].r) update(lc,l,r,flag);
 91     if (tree[rc].l < r) update(rc,l,r,flag);
 92     up(root);
 93 }
 94 
 95 int main()
 96 {
 97     while(scanf("%d",&n)!=EOF)
 98     {
 99     FILL(y);
100     top = len = ans = tmplen = 0;
101     for (int i = 1;i <= n;i++)
102     {
103         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
104         y[top] = y1;
105         line[top]= *new LINE(x1,y1,y2,1);
106         top++;
107         
108         y[top] = y2;
109         line[top]= *new LINE(x2,y1,y2,-1);
110         top++;
111     }
112     sort(line,line+top);
113     sort(y,y+top);
114     len = unique(y,y+top)-y;
115     build(1,0,len-1);
116     a = lower_bound(y, y+len, line[0].y1)-y;
117     b = lower_bound(y, y+len, line[0].y2)-y;
118     update(1,a,b,line[0].flag);
119     tmplen = ans = tree[1].len;
120     tmpcnt = tree[1].cnt;
121     for (int i = 1;i < top;i++)
122     {
123         a = lower_bound(y, y+len, line[i].y1)-y;
124         b = lower_bound(y, y+len, line[i].y2)-y;
125         update(1,a,b,line[i].flag);
126         ans += abs(tree[1].len-tmplen);
127         ans += tmpcnt*2*(line[i].x-line[i-1].x);
128         tmplen = tree[1].len;
129         tmpcnt = tree[1].cnt;
130     }
131     printf("%d
",ans);
132     }
133 }

View Code

POJ3277

题目大意：同一水平线上不同高度的矩形，求面积并。

分析：简化版的矩形面积并。离散化x，设节点标记cover表示当前节点最大高度。由y从小到大对每个操作排序，否则更新的时候小的会覆盖大的，模拟一下便知。更新时，将y插入[x1,x2]（离散化后）时，若区间覆盖当前节点，则将y与当前cover比较，求最大值。否则将当前cover下放到左右儿子，更新左右儿子。统计时，若当前区间cover>0，则返回区间差*cover，否则返回左右儿子的面积和。

参考代码：

  1 //
  2 //  POJ3277.cpp
  3 //  线段树
  4 //
  5 //  Created by TimmyXu on 13-8-17.
  6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <string>
 13 #include <algorithm>
 14 
 15 #define FILL(a) memset(a,0,sizeof(a));
 16 #define lc root<<1
 17 #define rc root<<1|1
 18 
 19 using namespace std;
 20 
 21 const int maxn = 80000 + 10;
 22 
 23 struct node
 24 {
 25     int l,r;
 26     long long cover;
 27 }tree[maxn<<2];
 28 
 29 struct node2
 30 {
 31     long long x1,x2,y;
 32     bool operator<(const node2&p)const
 33     {
 34         return y<p.y;
 35     }
 36 }seg[maxn];
 37 
 38 int n,tot,a,b;
 39 long long ans,tmp,x[maxn];
 40 
 41 void build(int root,int l,int r)
 42 {
 43     tree[root].l = l;
 44     tree[root].r = r;
 45     tree[root].cover = 0;
 46     if (l+1<r)
 47     {
 48         build(lc,l,(l+r)/2);
 49         build(rc,(l+r)/2,r);
 50     }
 51 }
 52 
 53 void update(int root,int l,int r)
 54 {
 55     if (l <= tree[root].l && tree[root].r <= r)
 56     {
 57         tree[root].cover = max(tree[root].cover,tmp);
 58         return;
 59     }
 60     if (tree[root].l+1<tree[root].r)
 61     {
 62         tree[lc].cover = max(tree[lc].cover,tree[root].cover);
 63         tree[rc].cover = max(tree[rc].cover,tree[root].cover);
 64         tree[root].cover = 0;
 65         if (l<tree[lc].r) update(lc,l,r);
 66         if (tree[rc].l<r) update(rc,l,r);
 67     }
 68 }
 69 
 70 long long getsum(int root)
 71 {
 72     if (tree[root].cover > 0)
 73         return tree[root].cover*(x[tree[root].r]-x[tree[root].l]);
 74     long long ans = 0;
 75     if (tree[root].l+1<tree[root].r)
 76     {
 77         ans += getsum(lc);
 78         ans += getsum(rc);
 79     }
 80     return ans;
 81 }
 82 
 83 int main()
 84 {
 85     scanf("%d",&n);
 86     FILL(seg);
 87     tot = 0;
 88     for (int i = 0;i < n;i++)
 89     {
 90         scanf("%lld%lld%lld",&seg[i].x1,&seg[i].x2,&seg[i].y);
 91         x[tot++] = seg[i].x1;
 92         x[tot++] = seg[i].x2;
 93     }
 94     sort(seg,seg+n);
 95     sort(x,x+tot);
 96     tot = unique(x,x+tot)-x;
 97     build(1,0,tot-1);
 98     for (int i = 0;i < n;i++)
 99     {
100         a = lower_bound(x, x+tot, seg[i].x1)-x;
101         b = lower_bound(x, x+tot, seg[i].x2)-x;
102         tmp = seg[i].y;
103         update(1,a,b);
104     }
105     ans = getsum(1);
106     printf("%lld
",ans);
107 }

View Code

*HDU1394

题目大意：给一列n的某种排列，每次将第一个数移到最后一个，操作n-1次，这样加上初始序列一共有n种不同的序列，问这n种序列中逆序数最小的是多少。

分析：为什么这题我加了*呢，因为这道被标记为线段树的题目我是用树状数组写的。。而且目前我还不会线段树的解法。。

用树状数组时，首先，对于原序列，从后往前插入，计算f[i]，表示当前位置之后的逆序数。再对每个f[i]累加，算出初始ans。

每次将第一个数移到最后时，产生的新的逆序数＝上一个序列逆序数-f[i]+n-f[i]-1;

这个是显而易见的，那么移第一个数时这是成立的，移后面的数呢？我们再设一个数组g[i]，表示当前这个数前面比它小的数，每次移动i时，f[i]+=g[i]，i之前比它小的数都移到后面的话，也被加到f[i]里面了，这样循环一遍，就能统计出每种序列的逆序数，取最小值即可。

参考代码：

 1 //
 2 //  HDU1394.cpp
 3 //  线段树
 4 //
 5 //  Created by TimmyXu on 13-8-17.
 6 //  Copyright (c) 2013年 TimmyXu. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <string>
13 #include <algorithm>
14 
15 #define FILL(a) memset(a,0,sizeof(a));
16 
17 using namespace std;
18 
19 const int maxn = 5000 + 10;
20 
21 int n,c[maxn],c2[maxn],f[maxn],g[maxn],data[maxn],ans,tmp;
22 
23 inline int lowbit(int x)
24 {
25     return x&(-x);
26 }
27 
28 void add(int x)
29 {
30     for (int i = x;i < maxn;i+=lowbit(i))
31         c[i]++;
32 }
33 
34 int sum(int x)
35 {
36     int tot = 0;
37     for (int i = x;i > 0;i-=lowbit(i))
38         tot+=c[i];
39     return tot;
40 }
41 
42 void add2(int x)
43 {
44     for (int i = x;i < maxn;i+=lowbit(i))
45         c2[i]++;
46 }
47 
48 int sum2(int x)
49 {
50     int tot = 0;
51     for (int i = x;i > 0;i-=lowbit(i))
52         tot+=c2[i];
53     return tot;
54 }
55 
56 int main()
57 {
58     while (scanf("%d",&n)!=EOF)
59     {
60         FILL(c);
61         FILL(c2);
62         FILL(f);
63         FILL(g);
64         for (int i = 1;i <= n;i++)
65         {
66              scanf("%d",&data[i]);
67             data[i]++;
68         }
69         ans = 0;
70         for (int i = n;i >= 1;i--)
71         {
72             add(data[i]+1);
73             f[i] = sum(data[i]);
74             ans+=f[i];
75         }
76         tmp = ans;
77         for (int i = 1;i < n;i++)
78         {
79             g[i] = sum2(data[i]-1);
80             f[i]+=g[i];
81             tmp = tmp-f[i]+n-f[i]-1;
82             ans = min(ans,tmp);
83             add2(data[i]);
84         }
85         printf("%d
",ans);
86     }
87 }

View Code

总结：话说做了这么多天线段树，才做了大概1/3都不到。。刷题真是累死人。。