Photo by Mohsin khan from Pexels ### 前言

线段树的专题事实上早就已经刷完了，然而一直拖到现在才写题解......

bin巨的线段树专题主要包括以下几个方面：

• 线段树维护和、区间和、立方和、最大值、最小值
• 线段树与染色问题
• 区间合并
• 扫描线

正文

HDU1166 敌兵布阵

题意是说，现在有N个数，三种操作，这三种操作分别是：

• Add i j，表示在第\(i\)个数\(a_i\)上加上\(j\)
• Sub i j，表示在第\(i\)个数\(a_i\)上减去\(j\)
• Query i j，表示询问区间\([i,j]\)的总和

典型的单点修改区间查询。直接套线段树模板即可。sub操作可以通过add上相反数实现。

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=50005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int sum[maxn<<2];
int arr[maxn];
void push_up(int rt)
{
    sum[rt]=sum[rt<<1|1]+sum[rt<<1];
}
void build(int lef,int rig,int rt)
{
    if(lef==rig){
        scanf("%d",&sum[rt]);
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int pos,int todo,int lef,int rig,int rt)
{
    if(lef==rig){
        sum[rt]+=todo;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(pos<=mid)
        update(pos,todo,lson);
    else
        update(pos,todo,rson);
    push_up(rt);
}
int query(int L,int R,int lef,int rig,int rt)
{
    if(L<=lef&&R>=rig)
        return sum[rt];
    int mid=lef+(rig-lef)/2;
    int ret=0;
    if(L<=mid)
        ret+=query(L,R,lson);
    if(R>mid)
        ret+=query(L,R,rson);
    return ret;
}
int main()
{
    int t;
    int kase=0;
    scanf("%d",&t);
    getchar();
    while(t--){
        printf("Case %d:\n",++kase);
        mst(arr,0);mst(sum,0);
        int n;
        scanf("%d",&n);
        getchar();
//        for(int i=1;i<=n;i++)
//            scanf("%d",&arr[i]);
        build(1,n,1);
        getchar();
        while(1){
            char str[15];int a,b;
            scanf("%s",str);
            getchar();
            if(str[0]=='E')        break;
            scanf("%d %d",&a,&b); 
            getchar();
            if(str[0]=='Q'){
                int ans=query(a,b,1,n,1);
                printf("%d\n",ans);
            }else if(str[0]=='A'){
                update(a,b,1,n,1);
            }else if(str[0]=='S'){
                update(a,-b,1,n,1);
            }
        }
    }
    return 0;
} 

HDU1754 I Hate It

题意是查询区间最大值，同时还要有修改操作。线段树维护区间最大值即可。

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define IOS std::ios::sync_with_stdio(false)
const int maxn=200000+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int maxi[maxn<<2];
void pushup(int rt)
{
    maxi[rt]=max(maxi[rt<<1],maxi[rt<<1|1]);
}
void build(int lef,int rig,int rt)
{
    if(lef==rig){
        int tmp;scanf("%d",&tmp);
        maxi[rt]=tmp;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
    return ;
}
void update(int pos,int val,int lef,int rig,int rt)
{
    if(lef==rig){
        maxi[rt]=val;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(pos<=mid)
        update(pos,val,lson);
    else
        update(pos,val,rson);
    pushup(rt);
    return ;
}
int ans;
void query(int L,int R,int lef,int rig,int rt)
{
    if(L<=lef&&rig<=R){
        ans=max(ans,maxi[rt]);
        return ;    
    }
    int mid=lef+(rig-lef)/2;
    if(L<=mid)
        query(L,R,lson);
    if(R>mid)
        query(L,R,rson);
    return ;
}
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        build(1,n,1);
        ans=-1;
//        getchar();
        for(int i=0;i<m;i++){
            getchar();
            char op;scanf("%c",&op);
            int x,y;scanf("%d %d",&x,&y);
            if(op=='Q'){
                ans=-1;
                query(x,y,1,n,1);
                printf("%d\n",ans);
            }else if(op=='U'){
                update(x,y,1,n,1);    
            }
        }
    }
    return 0;
}

这题有多组样例...OTZ

POJ3468 A Simple Problem with integers

题意是说，有一串数字以及两种操作，一是为某一区间上的数都加上某个数，另一个操作是询问区间和。最简单的区间修改区间查询。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll sum[maxn<<2];
ll lazy[maxn<<2];
void pushup(ll rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(ll lef,ll rig,ll rt)
{
    sum[rt]=0;lazy[rt]=0;
    if(lef==rig){
//        cin>>sum[rt];
        scanf("%lld",&sum[rt]);
        return ;
    }
    ll mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
}
void pushdown(ll rt,ll len)
{
    if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=lazy[rt]*(len-(len>>1));
        sum[rt<<1|1]+=lazy[rt]*(len>>1);
        lazy[rt]=0; 
    }
}
void update(ll toL,ll toR,ll todo,ll lef,ll rig,ll rt)
{
    if(toL<=lef&&toR>=rig){
        lazy[rt]+=todo;
        sum[rt]+=todo*(rig-lef+1); 
        return ;
    }
    pushdown(rt,rig-lef+1);
    ll mid=lef+(rig-lef)/2;
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    pushup(rt);
}
ll query(ll toL,ll toR,ll lef,ll rig,ll rt)
{
    if(toL<=lef&&toR>=rig){
        return sum[rt];
    }
    pushdown(rt,rig-lef+1);
    ll mid=lef+(rig-lef)/2;
    ll ans=0; 
    if(toL<=mid)
        ans+=query(toL,toR,lson);
    if(toR>mid)
        ans+=query(toL,toR,rson);
    return ans;
        
}
int main()
{
//    std::ios::sync_with_stdio(false);
    ll n,q;
    scanf("%lld %lld",&n,&q);
    build(1,n,1);
    for(int i=0;i<q;i++){
        char op;cin>>op;
        if(op=='Q'){
            ll L,R;
            scanf("%lld %lld",&L,&R);
            ll ans=query(L,R,1,n,1);
            printf("%lld\n",ans);
        }else if(op=='C'){
            ll L,R,to;
            scanf("%lld %lld %lld",&L,&R,&to);
            update(L,R,to,1,n,1);
        }
    }
    return 0;
} 

POJ2528 Mayor's posters

已写题解，不再赘述

Mayor's poster

HDU1698 Just a Hook

就是区间修改区间查询。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int lazy[maxn<<2];
int sum[maxn<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int len)
{
    if(lazy[rt]!=0){
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        sum[rt<<1]=(len-(len>>1))*lazy[rt];
        sum[rt<<1|1]=(len>>1)*lazy[rt];
        lazy[rt]=0;
    }
    return ;
}
void build(int lef,int rig,int rt)
{
    sum[rt]=0;
    if(lef==rig){
        sum[rt]=1;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
    if(toL<=lef&&toR>=rig){
        lazy[rt]=todo;
        sum[rt]=(rig-lef+1)*todo;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    pushdown(rt,rig-lef+1);
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    pushup(rt);
}
int query(int toL,int toR,int lef,int rig,int rt)
{
    if(toL<=lef&&toR>=rig){
        return sum[rt];
    }
    int mid=lef+(rig-lef)/2;
    pushdown(rt,rig-lef+1);
    int ret=0;
    if(toL<=mid)
        ret+=query(toL,toR,lson);
    if(toR>mid)
        ret+=query(toL,toR,rson);
    return ret; 
}
int main()
{
//    std::ios::sync_with_stdio(false);
    int t;scanf("%d",&t);
    int kase=0;
    while(t--){
        mst(lazy,0);mst(sum,0);
        int n;scanf("%d",&n);
        build(1,n,1);
//        debug;
        int q;scanf("%d",&q);
//        debug;
        for(int i=0;i<q;i++){
//            debug;
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            update(x,y,z,1,n,1);
        }
        int ans=query(1,n,1,n,1);
        printf("Case %d: The total value of the hook is %d.\n",++kase,ans);
    }
    return 0;
}

ZOJ1610 Count the Colors

依然是染色问题。题意是说，在一条直线上涂色，颜色与颜色之间可以相互覆盖，问最终可以看到的颜色有多少。

与贴海报那题思路几乎一样。只需要用个\(cnt[]\)数组记录一下颜色个数即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
const int maxn=8005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int lazy[maxn<<2];
int cnt[maxn];
struct node{
    int lef;
    int rig;
    int to;
};
node ns[8005];
void pushdown(int rt)
{
    if(lazy[rt]!=-1){
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        lazy[rt]=-1;
    }
    return ;
}
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
    if(toL<=lef&&toR>=rig){
        lazy[rt]=todo;
        return ;
    }
    pushdown(rt);
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    return ;
}
int tag=-1;
void query(int lef,int rig,int rt)
{
    if(lef==rig){
        if(lazy[rt]!=-1&&lazy[rt]!=tag){
            cnt[lazy[rt]]++;
        }
        tag=lazy[rt];
        return ;
    }
    pushdown(rt);
    int mid=lef+(rig-lef)/2;
    query(lson);
    query(rson);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int max_id=-1;
        int range=-1;
        mst(lazy,-1);mst(cnt,0);
        for(int i=0;i<n;i++){
            int lef,rig,to;
            scanf("%d %d %d",&ns[i].lef,&ns[i].rig,&ns[i].to);
            range=max(range,ns[i].rig); 
            max_id=max(max_id,ns[i].to);
        } 
        for(int i=0;i<n;i++)
            update(ns[i].lef+1,ns[i].rig,ns[i].to,0,range,1);
        query(0,range,1);
        for(int i=0;i<=max_id;i++)
            if(cnt[i]!=0)
                printf("%d %d\n",i,cnt[i]);
        printf("\n");
    }
    return 0;
}

POJ3264 Balanced Lineup

线段树维护区间最大值和最小值

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
const int maxn=8005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int lazy[maxn<<2];
int cnt[maxn];
struct node{
    int lef;
    int rig;
    int to;
};
node ns[8005];
void pushdown(int rt)
{
    if(lazy[rt]!=-1){
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        lazy[rt]=-1;
    }
    return ;
}
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
    if(toL<=lef&&toR>=rig){
        lazy[rt]=todo;
        return ;
    }
    pushdown(rt);
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    return ;
}
int tag=-1;
void query(int lef,int rig,int rt)
{
    if(lef==rig){
        if(lazy[rt]!=-1&&lazy[rt]!=tag){
            cnt[lazy[rt]]++;
        }
        tag=lazy[rt];
        return ;
    }
    pushdown(rt);
    int mid=lef+(rig-lef)/2;
    query(lson);
    query(rson);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int max_id=-1;
        int range=-1;
        mst(lazy,-1);mst(cnt,0);
        for(int i=0;i<n;i++){
            int lef,rig,to;
            scanf("%d %d %d",&ns[i].lef,&ns[i].rig,&ns[i].to);
            range=max(range,ns[i].rig); 
            max_id=max(max_id,ns[i].to);
        } 
        for(int i=0;i<n;i++)
            update(ns[i].lef+1,ns[i].rig,ns[i].to,0,range,1);
        query(0,range,1);
        for(int i=0;i<=max_id;i++)
            if(cnt[i]!=0)
                printf("%d %d\n",i,cnt[i]);
        printf("\n");
    }
    return 0;
}

