ACM经典题目之线段树

hello kity

期待您的批阅，由于写解题报告时不一定考虑的很周到，所以如果您有什么不懂的地方，请您留言，然而一天之内我肯定会看见您信息，再对代码注释详细，让您更好的阅读

分类

POJ 2777（Count Color）经典染色问题

题目大意：就是给出两种指令操作，
1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

题目分析：首先建树，树节点有三个域，分别为左右端点r,l,与代表颜色的color。首先声明，当color等于0的时候表示被多种颜色覆盖了。

更新：首先如果在查找的过程中遇到当前区间的颜色大于0，也就是说这个区间已经被完全染色过，那么就把这个区间的颜色值往下传递，然后把这个区间的颜色值color赋值为0，继续往下查找，也就是常规的三种情况：左子树，右子树，或者左右子树混合的

直到当前区间的跟我的所要更新的区间吻合，停止往下更新！进行染色，也就是把color值附给他，还有一种情况就是：当前区间的color值大于0并且等于我所要染色的颜色值，这样也可以停止往下更新！

计数：在往下计数的时候，如果遇到color值大于0的直接把他在hash[]表里的映射赋值为1，这样防止重复计数！如果color==0；就继续往下计数。又是常规的三种情况！

源程序+部分注释：

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
 
struct node{
    int a,b,color;
}s[400000];
int h[60];
int Build(int x,int y,int num){
    s[num].a=x; s[num].b=y;
    s[num].color=1;
    if(x==y)
        return 0;
    else{
        Build(x,(x+y)/2,num+num);
        Build((x+y)/2+1,y,num+num+1);
    }
}
 
int modify(int x,int y,int num,int color){
    if(x==s[num].a&&y==s[num].b){
        s[num].color=color;
        return 0;
    }
    if(s[num].color==color)
        return 0;
    if(s[num].color>0){
        s[num+num].color=s[num+num+1].color=s[num].color;
        s[num].color=0;
    }   
    if(y<=(s[num].a+s[num].b)/2)
        modify(x,y,num+num,color);
    else if(x>(s[num].a+s[num].b)/2)
        modify(x,y,num+num+1,color);
    else{
        modify(x,(s[num].a+s[num].b)/2,num+num,color);
        modify((s[num].a+s[num].b)/2+1,y,num+num+1,color);
    }
}
 
int getsum(int x,int y,int num){
    if(s[num].color>0){
        h[s[num].color]=1;
        return 0;
    }
    else{
        if(y<=(s[num].a+s[num].b)/2)
            getsum(x,y,num+num);
        else if(x>(s[num].a+s[num].b)/2)
            getsum(x,y,num+num+1);
        else{
            getsum(x,(s[num].a+s[num].b)/2,num+num);
            getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
        }
    }
}
 
int main(){
    int l,t,cas,i,j,sum;
    int x,y,color;
    char c;
    scanf("%d %d %d",&l,&t,&cas);
        memset(h,0,sizeof(h));
        Build(1,l,1);
        for(j=1;j<=cas;j++){
            sum=0;
            cin>>c;
            if('P'==c){
                scanf("%d %d",&x,&y);
                getsum(x,y,1);
                for(i=1;i<=t;i++)
                    cout<<h[i];
                cout<<endl;
                for(i=1;i<=t;i++)
                    sum+=h[i];
                printf("%d\n",sum);
                memset(h,0,sizeof(h));
            }
            else if('C'==c){
                scanf("%d %d %d",&x,&y,&color);
                modify(x,y,1,color);
            }
        }
    return 0;
}

HDU 1394(Minimum Inversion Number)

题目大意：给你一个连续的自然数序列，
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

中逆序数最大的是多少。

其实用树状数组求这个是非常方便速度的，但是为了锻炼线段树我还是用线段树写了。

程序+部分注释：

#include<iostream>
#include<stdio.h>
using namespace std;
int ans=0;
struct node{
    int a,b;
    int v;
}s[20000];
 
int t[5002];
 
int Build(int x,int y,int num){
    s[num].a=x; s[num].b=y;
    s[num].v=0;
    if(x==y)
        return 0;
    Build(x,(s[num].a+s[num].b)/2,num+num);
    Build((s[num].a+s[num].b)/2+1,y,num+num+1); 
}
 
