前言：前一段时间在网上找了一个线段树题目列表，我顺着做了一些，今天我把做过的整理一下。感觉自己对线段树了解的还不是很深，自己的算法能力还要加强。光练代码能力还是不够的，要多思考。向队友学习，向大牛学习。
ZOJ1610
题目大意：先后对线段涂色，最后统计每种颜色出现的段数，为0则不输出。
分析：以点建树，每个节点有一个标记col，初始为-1，表示未涂过色。涂色时，若完全覆盖，则col为颜色编号，若覆盖一部分，则先将标记下放到左右儿子节点，再将标号标记为-2，表示此节点被部分覆盖过。最后从根节点开始往下遍历，若遇到节点col>-1的，直接将区间l到r标记为true，若col为-1，则返回，若为-2，则分别到左右儿子遍历。
参考代码：
//
// ZOJ1610.cpp
// 线段树
//
// Created by TimmyXu on 13-8-11.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> const int maxn = + ; struct node
{
int l,r,col;
}tree[maxn<<]; int n,le,ri,c,tmp,mark[maxn],color[maxn]; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].col = -;
if (l < r)
{
buildtree(root<<, l, (l+r)/);
buildtree(root<<|, (l+r)/+, r);
}
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].col = c;
return;
}
int mid = (tree[root].l+tree[root].r)/;
if (tree[root].col > -)
{
tree[root<<].col = tree[root<<|].col = tree[root].col;
tree[root].col = -;
}
if (l <= mid) update(root<<, l, r, c);
if (mid < r) update(root<<|, l, r, c);
} void cnt(int root)
{
if (tree[root].col > -)
{
for (int i = tree[root].l;i <= tree[root].r;i++)
mark[i] = tree[root].col;
return;
}
if (tree[root].col == -)
{
cnt(root<<);
cnt(root<<|);
}
} int main()
{
while (scanf("%d",&n)!=EOF)
{
buildtree(,,);
memset(mark,-,sizeof(mark));
memset(color,,sizeof(color));
while (n--)
{
scanf("%d%d%d",&le,&ri,&c);
update(,le+,ri,c);
}
cnt();
tmp = -;
for (int i = ;i <= ;i++)
{
if (tmp == mark[i]) continue;
tmp = mark[i];
if (tmp != -) color[tmp]++;
}
for (int i = ;i <= ;i++)
if (color[i])
printf("%d %d\n",i,color[i]);
printf("\n");
}
}
POJ2777
题目大意：给两种操作，一种是对区间[a,b]涂色成c，一种是询问区间[a,b]之间不同颜色个数，在线的。由于给的区间直接是线段编号，所以以点建树，每个节点有一个标记col，初始都为颜色1。涂色时，若完全覆盖，则col为颜色编号，若覆盖一部分，则先将标记下放左右儿子，再将标号标记为-1，表示此节点被部分覆盖过。
查询时，
1、若给定区间覆盖当前节点区间，分两种情况：
1）当前区间col>0，则将col标为true；
2）当前区间col＝-1，则分别到左右儿子遍历；
2、若给定区间覆盖当前节点的部分区间，需要遍历左右儿子，那么如果当前区间col>0，需要将col标记下放到左右儿子，再对左右儿子进行查询。
参考代码：
//
// POJ2777.cpp
// 线段树
//
// Created by TimmyXu on 13-8-12.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = + ,maxt = + ; struct node
{
int l,r,col;
}tree[maxn<<]; int n,t,m,le,ri,c,ans;
char ch;
bool vis[maxt]; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].col = ;
if (l < r)
{
buildtree(root<<, l, (l+r)/);
buildtree(root<<|, (l+r)/+, r);
}
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].col = c;
return;
}
if (tree[root].col > )
{
tree[root<<].col = tree[root<<|].col = tree[root].col;
tree[root].col = -;
}
int mid = (tree[root].l+tree[root].r)/;
if (l <= mid) update(root<<, l, r, c);
if (mid < r) update(root<<|, l, r, c);
} void cnt(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
{
if (tree[root].col > )
vis[tree[root].col] = true;
else
{
cnt(root<<,l,r);
cnt(root<<|,l,r);
}
return;
}
if (tree[root].col > )
tree[root<<].col = tree[root<<|].col = tree[root].col; int mid = (tree[root].l+tree[root].r)/;
if (l <= mid) cnt(root<<,l,r);
if (mid < r) cnt(root<<|,l,r);
} int main()
{
scanf("%d%d%d",&n,&t,&m);
buildtree(,,n);
while (m--)
{
scanf("%c%c",&ch,&ch);
if (ch == 'C')
{
scanf("%d%d%d",&le,&ri,&c);
if (le > ri) swap(le,ri);
update(,le,ri,c);
}
else
{
scanf("%d%d",&le,&ri);
if (le > ri) swap(le,ri);
memset(vis,false,sizeof(vis));
cnt(,le,ri);
ans = ;
for (int i = ;i <= t;i++)
ans+=vis[i];
printf("%d\n",ans);
}
}
}
HDU1754
题目大意：两种操作，一个是把编号为a的点的值改为b，一个是询问[a,b]中最大值是多少。
分析：这题比较简单，以点建树，建树过程中建到叶子节点时读入每个点的初始值。更新时，若当前节点是叶子节点，直接更新，若是内部节点，则先递归更新，再用左右儿子的值来更新自己。
参考代码：
//
// HDU1754.cpp
// 线段树
//
// Created by TimmyXu on 13-8-12.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = + ; struct node
{
int l,r,maxs;
}tree[maxn<<]; int n,m,le,ri;
char ch; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
if (l == r)
scanf("%d",&tree[root].maxs);
else
{
buildtree(root<<, l, (l+r)/);
buildtree(root<<|, (l+r)/+, r);
tree[root].maxs = max(tree[root<<].maxs,tree[root<<|].maxs);
}
} void update(int root,int pos,int c)
{
if (tree[root].l == tree[root].r)
{
tree[root].maxs = c;
return;
}
int mid = (tree[root].l+tree[root].r)/;
if (pos <= mid) update(root<<, pos, c);
else update(root<<|, pos, c);
tree[root].maxs = max(tree[root<<].maxs,tree[root<<|].maxs);
} int getmax(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
return tree[root].maxs;
int ans = ,mid = (tree[root].l+tree[root].r)/;
if (l <= mid) ans = max(ans,getmax(root<<,l,r));
if (mid < r) ans = max(ans,getmax(root<<|,l,r));
return ans;
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
buildtree(,,n);
while (m--)
{
scanf("%c%c%d%d",&ch,&ch,&le,&ri);
if (ch == 'Q')
printf("%d\n",getmax(,le,ri));
else
update(,le,ri);
}
}
}
HDU1166
题目大意：和上一题类似，本题有三种操作，将编号a的值加b，将编号a的值减b（即加上-b），询问[a,b]和。
分析：以点建树，建树过程中遇到叶子节点读入初始值。更新时，首先将节点sum值加上b，若当前为叶子节点则返回，若为内部节点，则更新对应的左右儿子。询问时，若区间包含当前节点，则返回当前节点sum值，否则返回左儿子sum值＋右儿子sum值。
参考代码：
//
// HDU1166.cpp
// 线段树
//
// Created by TimmyXu on 13-8-12.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = + ; struct node
{
int l,r,mid,sum;
}tree[maxn << ]; int t,n,le,ri;
char st[]; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].mid = (l+r)/;
if (l == r)
{
scanf("%d",&tree[root].sum);
return;
}
buildtree(root<<, l, (l+r)/);
buildtree(root<<|, (l+r)/+, r);
tree[root].sum = tree[root<<].sum + tree[root<<|].sum;
} void update(int root,int p,int c)
{
tree[root].sum+=c;
if (tree[root].l == tree[root].r)
return;
if (p <= tree[root].mid) update(root<<,p,c);
else update(root<<|,p,c);
} int getsum(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
return tree[root].sum;
int ans = ;
if (l <= tree[root].mid) ans += getsum(root<<,l,r);
if (tree[root].mid < r) ans += getsum(root<<|,l,r);
return ans;
} int main()
{
scanf("%d",&t);
for (int o = ;o <= t;o++)
{
printf("Case %d:\n",o);
scanf("%d",&n);
if (n == ) continue;
buildtree(,,n);
while (scanf("%s",st)!=EOF)
{
if (st[] == 'E') break;
scanf("%d%d",&le,&ri);
if (st[] == 'A')
update(,le,ri);
if (st[] == 'S')
update(,le,-ri);
if (st[] == 'Q')
printf("%d\n",getsum(,le,ri));
}
}
}
HDU1698
题目大意：给定线段，初始值都为1，给定操作a,b,c，将[a,b]的值修改为c，c为1，2或3，最后询问线段所有数的和
分析：以点建树，初始标记col为1，更新时，若区间覆盖当前节点，则更新col为c，否则先将当前col下放到左右儿子，再标记为-1，表示当前节点被不止一种值覆盖。计算时，若当前节点col>0，则返回col＊节点区间长度，否则返回左儿子值＋右儿子值。
参考代码：
//
// HDU1698.cpp
// 线段树
//
// Created by TimmyXu on 13-8-12.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = ; struct node
{
int l,r,len,mid,col;
}tree[maxn << ]; int t,n,m,le,ri,c; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].len = r-l+;
tree[root].mid = (l+r)/;
tree[root].col = ;
if (l < r)
{
buildtree(root<<,l,(l+r)/);
buildtree(root<<|, (l+r)/+, r);
}
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].col = c;
return;
}
if (tree[root].col > )
{
tree[root<<].col = tree[root<<|].col = tree[root].col;
tree[root].col = -;
}
if (l <= tree[root].mid) update(root<<,l,r,c);
if (tree[root].mid < r) update(root<<|, l, r, c);
} int getsum(int root)
{
if (tree[root].col > )
return tree[root].col * tree[root].len;
int ans = ;
ans += getsum(root<<);
ans += getsum(root<<|);
return ans;
} int main()
{
scanf("%d",&t);
for (int o = ;o <= t;o++)
{
scanf("%d%d",&n,&m);
buildtree(,,n);
while (m--)
{
scanf("%d%d%d",&le,&ri,&c);
update(,le,ri,c);
}
printf("Case %d: The total value of the hook is %d.\n",o,getsum());
}
}
POJ3468
题目大意：给一列数，两种操作，一种是将[a,b]每个值加上c，另一种是询问[a,b]和。
分析：经典的区间修改区间询问题。以点建树，维护两个标记，add和sum，分别记录当前节点累加过的值和当前节点覆盖区间的值的和。更新时，若区间覆盖当前节点，则更新add和sum，否则，先用当前节点add值更新左右儿子的add和sum，再分别对左右儿子更新，更新完后再将当前节点sum值更新为左右儿子sum值之和。
参考代码：
//
// POJ3468.cpp
// 线段树
//
// Created by TimmyXu on 13-8-12.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = + ; struct node
{
int l,r,mid;
long long len,add,sum;
}tree[maxn<<]; int n,m,le,ri,c;
char ch; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].mid = (l+r)/;
tree[root].add = ;
tree[root].len = r-l+;
if (l == r)
{
scanf("%lld",&tree[root].sum);
return;
}
buildtree(root<<,l,(l+r)/);
buildtree(root<<|,(l+r)/+,r);
tree[root].sum = tree[root<<].sum + tree[root<<|].sum;
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].add += c;
tree[root].sum += c*tree[root].len;
return;
}
if (tree[root].add!=)
{
tree[root<<].add += tree[root].add;
tree[root<<].sum += tree[root].add*tree[root<<].len;
tree[root<<|].add += tree[root].add;
tree[root<<|].sum += tree[root].add*tree[root<<|].len;
tree[root].add = ;
}
if (l <= tree[root].mid) update(root<<,l,r,c);
if (tree[root].mid < r) update(root<<|,l,r,c);
tree[root].sum = tree[root<<].sum + tree[root<<|].sum;
} long long getsum(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
return tree[root].sum;
if (tree[root].add!=)
{
tree[root<<].add += tree[root].add;
tree[root<<].sum += tree[root].add*tree[root<<].len;
tree[root<<|].add += tree[root].add;
tree[root<<|].sum += tree[root].add*tree[root<<|].len;
tree[root].add = ;
}
long long ans = ;
if (l <= tree[root].mid) ans += getsum(root<<,l,r);
if (tree[root].mid < r) ans += getsum(root<<|,l,r);
tree[root].sum = tree[root<<].sum + tree[root<<|].sum;
return ans;
} int main()
{
scanf("%d%d",&n,&m);
buildtree(,,n);
while (m--)
{
scanf("%c%c%d%d",&ch,&ch,&le,&ri);
if (ch == 'Q')
printf("%lld\n",getsum(,le,ri));
else
{
scanf("%d",&c);
update(,le,ri,c);
}
}
}
Ural 1019
题目大意：给一条线段，初始为白色，之后给一系列操作，将[a,b]涂为黑色或白色，最后统计出白色最长的一段，输出左右区间。
分析：由于区间特别大，所以先离散化。注意题目给的区间都是点，而涂的颜色是线段。所以不能以点建树，而是以区间建树，元区间为[a,a+1)。
整个线段初始为白色，所以在所有操作前加一条将整个区间涂为白色的操作。更新时，若区间覆盖当前节点区间，则更新col（白色为1，黑色为-1，被多种覆盖为0），否则将col下放到左右儿子，当前col更新为0，再更新左右儿子。查询时，若当前节点col为1，则将当前节点区间[l,r-1]改为true，为什么是r-1呢？因为我们要计算的是线段，也避免了原本不相邻离散化后相邻的情况出现。最后统计最长的为true的区间。
参考代码：
//
// Ural1019.cpp
// 线段树
//
// Created by TimmyXu on 13-8-13.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = + ,MAXX = ; struct node
{
int l,r,col;
}tree[maxn<<],data[maxn]; struct node2
{
int p,num;
}line[maxn<<]; int n,x,y,seg[maxn][],cnt[maxn],top,tmp,ans,ansx,ansy;
bool flag[maxn];
char ch; bool cmp(const node2&p1,const node2&p2)
{
return p1.p < p2.p;
} void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].col = ;
if (l+<r)
{
buildtree(root<<,l,(l+r)/);
buildtree(root<<|,(l+r)/,r);
}
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].col = c;
return;
}
if (tree[root].col!=)
{
tree[root<<].col = tree[root<<|].col = tree[root].col;
tree[root].col = ;
}
int mid = (tree[root].l+tree[root].r)/;
if (l < mid) update(root<<,l,r,c);
if (mid < r) update(root<<|,l,r,c);
} void paint(int root)
{
if (tree[root].col!=)
{
if (tree[root].col == )
for (int i = tree[root].l;i <= tree[root].r-;i++)
flag[i] = true;
return;
}
paint(root<<);
paint(root<<|);
} int main()
{
scanf("%d",&n);
memset(seg,,sizeof(seg));
memset(cnt,,sizeof(cnt));
for (int i = ;i <= n;i++)
{
scanf("%d%d %c",&x,&y,&ch);
seg[i][] = x;
seg[i][] = y;
if (ch == 'w') seg[i][] = ;
else seg[i][] = -;
line[i<<].p = x;
line[i<<].num = -(i+);
line[i<<|].p = y;
line[i<<|].num = i+;
}
n++;
seg[][] = ;
seg[][] = MAXX;
seg[][] = ;
line[].p = ;
line[].num = -;
line[].p = MAXX;
line[].num = ;
sort(line,line+n*,cmp);
top = ;
tmp = line[].p;
cnt[] = tmp;
for (int i = ;i < *n;i++)
{
if (line[i].p!=tmp)
{
top++;
tmp = line[i].p;
cnt[top] = tmp;
}
if (line[i].num < )
seg[-line[i].num-][] = top;
else
seg[line[i].num-][] = top;
}
buildtree(,,top);
for (int i = ;i < n;i++)
if (seg[i][] != seg[i][])
update(,seg[i][],seg[i][],seg[i][]);
memset(flag,false,sizeof(flag));
paint();
x = y = ans = ;
for (int i = ;i <= top;i++)
{
if (flag[i])
if (x == ) x = i;
if (!flag[i])
if (x!=)
{
y = i;
if (cnt[y]-cnt[x] > ans)
{
ans = cnt[y]-cnt[x];
ansx = cnt[x];
ansy = cnt[y];
}
x = y = ;
}
}
printf("%d %d\n",ansx,ansy);
}
ZOJ2301
题目大意：跟上题差不多。这里不是涂线段而是涂小球，初始都为黑色。
分析：涂小球的时候给定的区间都是点，涂的也是点，为了避免原本不相邻离散化后却相邻的情况出现，我们把题目给定的区间的右端点+1，再以区间建树。最后输出结果时再把右区间-1即可。
参考代码：
//
// ZOJ2301.cpp
// 线段树
//
// Created by TimmyXu on 13-8-13.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; const int maxn = + ; struct node
{
int l,r,col;
}tree[maxn<<],data[maxn]; struct node2
{
int p,num;
}line[maxn<<]; int n,x,y,seg[maxn][],cnt[maxn],top,tmp,ans,ansx,ansy;
bool flag[maxn];
char ch; bool cmp(const node2&p1,const node2&p2)
{
return p1.p < p2.p;
} void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].col = -;
if (l+<r)
{
buildtree(root<<,l,(l+r)/);
buildtree(root<<|,(l+r)/,r);
}
} void update(int root,int l,int r,int c)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].col = c;
return;
}
if (tree[root].col!=)
{
tree[root<<].col = tree[root<<|].col = tree[root].col;
tree[root].col = ;
}
int mid = (tree[root].l+tree[root].r)/;
if (l < mid) update(root<<,l,r,c);
if (mid < r) update(root<<|,l,r,c);
} void paint(int root)
{
if (tree[root].col!=)
{
if (tree[root].col == )
for (int i = tree[root].l;i <= tree[root].r-;i++)
flag[i] = true;
return;
}
paint(root<<);
paint(root<<|);
} int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(seg,,sizeof(seg));
memset(cnt,,sizeof(cnt));
for (int i = ;i < n;i++)
{
scanf("%d%d %c",&x,&y,&ch);
y++;
seg[i][] = x;
seg[i][] = y;
if (ch == 'w') seg[i][] = ;
else seg[i][] = -;
line[i<<].p = x;
line[i<<].num = -(i+);
line[i<<|].p = y;
line[i<<|].num = i+;
}
sort(line,line+n*,cmp);
top = ;
tmp = line[].p;
cnt[] = tmp;
for (int i = ;i < *n;i++)
{
if (line[i].p!=tmp)
{
top++;
tmp = line[i].p;
cnt[top] = tmp;
}
if (line[i].num < )
seg[-line[i].num-][] = top;
else
seg[line[i].num-][] = top;
}
buildtree(,,top);
for (int i = ;i < n;i++)
update(,seg[i][],seg[i][],seg[i][]);
memset(flag,false,sizeof(flag));
paint();
x = y = ans = ;
for (int i = ;i <= top;i++)
{
if (flag[i])
if (x == ) x = i;
if (!flag[i])
if (x!=)
{
y = i;
if (cnt[y]-cnt[x] > ans)
{
ans = cnt[y]-cnt[x];
ansx = cnt[x];
ansy = cnt[y]-;
}
x = y = ;
}
}
if (ans == )
printf("Oh, my god\n");
else
printf("%d %d\n",ansx,ansy);
}
}
POJ3264
题目大意：给一列数，给一些询问，问[a,b]内最大值-最小值是多少
分析：比较简单的题目。以点建树，建树时，遇到叶子节点则读入，max = min = 读入值，否则用左右儿子的最大最小值来更新当前节点的最大最小值。查询就不多说了。
本题还有一种比较简便的RMQ做法，我用RMQ的ST算法也写了一遍，下面代码一起贴上。
参考代码1（线段树）：
//
// POJ3264.cpp
// 线段树
//
// Created by TimmyXu on 13-8-14.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits> using namespace std; const int maxn = + ; struct node
{
int l,r,mid,m1,m2;
}tree[maxn<<]; int n,q,x,y,m1,m2; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].mid = (l+r)/;
if (l == r)
{
scanf("%d",&tree[root].m1);
tree[root].m2 = tree[root].m1;
return;
}
buildtree(root<<,l,(l+r)/);
buildtree(root<<|,(l+r)/+,r);
tree[root].m1 = max(tree[root<<].m1,tree[root<<|].m1);
tree[root].m2 = min(tree[root<<].m2,tree[root<<|].m2);
} int getmax(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
return tree[root].m1;
int ans = ;
if (l <= tree[root].mid) ans = max(ans,getmax(root<<,l,r));
if (tree[root].mid < r) ans = max(ans,getmax(root<<|,l,r));
return ans;
} int getmin(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
return tree[root].m2;
int ans = INT_MAX;
if (l <= tree[root].mid) ans = min(ans,getmin(root<<,l,r));
if (tree[root].mid < r) ans = min(ans,getmin(root<<|,l,r));
return ans;
} int main()
{
scanf("%d%d",&n,&q);
buildtree(,,n);
while (q--)
{
scanf("%d%d",&x,&y);
m1 = getmax(,x,y);
m2 = getmin(,x,y);
printf("%d\n",m1-m2);
}
}
参考代码2（RMQ）：
//
// POJ3264(RMQ).cpp
// 线段树
//
// Created by TimmyXu on 13-8-14.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath> using namespace std; const int maxn = + ; int n,q,data[maxn],x,y,m1,m2,k,f1[maxn][],f2[maxn][]; int main()
{
scanf("%d%d",&n,&q);
memset(f1,,sizeof(f1));
memset(f2,,sizeof(f2));
for (int i = ;i <= n;i++)
{
scanf("%d",&f1[i][]);
f2[i][] = f1[i][];
}
k = trunc(log(double(n))/log(double()));
for (int j = ;j <= k;j++)
for (int i = ;i <= n-(<<j)+;i++)
{
f1[i][j] = max(f1[i][j-],f1[i+(<<(j-))][j-]);
f2[i][j] = min(f2[i][j-],f2[i+(<<(j-))][j-]);
}
while (q--)
{
scanf("%d%d",&x,&y);
k = trunc(log(double(y-x+))/log(double()));
m1 = max(f1[x][k],f1[y-(<<k)+][k]);
m2 = min(f2[x][k],f2[y-(<<k)+][k]);
printf("%d\n",m1-m2);
}
}
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之差。
（我知道我说的很模糊，可能我理解的不太深刻吧，不能清楚的表达出来。。）
参考代码：
//
// POJ1151(2).cpp
// 线段树
//
// Created by TimmyXu on 13-8-16.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define FILL(a,b) memset(a,b,sizeof(a)); using namespace std; const int maxn = + ; int n,o,tot,len,a,b; double y[maxn<<],x1,y1,x2,y2,z,ans; struct LINE
{
double x,y1,y2;
int flag;
bool operator<(const LINE&p)const
{
return x<p.x;
}
}line[maxn<<]; struct node
{
int l,r,cover;
double len;
}tree[maxn<<]; void buildtree(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].cover = tree[root].len = ;
if (l+<r)
{
buildtree(root<<, l, (l+r)/);
buildtree(root<<|, (l+r)/, r);
}
} int findp(double x)
{
int l = ,r = len,mid;
while (l<r)
{
mid = (l+r)/;
if (y[mid] == x) return mid;
if (y[mid]<x)l=mid+;
else r=mid;
}
return l;
} void up(int root)
{
if (tree[root].cover>)
{
tree[root].len = y[tree[root].r]-y[tree[root].l];
return;
}
if (tree[root].l+==tree[root].r)
{
tree[root].len = ;
return;
}
tree[root].len = tree[root<<].len+tree[root<<|].len;
} void update(int root,int l,int r,int flag)
{
if (l<=tree[root].l && tree[root].r <= r)
{
tree[root].cover += flag;
up(root);
return;
}
int mid = (tree[root].l+tree[root].r)/;
if (l<mid)
update(root<<,l,r,flag);
if (mid<r)
update(root<<|,l,r,flag);
up(root);
return;
} int main()
{
o = ;
while (scanf("%d",&n),n)
{
FILL(y,);
tot = len = ans = ;
for (int i = ;i <= n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
tot++;
y[tot] = y1;
line[tot].x = x1;
line[tot].y1 = y1;
line[tot].y2 = y2;
line[tot].flag = ; tot++;
y[tot] = y2;
line[tot].x = x2;
line[tot].y1 = y1;
line[tot].y2 = y2;
line[tot].flag = -;
}
len = ;
sort(y+,y++tot);
for (int i = ;i <= tot;i++)
if (y[i]!=y[i-])
y[++len] = y[i];
sort(line+,line++tot);
buildtree(,,len);
for (int i = ;i < tot;i++)
{
a = findp(line[i].y1);
b = findp(line[i].y2);
update(,a,b,line[i].flag);
ans += (line[i+].x-line[i].x)*tree[].len;
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++o,ans);
}
}
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多算了一个。最后算周长时和面积并差不多。
（貌似我说的更不清楚了。。）
参考代码：
//
// POJ1177.cpp
// 线段树
//
// Created by TimmyXu on 13-8-16.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define FILL(a) memset(a,0,sizeof(a));
#define lc root<<1
#define rc root<<1|1 using namespace std; const int maxn = + ; class LINE{
public:
int x,y1,y2,flag;
LINE(){};
LINE(int a,int b,int c,int d):x(a),y1(b),y2(c),flag(d){}
bool operator<(const LINE&p) const
{
if (x!=p.x)
return x<p.x;
return flag>p.flag;
}
}line[maxn]; struct node
{
int l,r,lb,rb,cover,cnt,len;
}tree[maxn<<]; int n,y[maxn],top,len,ans,x1,y1,x2,y2,tmplen,tmpcnt,a,b; int abs(int x)
{
return x<?-x:x;
} void build(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].lb = tree[root].rb = tree[root].cover = tree[root].cnt = tree[root].len = ;
if (l+<r)
{
build(lc,l,(l+r)/);
build(rc,(l+r)/,r);
}
} void up(int root)
{
if (tree[root].cover>)
{
tree[root].cnt = ;
tree[root].lb = tree[root].rb = ;
tree[root].len = y[tree[root].r]-y[tree[root].l];
return;
}
if (tree[root].l+==tree[root].r)
{
tree[root].len = tree[root].cnt = ;
tree[root].lb = tree[root].rb = ;
return;
}
tree[root].lb = tree[lc].lb;
tree[root].rb = tree[rc].rb;
tree[root].len = tree[lc].len+tree[rc].len;
tree[root].cnt = tree[lc].cnt+tree[rc].cnt;
if (tree[lc].rb&&tree[rc].lb)
tree[root].cnt--;
} void update(int root,int l,int r,int flag)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].cover += flag;
up(root);
return;
}
if (l < tree[lc].r) update(lc,l,r,flag);
if (tree[rc].l < r) update(rc,l,r,flag);
up(root);
} int main()
{
while(scanf("%d",&n)!=EOF)
{
FILL(y);
top = len = ans = tmplen = ;
for (int i = ;i <= n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
y[top] = y1;
line[top]= *new LINE(x1,y1,y2,);
top++; y[top] = y2;
line[top]= *new LINE(x2,y1,y2,-);
top++;
}
sort(line,line+top);
sort(y,y+top);
len = unique(y,y+top)-y;
build(,,len-);
a = lower_bound(y, y+len, line[].y1)-y;
b = lower_bound(y, y+len, line[].y2)-y;
update(,a,b,line[].flag);
tmplen = ans = tree[].len;
tmpcnt = tree[].cnt;
for (int i = ;i < top;i++)
{
a = lower_bound(y, y+len, line[i].y1)-y;
b = lower_bound(y, y+len, line[i].y2)-y;
update(,a,b,line[i].flag);
ans += abs(tree[].len-tmplen);
ans += tmpcnt**(line[i].x-line[i-].x);
tmplen = tree[].len;
tmpcnt = tree[].cnt;
}
printf("%d\n",ans);
}
}
POJ3277
题目大意：同一水平线上不同高度的矩形，求面积并。
分析：简化版的矩形面积并。离散化x，设节点标记cover表示当前节点最大高度。由y从小到大对每个操作排序，否则更新的时候小的会覆盖大的，模拟一下便知。更新时，将y插入[x1,x2]（离散化后）时，若区间覆盖当前节点，则将y与当前cover比较，求最大值。否则将当前cover下放到左右儿子，更新左右儿子。统计时，若当前区间cover>0，则返回区间差*cover，否则返回左右儿子的面积和。
参考代码：
//
// POJ3277.cpp
// 线段树
//
// Created by TimmyXu on 13-8-17.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> #define FILL(a) memset(a,0,sizeof(a));
#define lc root<<1
#define rc root<<1|1 using namespace std; const int maxn = + ; struct node
{
int l,r;
long long cover;
}tree[maxn<<]; struct node2
{
long long x1,x2,y;
bool operator<(const node2&p)const
{
return y<p.y;
}
}seg[maxn]; int n,tot,a,b;
long long ans,tmp,x[maxn]; void build(int root,int l,int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].cover = ;
if (l+<r)
{
build(lc,l,(l+r)/);
build(rc,(l+r)/,r);
}
} void update(int root,int l,int r)
{
if (l <= tree[root].l && tree[root].r <= r)
{
tree[root].cover = max(tree[root].cover,tmp);
return;
}
if (tree[root].l+<tree[root].r)
{
tree[lc].cover = max(tree[lc].cover,tree[root].cover);
tree[rc].cover = max(tree[rc].cover,tree[root].cover);
tree[root].cover = ;
if (l<tree[lc].r) update(lc,l,r);
if (tree[rc].l<r) update(rc,l,r);
}
} long long getsum(int root)
{
if (tree[root].cover > )
return tree[root].cover*(x[tree[root].r]-x[tree[root].l]);
long long ans = ;
if (tree[root].l+<tree[root].r)
{
ans += getsum(lc);
ans += getsum(rc);
}
return ans;
} int main()
{
scanf("%d",&n);
FILL(seg);
tot = ;
for (int i = ;i < n;i++)
{
scanf("%lld%lld%lld",&seg[i].x1,&seg[i].x2,&seg[i].y);
x[tot++] = seg[i].x1;
x[tot++] = seg[i].x2;
}
sort(seg,seg+n);
sort(x,x+tot);
tot = unique(x,x+tot)-x;
build(,,tot-);
for (int i = ;i < n;i++)
{
a = lower_bound(x, x+tot, seg[i].x1)-x;
b = lower_bound(x, x+tot, seg[i].x2)-x;
tmp = seg[i].y;
update(,a,b);
}
ans = getsum();
printf("%lld\n",ans);
}
*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]里面了，这样循环一遍，就能统计出每种序列的逆序数，取最小值即可。
参考代码：
//
// HDU1394.cpp
// 线段树
//
// Created by TimmyXu on 13-8-17.
// Copyright (c) 2013年 TimmyXu. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm> #define FILL(a) memset(a,0,sizeof(a)); using namespace std; const int maxn = + ; int n,c[maxn],c2[maxn],f[maxn],g[maxn],data[maxn],ans,tmp; inline int lowbit(int x)
{
return x&(-x);
} void add(int x)
{
for (int i = x;i < maxn;i+=lowbit(i))
c[i]++;
} int sum(int x)
{
int tot = ;
for (int i = x;i > ;i-=lowbit(i))
tot+=c[i];
return tot;
} void add2(int x)
{
for (int i = x;i < maxn;i+=lowbit(i))
c2[i]++;
} int sum2(int x)
{
int tot = ;
for (int i = x;i > ;i-=lowbit(i))
tot+=c2[i];
return tot;
} int main()
{
while (scanf("%d",&n)!=EOF)
{
FILL(c);
FILL(c2);
FILL(f);
FILL(g);
for (int i = ;i <= n;i++)
{
scanf("%d",&data[i]);
data[i]++;
}
ans = ;
for (int i = n;i >= ;i--)
{
add(data[i]+);
f[i] = sum(data[i]);
ans+=f[i];
}
tmp = ans;
for (int i = ;i < n;i++)
{
g[i] = sum2(data[i]-);
f[i]+=g[i];
tmp = tmp-f[i]+n-f[i]-;
ans = min(ans,tmp);
add2(data[i]);
}
printf("%d\n",ans);
}
}
总结：话说做了这么多天线段树，才做了大概1/3都不到。。刷题真是累死人。。