HDU4027 Can you answer these queries?

题意是说，现在有一正整数序列，还有两种操作，第一种是可以将某一区间内的整数变为其自身的平方根；第二种操作是询问区间和。

注意本题有一个条件，“Notice that the square root operation should be rounded down to integer.”，因此，当某次操作后，如果某个数的结果小于1，那它就直接变成0了！这就给了我们一个解题的思路：这题我们可以一直走到叶子节点再进行平方根操作，对于那些已经为0的数，就可以将它们记录下来，下次操作的时候就可以不用操作这个数了！由此降低复杂度。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=100000+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll sum[maxn<<2];
bool flag[maxn<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    flag[rt]=0;
    if(flag[rt<<1]&&flag[rt<<1|1])
        flag[rt]=1;
    return ;
}
void build(int lef,int rig,int rt)
{
    if(lef==rig){
        scanf("%lld",&sum[rt]);
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
    return ;
}
void update(int toL,int toR,int lef,int rig,int rt)
{
    if(flag[rt])
        return ;
    if(lef==rig){
        sum[rt]=(ll)sqrt(sum[rt]);
        if(sum[rt]<=1)        
            flag[rt]=1;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(toL<=mid) 
        update(toL,toR,lson);
    if(toR>mid)    
        update(toL,toR,rson);
    pushup(rt);
    return ;
}
ll ans=0;
void query(int toL,int toR,int lef,int rig,int rt)
{
    if(toL<=lef&&rig<=toR){
        ans+=sum[rt];
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        query(toL,toR,lson);
    if(toR>mid)
        query(toL,toR,rson);
    return ;
}
int main()
{
    int n;int kase=0;
    while(scanf("%d",&n)!=EOF){
        mst(flag,0);
        build(1,n,1);
        int t;scanf("%d",&t);
        printf("Case #%d:\n",++kase);
        while(t--){
            int op,l,r;
            scanf("%d %d %d",&op,&l,&r);
            if(l>r)
                swap(l,r);
            if(op==0){
                update(l,r,1,n,1);
            }else if(op==1){
                ans=0;
                query(l,r,1,n,1);
                printf("%lld\n",ans);
            }
        }
        printf("\n");
    }
    return 0;
}

HDU1540 Tunnel Warfare

地道战。

题意是说，有一系列的村庄，除了末端的两个村庄以外，其他的都与相邻的两个连接形成一条线。现在有三种操作，一种是摧毁第\(x\)个村庄；一种是询问有多少个村庄与第\(x\)个村庄直接或间接连接；还有一种是将最后被摧毁的村庄修复，意味着该村庄与其邻近两个村庄的连接重新建立。

这题的正解是区间合并，但有一种很巧妙的做法：用线段树维护区间最大值和最小值。对于最大值，一开始初始化每个村庄都为0；对于最小值，初始化每个村庄都为INF。摧毁的时候，如果要摧毁第\(x\)个村庄，只需要将对应的maxi[rt]改为\(x\)，对应的mini[rt]也改为\(x\)即可。查询的时候，对于第\(x\)个村庄，查询区间\([1,x-1]\)的最小值\(mini\_val\)，再查询区间\([x,n]\)的最大值\(mini\_val\)，答案就是\(mini\_val-maxi\_val-1\)。而对于修复操作，只需要将对应的maxi[rt]改回0，mini[rt]改回INF即可。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=50000+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mini[maxn<<2];
int maxi[maxn<<2];
int n;
void pushup(int rt)
{
    mini[rt]=min(mini[rt<<1],mini[rt<<1|1]);
    maxi[rt]=max(maxi[rt<<1],maxi[rt<<1|1]);
}
void build(int lef,int rig,int rt)
{
    if(lef==rig){
        mini[rt]=n+1;
        maxi[rt]=0;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
}
void update_max(int pos,int todo,int lef,int rig,int rt)
{
    if(lef==rig){
        maxi[rt]=todo;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(pos<=mid)
        update_max(pos,todo,lson);
    if(pos>mid)
        update_max(pos,todo,rson);
    maxi[rt]=max(maxi[rt<<1],maxi[rt<<1|1]);
}
void update_min(int pos,int todo,int lef,int rig,int rt)
{
    if(lef==rig){
        mini[rt]=todo;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(pos<=mid)
        update_min(pos,todo,lson);
    if(pos>mid)
        update_min(pos,todo,rson);
    mini[rt]=min(mini[rt<<1],mini[rt<<1|1]);
}
int min_val=INF;
int max_val=-1;
void query_max(int toL,int toR,int lef,int rig,int rt)
{
    if(toL<=lef&&rig<=toR){
        max_val=max(max_val,maxi[rt]);
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        query_max(toL,toR,lson);
    if(toR>mid)
        query_max(toL,toR,rson);
    return ;
}
void query_min(int toL,int toR,int lef,int rig,int rt)
{
    if(toL<=lef&&rig<=toR){
        min_val=min(min_val,mini[rt]);
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        query_min(toL,toR,lson);
    if(toR>mid)
        query_min(toL,toR,rson);
    return ;
}
int stk[maxn];
int main()
{
    int m;
     while(scanf("%d %d",&n,&m)!=EOF){
         getchar();int cnt=0;
         mst(stk,0);
         build(1,n,1);
         for(int i=0;i<m;i++){
             max_val=-2;min_val=INF;
            char op;cin>>op;
//            getchar();getchar();
            if(op=='D'){
                int a;scanf("%d",&a);
                stk[cnt++]=a;
                update_max(a,a,1,n,1);
                update_min(a,a,1,n,1);
            }else if(op=='Q'){
                int a;scanf("%d",&a);
                query_max(1,a,1,n,1);
                query_min(a,n,1,n,1);
//                cout<<"max:"<<max_val<<" "<<"min:"<<min_val<<endl; 
//                if(min_val==50001)        min_val=n+1;
//                if(max_val==-1)        max_val=1;
                int ans=min_val-max_val-1;
                if(min_val==max_val)        ans=0;
                printf("%d\n",ans);
            }else if(op=='R'){
                int tmp=stk[--cnt];
                update_max(tmp,0,1,n,1);
                update_min(tmp,n+1,1,n,1);
            }
        }
    }
    return 0;
}

然而本题的正解我却没有写hhhh，先挖个坑，到时再补

HDU3974 Assign the task

题意是说，一个公司有N个员工，每个员工都有一个直接的上司。叶子节点没有下属，树根没有上司。当上司收到工作后，上司会将这份工作下发给他的所有下属，包括不直属的下属。下属在收到一份新的工作后，会马上停止手头上的工作开始新的工作。问，当前某个员工的工作是什么。

先用dfs序将树转为线性区间，就转化为单点查询区间修改的问题了，可以直接用线段树来搞。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=50010;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int in[maxn];
int out[maxn];
vector<int> gra[maxn];
int tree[maxn<<3];
int len=0;
bool vis[maxn];
int id=1;
void dfs(int u)        //id从1开始 
{
    len++;
    in[u]=id++;        //记录一下入栈时间 
    for(int i=0;i<gra[u].size();i++){
        dfs(gra[u][i]);
    }
    out[u]=id++;    //记录一下出栈时间 
    len++;
}
void build(int lef,int rig,int rt)
{
    tree[rt]=-1;
    if(lef==rig){
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
}
void pushdown(int rt)
{
    if(tree[rt]!=-1){
        tree[rt<<1]=tree[rt];
        tree[rt<<1|1]=tree[rt];
        tree[rt]=-1;
        return ;
    }
    return ;
}
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
    if(toL<=lef&&rig<=toR){
        tree[rt]=todo;
        return ;
    }
    pushdown(rt);
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    return ;
}
int ans;
void query(int pos,int lef,int rig,int rt)
{
    if(lef==rig){
        ans=tree[rt];
        return ;
    }
    int mid=lef+(rig-lef)/2;
    pushdown(rt);
    if(pos<=mid)
        query(pos,lson);
    if(pos>mid)
        query(pos,rson);
    return ;
}
int main()
{
//    freopen("data_generator.txt","r",stdin);
    int t;scanf("%d",&t);
    int kase=0;
    while(t--){
        printf("Case #%d:\n",++kase);
        ans=0;id=1;
        mst(vis,0);
        mst(in,0);mst(out,0);
        int n;scanf("%d",&n);
        build(1,2*n,1);
        for(int i=0;i<n-1;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            gra[v].push_back(u);
            vis[u]=1;        //用来记录节点u是否是别人的儿子 
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i);
                break;
            }
        }
        int m;scanf("%d",&m);
//        getchar();
        for(int i=0;i<m;i++){
            char op;cin>>op;
//            char tmp=getchar();
            if(op=='C'){
                int x;scanf("%d",&x);
                query(in[x],1,2*n,1);
                printf("%d\n",ans);    
            }else if(op=='T'){
                int x,y;scanf("%d %d",&x,&y);
                update(in[x],out[x],y,1,2*n,1);    
            }
        }
        for(int i=1;i<=n;i++)
            gra[i].clear();
    }
    return 0;
}

HDU4578 Transformation

题意是说，现在有\(n\)个整数\(a_1,a_2,a_3,...,a_n\)，初始值都为0。有以下四种操作：

• 对\(a_x\)到\(a_y\)的数，分别都加上\(c\)。

• 对\(a_x\)到\(a_y\)的数，分别都乘上\(c\)。

• 将\(a_x\)到\(a_y\)的数，都改为\(c\)。

• 求\(a_x\)到\(a_y\)的数的\(p\)次幂的总和。即\(a_x^p+a_{x+1}^p+a_{x+2}^p+...+a_{y}^p\)。其中，\(0 \lt p \lt 4\)，\(p\)是整数。

  这是一道比较复杂的题目，难点在于怎么维护\(p\)次幂的区间和，以及加操作与乘操作之间的相互影响怎么处理。事实上根据以下两条式子来维护三次方和以及二次方和即可： \[ (x+c)^3=x^3+3cx^2+3c^2x+c^3 \\ (x+c)^2=x^2+2cx+c^2 \] 具体的看代码注释吧。

  代码如下

  #include <cstdio>
  #include <iostream>
  #include <cstring>
  #include <cmath>
  #include <algorithm>
  #include <vector>
  #include <list>
  #include <set>
  #include <map>
  #include <cctype>
  #include <string>
  #include <queue>
  #define mst(a,b) memset((a),(b),sizeof(a))
  #define debug printf("debug\n")
  #define INF 0x3f3f3f3f
  #define lson lef,mid,rt<<1
  #define rson mid+1,rig,rt<<1|1
  const int maxn=1e5+5;
  using namespace std;
  typedef long long ll;
  typedef unsigned long long ull;
  ll mod=10007;
  ll sum1[maxn<<2];        //区间和 
  ll sum2[maxn<<2];        //区间平方和 
  ll sum3[maxn<<2];        //区间立方和
  ll lazy_add[maxn<<2];
  ll lazy_mul[maxn<<2];
  ll lazy_set[maxn<<2];
  void push_up(int rt)
  {
      sum1[rt]=(sum1[rt<<1]+sum1[rt<<1|1])%mod;
      sum2[rt]=(sum2[rt<<1]+sum2[rt<<1|1])%mod;
      sum3[rt]=(sum3[rt<<1]+sum3[rt<<1|1])%mod; 
  }
  void build(int lef,int rig,int rt)
  {
      sum1[rt]=sum2[rt]=sum3[rt]=0;
      lazy_add[rt]=0;
      lazy_mul[rt]=1;
      lazy_set[rt]=0;
      if(lef==rig){
  //        sum1[rt]=sum2[rt]=sum3[rt]=0;
          return ;
      }
      int mid=lef+(rig-lef)/2;
      build(lson);
      build(rson);
      push_up(rt);
  }
  void push_down(int rt,int len)
  {
      if(lazy_set[rt]!=0){
          lazy_add[rt<<1]=lazy_add[rt<<1|1]=0;        
          lazy_mul[rt<<1]=lazy_mul[rt<<1|1]=1;
          lazy_set[rt<<1]=lazy_set[rt<<1|1]=lazy_set[rt];
          ll tmp=(lazy_set[rt]*(lazy_set[rt]%mod)*(lazy_set[rt]%mod))%mod;
          sum3[rt<<1]=((len-(len>>1))*tmp)%mod;
          sum3[rt<<1|1]=((len>>1)*tmp)%mod;
  
          sum2[rt<<1]=((len-(len>>1))*((lazy_set[rt]%mod)*(lazy_set[rt]%mod)))%mod;
          sum2[rt<<1|1]=((len>>1)*((lazy_set[rt]%mod)*(lazy_set[rt]%mod)))%mod;
  
          sum1[rt<<1]=((len-(len>>1))*(lazy_set[rt]%mod))%mod;
          sum1[rt<<1|1]=((len>>1)*(lazy_set[rt]%mod))%mod;
  
          lazy_set[rt]=0;
      }
      if(lazy_add[rt]!=0||lazy_mul[rt]!=1){
          ll add=lazy_add[rt];ll mul=lazy_mul[rt];
          ll tmp=(mul*mul%mod*mul%mod)%mod;
  
          lazy_add[rt<<1]=(lazy_add[rt<<1]*mul%mod+add%mod)%mod;
          lazy_add[rt<<1|1]=(lazy_add[rt<<1|1]*mul%mod+add%mod)%mod;
          lazy_mul[rt<<1]=(lazy_mul[rt<<1]%mod*mul%mod)%mod;
          lazy_mul[rt<<1|1]=(lazy_mul[rt<<1|1]*mul%mod)%mod;
  
          sum3[rt<<1]=(sum3[rt<<1]*tmp%mod+add*add%mod*add%mod*(len-(len>>1))
                      +3*sum2[rt<<1]*mul*mul%mod*add%mod+3*sum1[rt<<1]*mul
                      *add%mod*add%mod)%mod;        //(x + c)^3 = x^3 + 3cx^2 + 3(c^2)x + c^3
          sum3[rt<<1|1]=(sum3[rt<<1|1]*tmp%mod+add*add%mod*add%mod*(len>>1)
                      +3*sum2[rt<<1|1]*mul*mul%mod*add%mod+3*sum1[rt<<1|1]*mul
                      *add%mod*add%mod)%mod;        //(x + c)^3 = x^3 + 3cx^2 + 3(c^2)x + c^3
  
          sum2[rt<<1]=(sum2[rt<<1]*mul*mul%mod+add*add%mod*(len-(len>>1))
                      +2*mul*add%mod*sum1[rt<<1]%mod)%mod;    //(x + c)^2 = x^2 + 2cx + c^2
          sum2[rt<<1|1]=(sum2[rt<<1|1]*mul*mul%mod+add*add%mod*(len>>1)
                      +2*mul*add%mod*sum1[rt<<1|1]%mod)%mod;    //(x + c)^2 = x^2 + 2cx + c^2
  
          sum1[rt<<1]=(sum1[rt<<1]*mul%mod+add%mod*(len-(len>>1)))%mod;
          sum1[rt<<1|1]=(sum1[rt<<1|1]*mul%mod+add%mod*(len>>1))%mod;
  
          lazy_add[rt]=0;lazy_mul[rt]=1;
      }
  }
  /*
  op==1:add 
  op==2:mul
  op==3:set
  */
  void update(int op,int toL,int toR,int todo,int lef,int rig,int rt)
  {
      if(toR<lef||toL>rig)        return ;
      if(toL<=lef&&toR>=rig){
          if(op==1){
              lazy_add[rt]=(todo+lazy_add[rt])%mod;
              sum3[rt]=(sum3[rt]+(todo*todo%mod*todo%mod*(rig-lef+1))
              +3*todo%mod*sum2[rt]%mod+3*todo*todo%mod*sum1[rt]%mod)%mod;
              //(x + c)^3 = x^3 + 3cx^2 + 3(c^2)x + c^3
              sum2[rt]=(sum2[rt]+(todo*todo%mod)*(rig-lef+1)
              +2*sum1[rt]%mod*todo%mod)%mod;
  
              sum1[rt]=(sum1[rt]+(rig-lef+1)*todo%mod)%mod;
          }else if(op==2){
              lazy_add[rt]=(lazy_add[rt]*todo)%mod;
              lazy_mul[rt]=(lazy_mul[rt]*todo)%mod;
              sum1[rt]=(todo*sum1[rt])%mod;
              sum2[rt]=(todo*todo%mod*sum2[rt])%mod;
              sum3[rt]=(todo*todo%mod*todo%mod*sum3[rt]%mod)%mod;
          }else if(op==3){
              lazy_add[rt]=0;
              lazy_mul[rt]=1;
              lazy_set[rt]=todo;
              sum3[rt]=(rig-lef+1)%mod*todo*todo%mod*todo%mod;
              sum2[rt]=(rig-lef+1)%mod*todo*todo%mod;
              sum1[rt]=(rig-lef+1)%mod*todo%mod;
          }
          return ;
      }
      int mid=lef+(rig-lef)/2;
      push_down(rt,rig-lef+1);
      if(toL<=mid)
          update(op,toL,toR,todo,lson);
      if(toR>mid)
          update(op,toL,toR,todo,rson);
      push_up(rt);
  }
  ll query(int p,int toL,int toR,int lef,int rig,int rt)
  {
      if(toL<=lef&&toR>=rig){
          if(p==1)
              return sum1[rt];
          else if(p==2)
              return sum2[rt];
          else if(p==3)
              return sum3[rt]; 
      }
      if(lef==rig)        return 0;
      int mid=lef+(rig-lef)/2;
      push_down(rt,rig-lef+1);
      ll ret=0;
      if(toL<=mid)
          ret+=query(p,toL,toR,lson);
      if(toR>mid)
          ret+=query(p,toL,toR,rson);
      return ret%mod;
  }
  //void update(int op,int toL,int toR,int todo,int lef,int rig,int rt)
  int main()
  {
  //    freopen("data_generator.txt","r",stdin);
  //    freopen("out_hdu4578.txt","w",stdout);
      int n,m;
      while(scanf("%d %d",&n,&m)!=EOF&&n&&m){
  //        mst(sum1,0);mst(sum2,0);mst(sum3,0);
  //        mst(lazy_add,0);mst(lazy_mul,0);mst(lazy_set,0);
          build(1,n,1);
          for(int i=0;i<m;i++){
              int type;
              scanf("%d",&type);
              int a,b,c;
              c%=mod; 
              scanf("%d %d %d",&a,&b,&c);
              if(type!=4){
                  update(type,a,b,c,1,n,1);
              }else{
                  ll ans=query(c,a,b,1,n,1);
                  ans%=mod;
                  printf("%lld\n",ans);
              }
          }
      }
      return 0;
  }

HDU4614 Vases and Flowers

题意是说，有若干个花瓶，有两种操作，分别是

• 从花瓶A开始放F朵花，如果某个花瓶已经有花了，就跳过这个花瓶。不断尝试花瓶，直至所有花都放完了，或者A以及A以后的花瓶都被尝试了一边。输出放第一朵花的位置以及放最后一朵花的位置。
• 第二种操作则是清楚区间内的花。并输出清除了多少花

思路是，空花瓶用1表示，线段树提供set操作，维护区间和。清空花瓶的操作很简单，只需要查询一下区间和，然后用区间长度减去区间和即可。对于放花的操作，可以用二分找到左边界和右边界。具体见代码及注释。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=50005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int lazy[maxn<<2];
int sum[maxn<<2];
int n,m;
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int lef,int rig,int rt)
{
    lazy[rt]=-1;
    if(lef==rig){
        sum[rt]=1;
        return ;
    }
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
    pushup(rt);
}
void pushdown(int rt,int len)
{
    if(lazy[rt]!=-1){
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        sum[rt<<1]=lazy[rt]*(len-(len>>1));
        sum[rt<<1|1]=lazy[rt]*(len>>1);
        lazy[rt]=-1;
    }
}
void update(int toL,int toR,int todo,int lef,int rig,int rt)        //进行set操作    //空花瓶用1表示 
{
    if(toL<=lef&&rig<=toR){
        lazy[rt]=todo;
        sum[rt]=(rig-lef+1)*todo;
        return ;
    }
    pushdown(rt,rig-lef+1);
    int mid=lef+(rig-lef)/2;
    if(toL<=mid)
        update(toL,toR,todo,lson);
    if(toR>mid)
        update(toL,toR,todo,rson);
    pushup(rt);
} 
int query(int toL,int toR,int lef,int rig,int rt)
{
    if(toL<=lef&&rig<=toR){
        return sum[rt];
    }
    int mid=lef+(rig-lef)/2;
    pushdown(rt,rig-lef+1);
    int ret=0;
    if(toL<=mid)
        ret+=query(toL,toR,lson);
    if(toR>mid)
        ret+=query(toL,toR,rson);
    return ret;
}
int binary(int L,int R,int num,int cnt)        //cnt为要找的空花瓶的数目 
{
    int ans=0;
    int mid=L+(R-L)/2;
    while(L<=R){
        mid=L+(R-L)/2;
        if(query(0,mid,0,n-1,1)-num>=cnt){
            R=mid-1;
            ans=mid;
        }else{
            L=mid+1;
        }
    }
    return ans;
}
int main()
{
    int t;cin>>t;
    while(t--){
        cin>>n>>m;
        build(0,n-1,1);
        for(int i=0;i<m;i++){
            int op;int x,y;
            cin>>op>>x>>y;
            if(op==1){
                int tot=query(x,n-1,0,n-1,1);
                if(tot==0){
                    printf("Can not put any one.\n");
                    continue;
                }
                if(tot<y)        y=tot;    //tot为从x开始最多能放的花的数目 
                int nu=0;
                if(x>=1)
                    nu=query(0,x-1,0,n-1,1);
                else
                    nu=0;        //此时x-1为负数，要特判一下 
                int lef=binary(x,n-1,nu,1);
                int rig=binary(x,n-1,nu,y);
                cout<<lef<<" "<<rig<<endl;
                update(lef,rig,0,0,n-1,1);
            }else{
                int ans=(y-x+1)-query(x,y,0,n-1,1);
                cout<<ans<<endl;
                update(x,y,1,0,n-1,1);        //1表示空花瓶 
            }
        }
        printf("\n");
    }
    return 0;
}

POJ1177 Picture

题目是让我们求若干个矩形重叠后形成的大矩形的周长。 扫描线题目，但一般来说扫描线都是用来求取重叠面积的，而此处是求取周长。线段树维护区间中被覆盖的长度以及区间中线段的数目。之所以要维护线段长度，是因为在计算矩形\(y\)方向上的周长时需要用到。每次update的时候根据线段树更新区间结果即可。 代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=20005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct seg{
    int lef,rig;
    int h;
    int tag;
    seg(){
    }
    seg(int lef,int rig,int h,int tag)
        :lef(lef),rig(rig),h(h),tag(tag){
        }
    bool operator<(const seg& se) const{
        return h<se.h;
    }
};
seg segs[5005*2];
struct node{        //表示一个区间 
    int lef,rig;    //左右端点 
    int len;        //被覆盖的长度 
    int cover_cnt;    //被覆盖的次数 
    bool lc,rc;        //左右端点是否被覆盖 
    int num;        //区间中线段数目 
    node(){
    }
};
node ns[maxn<<2];
void build(int lef,int rig,int rt)
{
    ns[rt].lef=lef;ns[rt].rig=rig;
    ns[rt].len=0;
    ns[rt].cover_cnt=ns[rt].lc=ns[rt].rc=0;
    ns[rt].num=0;
    if(lef==rig)
        return ;
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson); 
}
void pushup(int rt)
{
    if(ns[rt].cover_cnt){
        ns[rt].len=ns[rt].rig-ns[rt].lef+1;
        ns[rt].lc=ns[rt].rc=1;
        ns[rt].num=1;
    }else if(ns[rt].lef==ns[rt].rig){
        ns[rt].len=0;
        ns[rt].lc=ns[rt].rc=0;
        ns[rt].num=0;
    }else{
        int tmp=0;
        if(ns[rt<<1].rc&&ns[rt<<1|1].lc)
            tmp=1;
        ns[rt].len=ns[rt<<1].len+ns[rt<<1|1].len;
        ns[rt].num=ns[rt<<1].num+ns[rt<<1|1].num-tmp;        
        //当左儿子的右端点以及右儿子的左端点完全被覆盖时，中间会有一段被重复计算
        //的线段，故需要将其减去. 
        ns[rt].lc=ns[rt<<1].lc;ns[rt].rc=ns[rt<<1|1].rc;
    }
}
void update(int val,int lef,int rig,int rt)        //根据扫描线对线段树节点进行更新
//参数表中的lef和rig表示扫描线的左右端点 
{
//    cout<<"rt = "<<rt<<endl;
    if(lef==ns[rt].lef&&ns[rt].rig==rig){
        ns[rt].cover_cnt+=val;
        pushup(rt);
        return ;
    }
    int mid=(ns[rt].lef)+(ns[rt].rig-ns[rt].lef)/2;
    if(rig<=mid){
        update(val,lef,rig,rt<<1);
    }else if(lef>mid){
        update(val,lef,rig,rt<<1|1);
    }else{
        update(val,lef,mid,rt<<1);
        update(val,mid+1,rig,rt<<1|1);
    }
    pushup(rt);
}
int main()
{
    IOS;
    int n;cin>>n;
    int cnt=0;
    int ub=-INF;
    int lb=INF;
    for(int i=0;i<n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        segs[cnt++]=seg(x1,x2,y1,1);
        segs[cnt++]=seg(x1,x2,y2,-1);
        ub=max(ub,x2);
        lb=min(lb,x1);        
    }
    sort(segs,segs+cnt);
    build(lb,ub,1);
    int ans=0;int last=0;
    for(int i=0;i<cnt;i++){
        update(segs[i].tag,segs[i].lef,segs[i].rig-1,1);
        ans+=abs(ns[1].len-last);        //当前的ns[1].len包括上一次统计的区间长度,因此需要减去last 
        last=ns[1].len;
        ans+=(segs[i+1].h-segs[i].h)*2*ns[1].num;        //ns[1]为当前扫描线下区间的线段数目 
    }
    cout<<ans<<endl;
    return 0;
} 

HDU1255 覆盖的面积

扫描线计算被覆盖两次及以上的覆盖面积。\(cover\_cnt\)表示的是被完全覆盖的区间的长度。当一个区间被完全覆盖的次数大于等于2时，其二次覆盖长度就是其区间长度；当被完全覆盖的次数为1时，其二次覆盖长度为左儿子与右儿子的一次覆盖面积的和；若以上两种情况都不符合，那就由左儿子和右儿子的二次覆盖面积转移得到。

另外，这题需要离散化。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct seg{
    double lef,rig;
    double hei;
    int tag;
    seg(){}
    seg(double lef,double rig,double hei,int tag)
        :lef(lef),rig(rig),hei(hei),tag(tag){}
    bool operator<(const seg& se) const{
        return hei<se.hei;
    }
};
seg segs[maxn<<1];
struct node{        //线段树节点,表示一个区间
    int lef,rig;
    double len,len2;
    int cover_cnt;
    node(){}
    node(int lef,int rig)
        :lef(lef),rig(rig){
            len=0;cover_cnt=0;len2=0;
        }
};
node ns[maxn<<3];
double xs[maxn<<1];
void build(int lef,int rig,int rt)
{
    ns[rt].lef=lef;ns[rt].rig=rig;
    ns[rt].len=ns[rt].len2=0;
    ns[rt].cover_cnt=0;
    if(lef==rig)    return ;
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
}
void pushup(int rt)
{
    if(ns[rt].cover_cnt){
        ns[rt].len=xs[ns[rt].rig+1]-xs[ns[rt].lef];
    }else if(ns[rt].lef==ns[rt].rig){
        ns[rt].len=0;
    }else{
        ns[rt].len=ns[rt<<1].len+ns[rt<<1|1].len;
    }
    if(ns[rt].cover_cnt>=2){
        ns[rt].len2=xs[ns[rt].rig+1]-xs[ns[rt].lef];
    }else if(ns[rt].lef==ns[rt].rig){
        ns[rt].len2=0;
    }else if(ns[rt].cover_cnt==1){
        ns[rt].len2=ns[rt<<1].len+ns[rt<<1|1].len;
    }else{
        ns[rt].len2=ns[rt<<1].len2+ns[rt<<1|1].len2;
    }
}
void update(int val,int lef,int rig,int rt)
{
    if(ns[rt].lef==lef&&ns[rt].rig==rig){
        ns[rt].cover_cnt+=val;
        pushup(rt);
        return ;
    }
    int mid=(ns[rt].lef)+(ns[rt].rig-ns[rt].lef)/2;
    if(rig<=mid){
        update(val,lef,rig,rt<<1);
    }else if(lef>mid){
        update(val,lef,rig,rt<<1|1);
    }else{
        update(val,lef,mid,rt<<1);
        update(val,mid+1,rig,rt<<1|1);
    }
    pushup(rt);
}
int binary(double arr[],double key,int n)
{
    int lef=0;int rig=n-1;
    while(lef<=rig){
        int mid=lef+(rig-lef)/2;
        if(arr[mid]==key)
            return mid;
        else if(arr[mid]<key)
            lef=mid+1;
        else
            rig=mid-1;
    }
    return rig;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--){
        mst(xs,0);
        int n;scanf("%d",&n);
        int cnt=0;
        for(int i=0;i<n;i++){
            double x1,y1,x2,y2;
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
            segs[cnt]=seg(x1,x2,y1,1);       //下位
            xs[cnt++]=x1;
            segs[cnt]=seg(x1,x2,y2,-1);
            xs[cnt++]=x2;
        }
        sort(xs,xs+cnt);
//        for(int i=0;i<cnt;i++)
//            cout<<xs[i]<<" ";
//        cout<<"\n";
        sort(segs,segs+cnt);
        int idx=1;
        for(int i=1;i<cnt;i++)
            if(xs[i]!=xs[i-1])
                xs[idx++]=xs[i];
        build(0,idx-1,1);
        double ans=0;
        for(int i=0;i<cnt-1;i++){
            int lx=binary(xs,segs[i].lef,idx);
            int rx=binary(xs,segs[i].rig,idx)-1;
            update(segs[i].tag,lx,rx,1);
            ans+=(segs[i+1].hei-segs[i].hei)*(ns[1].len2);
//            printf("ans+: %.2lf\n",(segs[i+1].hei-segs[i].hei)*(ns[1].len2));
//            printf("ns[1].len2: %.2lf\n",ns[1].len2);
//            printf("segs[i+1].hei-segs[i].hei: %.2lf\n\n",segs[i+1].hei-segs[i].hei);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}

HDU1542 Atlantis

扫描线最经典的应用，求矩形的面积并。线段树维护区间的被覆盖长度，然后根据扫描线高度差计算面积即可。另外，本题需要离散化。 代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=2005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct seg{
    double lef;double rig;
    double hei;int tag;
    //tag=1表示下位边,tag=-1表示上位边
    seg(){
    } 
    seg(double lef,double rig,double hei,int tag)
        :lef(lef),rig(rig),hei(hei),tag(tag){
        } 
    bool operator<(const seg& se) const{
        return hei<se.hei;
    }
};
seg segs[maxn];
double X[maxn<<2];
int vis[maxn<<2];
double sum[maxn<<2];
int idx;
void pushup(int l,int r,int rt)
{
    if(vis[rt])
        sum[rt]=X[r+1]-X[l];
    else if(l==r)
        sum[rt]=0;
    else
        sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
}
void update(int L,int R,int val,int lef,int rig,int rt)
{
    if(L<=lef&&rig<=R){
        vis[rt]+=val;
        pushup(lef,rig,rt);
        return ;
    }
    int mid=lef+(rig-lef)/2;
    if(L<=mid)
        update(L,R,val,lson);
    if(R>mid)
        update(L,R,val,rson);
    pushup(lef,rig,rt);
}
int binary(double todo)
{
    int Lef,Rig;
    Lef=0;Rig=idx-1;
    while(Lef<=Rig){
        int mid=Lef+(Rig-Lef)/2;
        if(X[mid]>todo)
            Rig=mid-1;
        else
            Lef=mid+1;
    }
    return Rig;
}
int main()
{
    int n;int kase=0;
    while(cin>>n&&n){
        int cnt=0;idx=0;
        for(int i=0;i<n;i++){
            double x1,y1,x2,y2;
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); 
            segs[cnt]=seg(x1,x2,y1,1);
            X[cnt++]=x1;
            segs[cnt]=seg(x1,x2,y2,-1);
            X[cnt++]=x2;
        }
        sort(segs,segs+cnt);
        sort(X,X+cnt);
        idx=1;double ans=0;
        for(int i=1;i<cnt;i++)
            if(X[i]!=X[i-1])
                X[idx++]=X[i];
        mst(sum,0);mst(vis,0);
        for(int i=0;i<cnt-1;i++){
            int L=binary(segs[i].lef);
            int R=binary(segs[i].rig)-1;
            update(L,R,segs[i].tag,0,idx-1,1);
            ans+=sum[1]*(segs[i+1].hei-segs[i].hei);
        }
        printf("Test case #%d\n",++kase);
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
} 

HDU3642 Get the Treasury 题意是求在三维空间中，有若干个矩形区域，求重叠次数大于等于3的区域的体积。 思路是用线段树维护单个平面被覆盖次数大于等于3的平面区域的面积，然后枚举z轴上的高度差，进而算出面积（z的范围并不大，可以枚举） 具体见代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define mst(a,b) memset((a),(b),sizeof(b))
#define debug cout<<"debug"<<endl;
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
typedef long long ll;
const int maxn=2500;
using namespace std;
struct seg{
    int lef,rig;
    int hei;
    int tag;
    seg(){}
    seg(int lef,int rig,int hei,int tag)
        :lef(lef),rig(rig),hei(hei),tag(tag){}
    void set(int l,int r,int h,int tt){
        lef=l;rig=r;hei=h;
        tag=tt;
    }
    bool operator<(const seg& se)const{
        return hei<se.hei;
    }
};
struct node{
    int lef,rig;
    int len,len2,len3;    
    int cover_cnt;
    node(){}
//    node(int lef,int rig)
//        :lef(lef),rig(rig){len=len2=len3=cover_cnt=0;}
};
struct point{
    int x,y,z;
    point(int x,int y,int z)
        :x(x),y(y),z(z){}
    point(){}
};
node tree[maxn<<3];
point ps[maxn<<1];
int xs[maxn<<1];
int zs[maxn<<1];
seg segs[maxn<<1];
void build(int lef,int rig,int rt)
{
    tree[rt].lef=lef;tree[rt].rig=rig;
    tree[rt].len=tree[rt].len2=tree[rt].len3=tree[rt].cover_cnt=0;
    if(lef==rig)
        return ;
    int mid=lef+(rig-lef)/2;
    build(lson);
    build(rson);
}
void pushup(int rt)
{
    if(tree[rt].cover_cnt>=3){
        tree[rt].len3=xs[tree[rt].rig+1]-xs[tree[rt].lef];
        tree[rt].len2=tree[rt].len=0;
    }else if(tree[rt].cover_cnt>=2){
        tree[rt].len3=tree[rt<<1].len3+tree[rt<<1|1].len3+tree[rt<<1].len2+tree[rt<<1|1].len2+tree[rt<<1].len+tree[rt<<1|1].len;
        tree[rt].len2=xs[tree[rt].rig+1]-xs[tree[rt].lef]-tree[rt].len3;
        tree[rt].len=0;
    }else if(tree[rt].cover_cnt>=1){
        tree[rt].len3=tree[rt<<1].len3+tree[rt<<1|1].len3+tree[rt<<1].len2+tree[rt<<1|1].len2;
        tree[rt].len2=tree[rt<<1].len+tree[rt<<1|1].len;
        tree[rt].len=xs[tree[rt].rig+1]-xs[tree[rt].lef]-tree[rt].len2-tree[rt].len3;
    }else{
        tree[rt].len3=tree[rt<<1].len3+tree[rt<<1|1].len3;
        tree[rt].len2=tree[rt<<1].len2+tree[rt<<1|1].len2;
        tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
    }
}
void update(int val,int lef,int rig,int rt)
{
    if(lef==tree[rt].lef&&rig==tree[rt].rig){
        tree[rt].cover_cnt+=val;
        pushup(rt);
        return ;
    }
    int mid=(tree[rt].lef)+(tree[rt].rig-tree[rt].lef)/2;
    if(rig<=mid){
        update(val,lef,rig,rt<<1);
    }else if(lef>mid){
        update(val,lef,rig,rt<<1|1);
    }else{
        update(val,lef,mid,rt<<1);
        update(val,mid+1,rig,rt<<1|1);
    }
    pushup(rt);
}
void init(int n)
{
    for(int i=0;i<n+1;i++){
        tree[i].cover_cnt=tree[i].lef=tree[i].rig=0;
        tree[i].len=tree[i].len2=tree[i].len3=0;
    }
}
int main()
{
    int t;scanf("%d",&t);
    int kase=0;
    while(t--){
        init(2005);
        mst(xs,0);mst(zs,0);
        int n;scanf("%d",&n);
        int cnt=0;
        for(int i=0;i<n;i++){
            int x1,y1,z1;
            int x2,y2,z2;
            scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2);
            xs[cnt]=x1;xs[cnt+1]=x2;
            zs[cnt]=z1;zs[cnt+1]=z2;
            ps[cnt]=point(x1,y1,z1);ps[cnt+1]=point(x2,y2,z2);
            cnt+=2;
        }
        sort(xs,xs+cnt);
        sort(zs,zs+cnt);
        int idx=1;
        for(int i=1;i<cnt;i++)
            if(xs[i]!=xs[i-1])
                xs[idx++]=xs[i];
        int idx1=1;
        for(int i=1;i<cnt;i++)
            if(zs[i]!=zs[i-1])
                zs[idx1++]=zs[i];
        ll ans=0;
        for(int i=0;i<idx1-1;i++){
            int k=0;
            for(int j=0;j<cnt;j+=2){
                if(ps[j].z<=zs[i]&&ps[j+1].z>zs[i]){
                    segs[k++].set(ps[j].x,ps[j+1].x,ps[j].y,1);
                    segs[k++].set(ps[j].x,ps[j+1].x,ps[j+1].y,-1);
                    // segs[k++]=seg(ps[j].x,ps[j+1].x,ps[j].y,1);
                    // segs[k++]=seg(ps[j].x,ps[j+1].x,ps[j+1].y,-1);
                }
            }
            init(idx-1);
            sort(segs,segs+k);
            build(0,idx-1,1);
            ll tmp=0;
            for(int j=0;j<k-1;j++){
                int lx=lower_bound(xs,xs+idx,segs[j].lef)-xs;
                int rx=lower_bound(xs,xs+idx,segs[j].rig)-xs-1;
                update(segs[j].tag,lx,rx,1);
                tmp+=(ll)tree[1].len3*(ll)(segs[j+1].hei-segs[j].hei);
            }
            ans+=(ll)tmp*(ll)(zs[i+1]-zs[i]);
        }
        if(n<3)
            ans=0;
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}
/*
4
4 5 0 8 9 5
0 3 3 4 5 7
5 4 4 10 6 9
5 5 5 9 9 7
*/

后记

看了一下，虽然专题里面有区间合并的题目，但我并不是用正统的区间合并的方法做的啊......所以说这方面还需要再好好学一下呢。