int modify(int num,int ide ){
    if(s[num].a==s[num].b){
        s[num].v=1;
        return 0;
    }
    else{
        if(ide<=(s[num].a+s[num].b)/2)
            modify(num+num,ide);
        else if(ide>(s[num].a+s[num].b)/2)
            modify(num+num+1,ide);
        s[num].v=s[num+num].v+s[num+num+1].v;
    }
}
 
int getsum(int x,int y,int num){
    if(x==s[num].a&&y==s[num].b){
        ans+=s[num].v;
        return 0;
    }
    else{
        if(y<=(s[num].a+s[num].b)/2)
            getsum(x,y,num+num);
        else if(x>(s[num].a+s[num].b)/2)
            getsum(x,y,num+num+1);
        else{
            getsum(x,(s[num].a+s[num].b)/2,num+num);
            getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
        }
    }
}
 
int main(){
    int n,i,min;
    while(scanf("%d",&n)!=EOF){
        ans=0;
        for(i=1;i<=n;i++)
            scanf("%d",&t[i]);
        Build(1,n,1);
        for(i=n;i>=1;i--){
            getsum(1,t[i]+1,1);
            modify(1,t[i]+1);
                        求出总和
        }
        min=ans;
        for(i=1;i<=n-1;i++){
            ans=ans-t[i]+n-t[i]-1;
                        //因为数组是连续的自然数，从0到n所以
                       //t[i]移动到最后面去，就减少了t[i]个逆                    
                         //序对，同时也与以前是后面的而且比他大的数构成了
                           //N-（t[i]+1）组逆序对
            if(ans<min)
                min=ans;
        }
        printf("%d\n",min);
    }
    return 0;
}

HDU 1698（Just a Hook）

题目大意：给一组棍子染色，不同的颜色有不同的值，执行一系列的区间染色后，问这组棍子的总值是多少。

题目分析：建树：节点的域有左右节点和颜色，a,b,v；v=0时表示这个区间由多种颜色覆盖。

更新的时候，如果更新区间比当前区间小，并且当前区间的颜色大于0，说明已经被完全染色，就把该区间颜色传递到左右子树上，该区间染色为0，然后根据更新区间的大小，在左右子树上去搜索。

求和的时候遇到区间的v>0的时候说明完全被染色过了，就把区间的长度乘以颜色的值加到总和里面去，然后结束这个方向的递归查询，

源程序+部分注释：

#include<stdio.h>
#include<iostream>
using namespace std;
struct node{
    int a,b,v;
}s[400000];
 
int t[150000],ans;
 
void Build(int x,int y,int num){
    s[num].a=x; 
    s[num].b=y;
    s[num].v=1;
    if(x==y)
        return ;    
    else{
        Build(x,(x+y)/2,num+num);
        Build((x+y)/2+1,y,num+num+1);
    }
}
 
void modify(int x,int y,int num,int value){
    if(x==s[num].a&&s[num].b==y){
        s[num].v=value;
        return ;
    }
    if(s[num].v==value)
        return ;
    if(s[num].v>0){
        s[2*num].v=s[2*num+1].v=s[num].v;
        s[num].v=0;
              //值往下传递。0代表混合染色
    }
    if(y<=(s[num].a+s[num].b)/2){
        modify(x,y,num+num,value);
    }
    else if(x>(s[num].a+s[num].b)/2)
        modify(x,y,num+num+1,value);
    else{   int mid=(s[num].a+s[num].b)/2;
        modify(x,mid,num+num,value);
        modify(mid+1,y,num+num+1,value);
    }
         
}
 
int getsum(int x,int y,int num){
    if(s[num].v>0){
        ans+=(s[num].b-s[num].a+1)*s[num].v;
        return 0;
    }
    else{
        if(y<=(s[num].a+s[num].b)/2)
            getsum(x,y,num+num);
        else if(x>(s[num].a+s[num].b)/2)
            getsum(x,y,num+num+1);
        else{
            getsum(x,(s[num].a+s[num].b)/2,num+num);
            getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
        }
    }
 
}
 
int main(){
    int cas,n,k,i,v;
    int x,y,count;
    cin>>cas;
    k=1;
    while(cas--){
        ans=0;
        cin>>n;
        for(i=1;i<=n;i++){
            t[i]=1;
        }
        Build(1,n,1);
        scanf("%d",&count);
        for(i=1;i<=count;i++){
            scanf("%d %d %d",&x,&y,&v);
            modify(x,y,1,v);
        }
        getsum(1,n,1);
        printf("Case %d: The total value of the hook is %d.\n",k++,ans);
    }
    return 0;
}

hdu 1754(I HATE IT)

题目分析：学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

有一次参加农大月赛，因为对线段树的求区间最值的更新还是不熟练，所以出错了！缅怀！

#include<stdio.h>
int Max(int a,int b)
{
    return a>b?a:b;
}
struct node{
    int max,a,b;
}s[800000];
 
int t[200010];
 
void Build(int x,int y,int num){
    s[num].a=x; s[num].b=y;
    if(x==y){
        s[num].max=t[x];
        return ;
    }
    else{
        Build(x,(x+y)/2,num+num);
        Build(((x+y)/2)+1,y,num+num+1);
        s[num].max=Max(s[num+num].max,s[num+num+1].max);
    }
}
int Query_max(int x,int y,int idx)
{
    if(x<=s[idx].a && s[idx].b<=y)
    {
        return s[idx].max;
    }
    if(y<=s[idx*2].b) return Query_max(x,y,idx*2);
    else if(x>=s[idx*2+1].a) return Query_max(x,y,idx*2+1);
    else return Max(Query_max(x,s[idx*2].b,idx*2),Query_max(s[idx*2+1].a,y,idx*2+1));
}
int modify(int x,int y,int num){
    if(s[num].a==x&&s[num].b==x){
        s[num].max=y;   
        return 0;
    }
    else{
        if(x<=s[num+num].b)
            modify(x,y,num+num);
        else
            modify(x,y,num+num+1);
        s[num].max=Max(s[num+num].max,s[num+num+1].max);
    }
}
 
int main(){
    int n,cas,i,x,y;
    char c;
    while(scanf("%d %d",&n,&cas)!=EOF){
        for(i=1;i<=n;i++)
            scanf("%d",&t[i]);
        Build(1,n,1);
        while(cas--){
            getchar();
            scanf("%c %d %d",&c,&x,&y);
            if(c=='Q'){
                printf("%d\n",Query_max(x,y,1));        
            }
            else {
                modify(x,y,1);
            }
        }
         
    }
    return 0;
}

题目大意：(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
                (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
                (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
                (4)End 表示结束，这条命令在每组数据最后出现;

题目分析：目的是纪念我线段树的开端，也是为了今后的回顾。其实就是基本操作，更新跟建树。

源程序+部分注释：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
 
struct node{
    int sum,a,b;
}s[140000];
 
int t[52005],ans;
 
void Build(int x,int y,int num){
    s[num].a=x;  s[num].b=y;
    if(x==y)
        s[num].sum=t[x];
    else{
        Build(x,(x+y)/2,num+num);
        Build(((x+y)/2)+1,y,num+num+1);
        s[num].sum=s[num+num].sum+s[num+num+1].sum;
    }
}
 
void Query(int x,int y,int num){
    if(x<=s[num].a&&y>=s[num].b)
        ans+=s[num].sum;
    else{
        if(x>(s[num].a+s[num].b)/2)
            Query(x,y,num+num+1);
        else if(y<=(s[num].a+s[num].b)/2)
            Query(x,y,num+num);
        else{
            Query(x,y,num+num);
            Query(x,y,num+num+1);
        }
    }
}
 
void Add(int x,int y,int num){
    s[num].sum+=y;
    if(s[num].a==x&&s[num].b==x)
        return ;
    else{
        if(x<=(s[num].a+s[num].b)/2)
            Add(x,y,num+num);
        else
            Add(x,y,num+num+1);
    }
}
 
int Sub(int x,int y,int num){
    s[num].sum-=y;
    if(s[num].a==x&&s[num].b==x)
        return 0;
    else{
        if(x<=(s[num].a+s[num].b)/2)
            Sub(x,y,num+num);
        else
            Sub(x,y,num+num+1);
    }
}
 
int main(){
    int cas,n,i,k,x,y;
    char c[20];
    scanf("%d",&cas);
    k=1;
    while(cas--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&t[i]);
        }
        Build(1,n,1);
        cout<<"Case "<<k<<":"<<endl;
        k++;
        while(1){
            scanf("%s",c);
            if(c[0]=='E')
                break;
            scanf("%d %d",&x,&y);
            if(c[0]=='Q'){
                ans=0;
                Query(x,y,1);
                cout<<ans<<endl;            
            }
            else if(c[0]=='A'){
                Add(x,y,1);
            }
            else{
                if(c[0]=='S')
                    Sub(x,y,1);
            }
        }
    }
    return 0;
}

HDU 2852（KiKi's K-Number）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define max 100000
#define lowbit(x) (x&(-x))
using namespace std;
const int N=100001;
int c[100005],a[100005];
 
int getsum(int x){
    int sum=0;
    while(x){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
 
int modify(int x,int num){
    while(x<=N){
        c[x]+=num;
        x+=lowbit(x);
    }
    return 0;
}
 
int main(){
    int n,i,left,right,md;
    int sign,m,t,num1;
    while(scanf("%d",&n)!=EOF){
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        while(n--){
            scanf("%d",&sign);
            if(sign==0){
                scanf("%d",&t);
                a[t]++;
                modify(t,1);
            }
            else if(sign==1){
                scanf("%d",&t);
                if(!a[t])
                    cout<<"No Elment!"<<endl;
                else{
                    a[t]--;
                    modify(t,-1);
                }
            }
            else if(sign==2){
                scanf("%d %d",&m,&t);
                num1=getsum(m)+t;
                if(num1>getsum(max)){
                    cout<<"Not Find!"<<endl;
                        continue;               
                }
                left=m+1;
                right=max;
                while(right-left>1){
                    md=getsum((right+left)/2);
                    if(md>num1){
                        right=(right+left)/2;
                    }
                    else if(md<num1){
                        left=(right+left)/2;
                    }
                    else {
                        if(a[(right+left)/2]){
                            cout<<(right+left)/2<<endl;
                            break;
                        }
                        else
                            right=(right+left)/2;
                    }
                }
                if(right-left<=1){
                    if(getsum(left)>=num1)
                        cout<<left<<endl;
                    else
                        cout<<right<<endl;
                }
            }
             
        }
    }
    return 0;
}

HDU 1828（Picture）经典求矩形的并周长

题目大意：给出对角线让您求所有矩形构成整体的并周长。

解题分析：这里跟求面积所要求的基本操作是一致的。对Y进行离散化，然后建树，树节点里比起求并面积的多了几个域，一个是记录左右端点被覆盖的次数lb,rb，一个是记录区间内连续子段的个数。

通过上面的记录更新我们可以这样计算：

1）通过Y的长度就是，把这次在Y轴上的投影与上次的取差的绝对值，这就是它在Y上面的增量，把这些增量求和，这样就解决了Y上的周长问题！

2）因为线段树的节点里已经计算出目前该区间的连续子区间的个数，所以在这里就可以计算周长在X上的长度，因为Y上的段树就表明有该区间X的元线段要计算多少次，计算公式：sum+=2*(t[i].x-t[i-1].x)*lastn;在这里lastn表示上一次计算出的Y上投影的区间个数，也就是我这次计算所涉及的！

代码程序如下：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
int ym[10200];//注意区间要开大点 不然RE
 
struct Tree{
    int li,ri,lb,rb;//li,ri左右端点的值
    int lenth,ans,cover;//lenth表示被覆盖至少一次的长度
       //ans记录子区间个数,lb,rb记录左右端点被覆盖次数
       //cover记录整个区间被覆盖的次数
}s[50000];
 
struct node{
    int x,y1,y2;
    int flag;
}t[50000];//表示左，右边的节点
 
int cmp1(int x,int y){
    return x<y;
}
 
int cmp2(struct node st,struct node sd){
    if(st.x!=sd.x)
        return st.x<sd.x;
    else
        return st.flag>sd.flag;
            //这里要非常注意，因为要计算并周长，
          //当两个边x一样的时候，要将左边先插入！
}
 
int len(int num){
    if(s[num].cover>0)
        s[num].lenth=s[num].ri-s[num].li;
    else
        s[num].lenth=s[num+num].lenth+s[num+num+1].lenth;
}
 
int slen(int num){
    if(s[num].cover>0)
        s[num].ans=1;
    else {
        s[num].ans=s[num+num].ans+s[num+num+1].ans;
        if(s[num+num].rb!=0&&s[num+num+1].lb!=0)
            s[num].ans--;   
             //左子树的右端点如果跟右子树的左端点都被覆盖了
            //说明在整个区间里，有一个区间横跨左右子树，
           //但被重复计算了，所以要减去1！
    }
}
 
int Build(int x,int y,int num){
    s[num].li=ym[x];    s[num].ri=ym[y];
    s[num].lenth=0;
    s[num].cover=s[num].rb=s[num].lb=s[num].ans=0;
    if(x+1==y)
        return 0;
    int mid=(x+y)>>1;
    Build(x,mid,num+num);
    Build(mid,y,num+num+1);
}
 
int modify(int num,struct node st){
    if(st.y1==s[num].li)    s[num].lb+=st.flag;
    if(st.y2==s[num].ri)    s[num].rb+=st.flag;
    if(st.y1==s[num].li&&st.y2==s[num].ri){
        s[num].cover+=st.flag;
    }
    else{
        if(st.y1>=s[num+num].ri)
            modify(num+num+1,st);
        else if(st.y2<=s[num+num+1].li)
            modify(num+num,st);
        else{
            struct node sd=st;
            sd.y2=s[num+num].ri;
            modify(num+num,sd);
            sd=st;
            sd.y1=s[num+num+1].li;
            modify(num+num+1,sd);
        }
    }
    len(num);
    slen(num);
}
 
int main(){
    int cas,i,j;
    int x1,x2,y1,y2;
    int sum=0;
    while(scanf("%d",&cas)!=EOF){
        sum=0;
        for(j=1,i=1;i<=cas;i++,j+=2){
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            ym[j]=y1;
            t[j].x=x1;
            t[j].y1=y1;
            t[j].y2=y2;
            t[j].flag=1;
            ym[j+1]=y2;
            t[j+1].x=x2;
            t[j+1].y1=y1;
            t[j+1].y2=y2;
            t[j+1].flag=-1;
         
        }
        sort(ym+1,ym+j,cmp1);
        sort(t+1,t+j,cmp2);
        Build(1,j-1,1);
        int lastn=0,lasts=0;
              //lasts 表示上次Y上次的投影长度，lastn
              //表示Y上次的投影连续区间的个数
              //其实连续区间就是指图形从上到下有多少个不相连的部分
              //因为求周长，所以有多少个部分就要把X的区间长度
              //乘以这个区间个数，因为他们每个部分的上下边不重叠
        for(i=1;i<j;i++){
            modify(1,t[i]);
            sum+=abs(lasts-s[1].lenth);
            if(i!=1){
                sum+=lastn*(t[i].x-t[i-1].x)*2;
            }
            lastn=s[1].ans;
               //当初我答案一直错，检查了很久，最后终于发现是
              //把lastn=s[1].ans；放在了if语句里面，这样的话影响了第2次的计算。所以周长计算出来会有点偏小，因为我第二次的lastn还是=0，应该是等于1，呵呵
            lasts=s[1].lenth;
         
        }
        printf("%d\n",sum);
    }
}

HDU 1255 （覆盖的面积）典型的求交面积

题目大意：给对角线求覆盖次数至少为2次的面积

思路：首先把Y离散化，从小到大排序，然后以Y在数组种存放的位置，建树。但是线段树的lf,rf,存放的是Y的实际值，这就是离散化。

然后在节点里用cover记录被覆盖的次数，lenth表示至少被覆盖一次的区间长度,inlenths,记录被覆盖两次以上的区间长度，这里比起求矩形的并面积，就是多了个记录与更新至少覆盖两次的情况的操作！
建树：跟求区间的并区别不大，就是多了一个对inlenths的初始化。

更新：从上到下遍历，找到需要更新区间，如果是矩形的左边，cover加1，表示在这个高度，多了个区间覆盖在其之上，如果是矩形的右边则减1，说明，少了个区间覆盖在这个高度范围内，也就是矩形的覆盖，更新当前区间的lenth,如果cover>0则lenth等于该区间的整体长度，否则等于左右子树的覆盖长度，然后更新inlenths的长度，当cover>2,表明这个高度有2个以上矩形覆盖，即把inlenths赋值为当前区间的整体长度，如果cover=1说明这个区间整体只被覆盖一次，那么inlenths的值就等于左右子区间被覆盖一次以上的长度，因为整体的已经被覆盖了一次，只有子区间有被覆盖过大于等于一次，那么该长度也被覆盖了2次以上！，最后当cover=0，那么说明这个区间没有整体被覆盖过，那么inlenths等于左右子区间的inlenths的长度！最后结束这次的遍历。如果没有到达更新区间，那么就分三种情况，在左子树，右子树，左右子树混合的情况，分别考虑，然后每次都会往上更新lenth和inlenths的值！

源程序代码+部分注释：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define esp (1e-8)
using namespace std;
double x_1,y_1,x_2,y_2,ym[30000],sum;
int i,j,n,cas;
struct tree{
    double lf,rf,lenth,inlenths;
    int cover;
}s[80000];
//这里数组开的小了当初，WA了好多次
//所以一气之下开的很大！
struct node{
    double x,y1,y2;
    int flag;
}t[30000];
 
void len(int num){
    if(s[num].cover>0)
        s[num].lenth=s[num].rf-s[num].lf;
    else
        s[num].lenth=s[num+num].lenth+s[num+num+1].lenth;
}
 
void inlen(int num){
    if(s[num].cover>1)//表示整个区间被覆盖次数大于等于2
        s[num].inlenths=s[num].rf-s[num].lf;
    else if(s[num].cover==1)
        s[num].inlenths=s[num+num].lenth+s[num+num+1].lenth;
                //整个区间只被覆盖一次，如果子区间有被覆盖大于等于1次，说明该子段的长度，
                //为被覆盖至少2次的长度
    else
        s[num].inlenths=s[num+num].inlenths+s[num+num+1].inlenths;
                //整个区间都没被覆盖，该区间覆盖2次以上的长度就等于
                //他左右子树被覆盖的长度的和
}
 
int cmp1(double a,double b){
    return a<b;
}
 
int cmp2(struct node a,struct node b){
    return a.x<b.x;
}
 
int Build(int x,int y,int num){
    s[num].lf=ym[x];
    s[num].rf=ym[y];
    s[num].cover=s[num].lenth=s[num].inlenths=0;
    if(x+1==y)
        return 0;
    int mid=(x+y)/2;
    Build(x,mid,num+num);
    Build(mid,y,num+num+1);
}
 
int modify(int num,struct node n){
    if(fabs(s[num].lf-n.y1)<=esp&&fabs(s[num].rf-n.y2)<=esp){
        s[num].cover+=n.flag;
        len(num);
        inlen(num);
        return 0;
    }
        //以下是分三种情况进行讨论
    if(n.y1>=s[num+num].rf)
        modify(num+num+1,n);
    else if(n.y2<=s[num+num+1].lf)
        modify(num+num,n);
    else{
        struct node sn=n;
        sn.y2=s[num+num].rf;
        modify(num+num,sn);
        sn=n;
        sn.y1=s[num+num+1].lf;
        modify(num+num+1,sn);
    }
    len(num);
    inlen(num);
}
 
int main(){
    scanf("%d",&cas);
    while(cas--){   
        sum=0;
        scanf("%d",&n);
        for(i=1,j=1;i<=n;i++,j+=2){
            scanf("%lf %lf %lf %lf", &x_1, &y_1, &x_2, &y_2);
            ym[j]=y_1;
            t[j].x=x_1;
            t[j].y1=y_1;
            t[j].y2=y_2;
            t[j].flag=1;
            ym[j+1]=y_2;
            t[j+1].x=x_2;
            t[j+1].y1=y_1;
            t[j+1].y2=y_2;
            t[j+1].flag=-1;
        }
        sort(ym+1,ym+j,cmp1);
        sort(t+1,t+j,cmp2);
        Build(1,j-1,1);
        modify(1,t[1]);
        for(i=2;i<j;i++){
            sum+=s[1].inlenths*(t[i].x-t[i-1].x);
            modify(1,t[i]);
        }
        printf("%.2lf\n",sum);
              //在我的编译器上好像样例的答案为7.62但是可以过
              //我不知道有没有更好的办法能够四舍五入保留两位小数
    }
    return 0;

继续阅读

HDU 1542 Atlantis（线段的树应用——求矩形的面积并）

题目大意：给定每个矩形的对角线的两个端点，让你求这些矩形的面积的并集，即重叠的不能重复计算！

题目分析：这题就是典型的线段树求面积并！

离散化：对所有节点的Y进行升序排序，然后以Y的位置建树，就是指，在线段树里面，左右节点的实际意义就是指这个线段在Y的升序数组里的位置，但是我们把lf,rf赋值为这个线段左右端点的具体值！这就是离散化！

建树的细节：树的每个节点有lf,rf,cover,lenth，分别指这个节点所表示的线段的左端点，右端点，被覆盖的次数（在这里覆盖的次数是为了区分重叠矩形的情况下，高度的正确存取，因为一个矩形对Y轴的覆盖是以他的左边开始，右边结束的，所以当插入左边的时候，我们把cover+1，右边的时候把cover-1，说明这个矩形对Y的覆盖已经结束，计算下一个矩形时，不会错误的把我这个矩形的高度当作下一个矩形的高度！），lenth指这个区间被矩形覆盖的长度即矩形的实际高度！；

插入的时候，先把存放节点的数组，对X进行升序排序！然后顺次插入，分别计算！

代码如下+部分注释：

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
 
struct tree{
    double lf,rf,lenth;
    int cover;
}s[4000];//树节点定义
 
double x1,y1,x2,y2,ym[1000];
 
struct node{
    double x,y1,y2;
    int flag;
}t[4000];//存放矩形左，右边的节点
 
int cmp1(double x,double y){
    return x<y;
}
 
int cmp2(struct node a,struct node b){
    return a.x<b.x;
}
 
void len(int n){
    if(s[n].cover>0)
        s[n].lenth=s[n].rf-s[n].lf;
    else
        s[n].lenth=s[2*n+1].lenth+s[2*n].lenth;
}
 
int Build(int x,int y,int num){
    s[num].lf=ym[x];
    s[num].rf=ym[y];
    s[num].lenth=s[num].cover=0;
    if(x+1==y)
        return 0;
    int mid=(x+y)/2;
    Build(x,mid,num+num);
    Build(mid,y,num+num+1);
}
 
int modify(int num,struct node n){
    if(s[num].lf==n.y1&&s[num].rf==n.y2){
        s[num].cover+=n.flag;
        len(num);
        return 0;
    }
    if(n.y1>=s[num+num].rf)
        modify(num+num+1,n);
    else if(n.y2<=s[num+num+1].lf)
        modify(num+num,n);
    else{
        struct node vs=n;
        vs.y2=s[num+num].rf;
        modify(num+num,vs);
        vs=n;
        vs.y1=s[num+num+1].lf;
        modify(num+num+1,vs);
    }
    len(num);//往上更新线段被覆盖的实际长度！如果节点的cover>0 该区间节点的被覆盖就是，区间的整体程度，否则，该区间节点的被覆盖等于左右节点被覆盖长度的和！
}
 
int main(){
    int cas,i,j,k=1;
    double sum;
    while(cin>>cas,cas){
        for(j=i=1;i<=cas;i++,j+=2){
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
            ym[j]=y1;
            t[j].x=x1;
            t[j].y1=y1;
            t[j].y2=y2;
            t[j].flag=1;
            ym[j+1]=y2;
            t[j+1].x=x2;
            t[j+1].y1=y1;
            t[j+1].y2=y2;
            t[j+1].flag=-1;
        }
        sort(ym+1,ym+j,cmp1);
        sort(t+1,t+j,cmp2);
        Build(1,j-1,1);
        modify(1,t[1]);
        sum=0;
        for(i=2;i<j;i++){
            sum+=(t[i].xt[i-1].x)*s[1].lenth;
                      //每插入完一个点，就以他后继的点求面积！
            modify(1,t[i]);
        }
        printf("Test case #%d\n",k);
        printf("Total explored area: %.2lf\n\n",sum);
        k++;
    }
    return 0;
}

POJ 2528（Mayor's posters）经典线段树问题

题目大意：给出N个海报的左右边界，然后按顺序贴完这些海报，要求计算没有完全被覆盖的海报的张数。

题目分析：首先离散化：按顺序用数组把左右边界存起来，然后升序排序，去除重复出现的，最后用左右边界在该数组出现的位置作为左右边界的值；还有一个就是，计算的时候可以当作一个染色过程，倒着染，您可以自己想想一下，这样才能够使得结果不被后面的染色操作干扰，不是么！因为后面计算的都是先贴的，根本不会对我产生影响的！

100

101

102

103

104

105

106

107

108

109

110

111

112

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define MAX 10005
using namespace std;
 
struct node{
    int a,b,color,flag;
}s[8*MAX];
 
struct st{
    int x,y;
}t[2*MAX];
 
int N[2*MAX],vs[2*MAX],sim[4*MAX],times,ans;
 
int cmp(int a,int b){
    return a<b;
}
 
int getidex(int y){
    int i=1,j=times+1,mid;
    while(i<=j){
        mid=(i+j)/2;
        if(N[mid]==y)   return mid;
        if(N[mid]>y) j=mid;
        else i=mid+1;
    }
    return 0;
}
 
int Build(int x,int y,int num){
    s[num].color=0;
    s[num].flag=0;
    s[num].a=x; 
    s[num].b=y;
    if(x==y)
        return 0;
    int mid=(x+y)/2;
        Build(x,mid,num+num);
        Build(mid+1,y,num+num+1);
}
 
int modify(int x,int y,int num,int color){
    if(s[num].color>0) //说这个区间会被覆盖，不用再讨论了！
        return 0;
    if(x==s[num].a&&y==s[num].b){//找到查询区间
        if(s[num].flag==0){//判断是否被完全覆盖
            s[num].color=color;
            s[num].flag=1;//染色
            if(!vs[color]){//如果这个颜色没有出现过，计数！
                               //先前我这里忘记考虑了，其实这个也许是这次查询的一个子区间
                              //这里是对其中一个子区间进行染色，计数，当然，其他的子区间肯定也染色！
                              //但是计数只需要一次！！
                ans++;
                vs[color]=1;
            }
        }
        return 0;
    }
    int mid=(s[num].a+s[num].b)/2;
    if(y<=mid)
        modify(x,y,num+num,color);
    else if(x>mid)
        modify(x,y,num+num+1,color);
    else{
        modify(x,mid,num+num,color);
        modify(mid+1,y,num+num+1,color);
    }
        //重点注意一下这里：如果左右子树都被染色了
        //很显然要往上更新父亲节点的染色状态即flag!
    if(s[num+num].flag&&s[num+num+1].flag)
        s[num].flag=1;
}
 
int main(){
    int cas,n,i,j;
    scanf("%d",&cas);
    while(cas--){
        memset(vs,0,sizeof(vs));
        ans=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d%d",&t[i].x,&t[i].y);
                //把左右边界的存放在sim[]里面一边，以便下面的离散操作！
        for(i=1;i<=n;i++){
            sim[i]=t[i].x;
        }
        for(i=n+1,j=1;j<=n;j++,i++){
            sim[i]=t[j].y;
        }
        sort(sim+1,sim+1+2*n,cmp);//升序排序
                //去除重复的边界值
        N[1]=sim[1];
        times=1;
        for(i=2;i<=2*n;i++){
            if(N[times]!=sim[i])
                N[++times]=sim[i];
        }
        Build(1,times,1);
        int color=0;
        for(i=n;i>=1;i--){
            int sx=getidex(t[i].x);
                 //以边界值在sim[]里面的位置，作为当前的边界值，这就是离散的核心思想！
            int sy=getidex(t[i].y);
            modify(sx,sy,1,++color);
        }
        printf("%d\n",ans);
    }
    return 0;
}