[kuangbin带你飞]专题七 线段树

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



228 / 440 Problem A HDU 1166 敌兵布阵

hint.解题报告见之前博客


207 / 438 Problem B HDU 1754 I Hate It

d.给出N个学生的成绩，现在有2种操作，

操作1：询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 

操作2：把ID为A的学生的成绩更改为B。 

对于每个询问，输出最高成绩。

s.线段树单点更新，区间查询。

#include<iostream>
#include<stdio.h>
using namespace std;

#define MAXN 200005
int ans;

int grade[MAXN];

struct node{
    int left,right;//,sum;
    int ma;//区间最大值
    int mid(){
        return (left+right)>>1;
    }
}tree[MAXN*4];//注意范围，4倍空间

void btree(int left,int right,int rt){//建树
    tree[rt].left=left;
    tree[rt].right=right;
    if(left==right){
        //scanf("%d",&tree[rt].sum);
        tree[rt].ma=grade[left];
        return;
    }
    int mid=tree[rt].mid();
    btree(left,mid,rt<<1);
    btree(mid+1,right,rt<<1|1);
    //tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//区间里的点数=左区间+右区间
    tree[rt].ma=tree[rt<<1].ma>tree[rt<<1|1].ma?tree[rt<<1].ma:tree[rt<<1|1].ma;
}

void query(int left,int right,int rt,int L,int R){//询问求最大值
    if(L<=left&&right<=R){
        //ans+=tree[rt].sum;
        if(tree[rt].ma>ans){
            ans=tree[rt].ma;
        }
        return;
    }
    int mid=tree[rt].mid();
    if(R<=mid)query(left,mid,rt<<1,L,R);//区间在左子树
    else if(L>mid)query(mid+1,right,rt<<1|1,L,R);//区间在右子树
    else{
        query(left,mid,rt<<1,L,R);
        query(mid+1,right,rt<<1|1,L,R);
    }
}

void update(int left,int right,int rt,int pos,int add){//单点更新函数
    if(left==right){
        //tree[rt].sum+=add;
        tree[rt].ma=add;
        return;
    }
    int mid=tree[rt].mid();
    if(pos<=mid)update(left,mid,rt<<1,pos,add);//点在左子树
    else update(mid+1,right,rt<<1|1,pos,add);//点在右子树
    //tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//区间和更新
    tree[rt].ma=tree[rt<<1].ma>tree[rt<<1|1].ma?tree[rt<<1].ma:tree[rt<<1|1].ma;//区间最大值更新
}

int main(){

    int N,M;
    char str[2];
    int A,B;

    while(~scanf("%d%d",&N,&M)){

        for(int i=1;i<=N;++i){
            scanf("%d",&grade[i]);
        }

        btree(1,N,1);

        for(int i=0;i<M;++i){
            scanf("%1s",str);
            scanf("%d%d",&A,&B);
            if(str[0]=='Q'){
                ans=0;
                query(1,N,1,A,B);
                printf("%d
",ans);
            }
            else{
                update(1,N,1,A,B);
            }
        }

    }

    return 0;
}
View Code

181 / 727 Problem C POJ 3468 A Simple Problem with Integers

hint.解题报告见之前博客


105 / 410 Problem D POJ 2528 Mayor's posters

d.n张海报，高度相同，给出要贴在墙上的左右端点，后面贴的覆盖前面的，求最后能看到的海报数。

s.宽度范围很大，离散化

c.从前向后贴

/*
线段树
区间更新
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define L(root) ((root)<<1)
#define R(root) (((root)<<1)|1)

const int MAXN=10005;//
int numbers[MAXN];//初始值

int myHash[10000005];
bool vis[MAXN];//这种颜色存在标志

struct node{
    int left,right;//
    int color;
    int flag;//-1不向下更新，1向下更新，即单色时
    int mid(){
        return left+((right-left)>>1);
    }
}tree[MAXN*2*4];//4倍空间

void pushUp(int root){
}

void pushDown(int root){

    if(tree[root].flag==1){//需要向下更新
        tree[L(root)].flag=1;
        tree[R(root)].flag=1;
        tree[L(root)].color=tree[root].color;
        tree[R(root)].color=tree[root].color;
        tree[root].flag=-1;
    }
}

void build(int root,int left,int right){
    tree[root].left=left;
    tree[root].right=right;

    tree[root].flag=-1;
    if(left==right){
        return;
    }
    int mid=tree[root].mid();
    build(L(root),left,mid);
    build(R(root),mid+1,right);
}

int query(int root,int left,int right){

    if(tree[root].flag==1){//当前区间为单色的
        if(!vis[tree[root].color]){//第一次出现这种颜色
            vis[tree[root].color]=true;
            return 1;
        }
        return 0;
    }

    int mid=tree[root].mid();
    if(right<=mid){
        return query(L(root),left,right);
    }
    else if(left>mid){
        return query(R(root),left,right);
    }
    else{
        return query(L(root),left,mid)+query(R(root),mid+1,right);
    }
}

void update(int root,int left,int right,int add){
    if(tree[root].flag==1&&tree[root].color==add){
        return;//小剪枝，当前区间单色且与要更改的区间颜色相同则返回不用深入
    }

    if(tree[root].left==left&&tree[root].right==right){
        tree[root].color=add;
        tree[root].flag=1;
        return;
    }
    pushDown(root);
    int mid=tree[root].mid();
    if(right<=mid){
        update(L(root),left,right,add);
    }
    else if(left>mid){
        update(R(root),left,right,add);
    }
    else{
        update(L(root),left,mid,add);
        update(R(root),mid+1,right,add);
    }
}

int main(){

    int c;
    int n;
    int post[MAXN][2];//每个区间
    int p[MAXN*2];//所有的点
    int cnt;//所有点的个数
    int p2[MAXN*2];//去除重复
    int cnt2;

    int i;

    scanf("%d",&c);
    while(c--){
        scanf("%d",&n);
        cnt=0;
        for(i=0;i<n;++i){
            scanf("%d%d",&post[i][0],&post[i][1]);
            p[cnt++]=post[i][0];//保存所有端点
            p[cnt++]=post[i][1];
        }
        sort(p,p+cnt);//排序

        p2[0]=p[0];
        cnt2=1;
        for(i=1;i<cnt;++i){//去重
            if(p[i]!=p[i-1]){
                p2[cnt2++]=p[i];
            }
        }

        for(i=0;i<cnt2;++i){//所有点hash映射到0~cnt2-1
            myHash[p2[i]]=i;
        }


        build(1,0,cnt2-1);//0~cnt2-1
        for(i=0;i<n;++i){//n种颜色从头开始涂
            update(1,myHash[post[i][0]],myHash[post[i][1]],i);
        }

        memset(vis,false,sizeof(vis));
        printf("%d
",query(1,0,cnt2-1));//0~cnt2-1
    }

    return 0;
}
View Code

c2.从后向前看

/*
HDU 2528 Mayor's posters
本题大意：给定一些海报，可能相互重叠，告诉你每个海报
的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？
海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。
如果直接建树，就算不TLE,也会MLE。即单位区间长度太多。
其实10000张海报，有20000个点，最多有19999个区间。对各个区间编号，就是离散化。然后建数。
其实浮点数也是一样离散化的。

writer:kuangbin
*/
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN=10010;
struct Cpost
{
    int l,r;
} posters[MAXN];
int x[MAXN*2];
int hash[10000005];
struct Node
{
    int l,r;
    bool bCovered;//标记是否被完全覆盖
} segTree[MAXN*8]; //这里必须开到线段数的四倍，？？
void Build(int i,int l,int r)//建立线段树
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].bCovered=false;
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
}
bool Post(int i,int l,int r)//贴上一个好报，同时判断是否被完全覆盖
{
    if(segTree[i].bCovered)  return false;
    if(segTree[i].l==l&&segTree[i].r==r)
    {
        segTree[i].bCovered=true;
        return true;
    }
    bool bResult;
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if(r<=mid)  bResult=Post(i<<1,l,r);
    else if(l>mid)
        bResult=Post(i<<1|1,l,r);
    else
    {
        bool b1=Post(i<<1,l,mid);
        bool b2=Post(i<<1|1,mid+1,r);
        bResult=b1||b2;//不能直接或上去，因为如果前面的真，后面的会不做的
    }
    //这个很重要，要反馈回原结点，如果左右儿子都被完全覆盖了，自然也完全覆盖了
    if(segTree[i<<1].bCovered && segTree[i<<1|1].bCovered)
        segTree[i].bCovered=true;
    return bResult;
}
int main()
{
    int T;
    int i,j,k;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int nCount=0;
        for(i=0; i<n; i++)
        {
            scanf("%d%d",&posters[i].l,&posters[i].r);
            x[nCount++]=posters[i].l;
            x[nCount++]=posters[i].r;
        }
        sort(x,x+nCount);//先排序
        nCount=unique(x,x+nCount)-x;//合并掉相同的项
        for(i=0; i<nCount; i++)
            hash[x[i]]=i;
        Build(1,0,nCount-1);
        int res=0;
        for(i=n-1; i>=0; i--) //要从上面开始看。
            if(Post(1,hash[posters[i].l],hash[posters[i].r]))
                res++;
        printf("%d
",res);
    }
    return 0;
}
View Code

138 / 230 Problem E HDU 1698 Just a Hook

d.刚开始区间内元素全是1，每次操作可以把一个区间里的值全都变为1或2或3，求经过一些操作后，整个区间的元素的和

s.区间更新，区间查询。

#include<iostream>
#include<stdio.h>
using namespace std;

#define L(root) ((root) << 1)
#define R(root) (((root) << 1) + 1)

const int MAXN = 100005;
//int numbers[MAXN];

struct st
{
    // 区间范围
    int left, right;
    // 更新值、区间总和
    long long delta, sum;
} st[MAXN * 4];

// 建树代码基本不变
void build(int root, int l, int r)
{
    st[root].left = l, st[root].right = r, st[root].delta = 0;
    if (l == r)
    {
        //st[root].sum = numbers[l];
        st[root].sum=1;
        return;
    }

    int m = l + ((r - l) >> 1);
    build(L(root), l, m);
    build(R(root), m + 1, r);
    st[root].sum = st[L(root)].sum + st[R(root)].sum;
}

long long query(int root, int l, int r)
{
    // 如查询区间恰等于节点区间，直接返回该区间总和即可
    if (st[root].left == l && st[root].right == r)
    {
        return st[root].sum;
    }

    // 否则需将当前区间的“缓冲”值更新下去并修正各节点区间的总和
    if (st[root].delta)
    {
        st[L(root)].delta = st[root].delta;
        st[R(root)].delta = st[root].delta;
        st[L(root)].sum = st[root].delta * (st[L(root)].right - st[L(root)].left + 1);
        st[R(root)].sum = st[root].delta * (st[R(root)].right - st[R(root)].left + 1);
        st[root].delta = 0;
    }

    int m = st[root].left + ((st[root].right - st[root].left) >> 1);
    if (r <= m)
    {
        return query(L(root), l, r);
    }
    else if (l > m)
    {
        return query(R(root), l, r);
    }
    else
    {
        return query(L(root), l, m) + query(R(root), m + 1, r);
    }
}

void update(int root, int l, int r, long long v)
{
    // 如变更区间恰等于节点区间，只修正当前节点区间即可
    if (st[root].left == l && st[root].right == r)
    {
        st[root].delta = v;
        st[root].sum = v * (r - l + 1);
        return;
    }

    // 否则需向下修正相关节点区间
    if (st[root].delta)
    {
        st[L(root)].delta = st[root].delta;
        st[R(root)].delta = st[root].delta;
        st[L(root)].sum = st[root].delta * (st[L(root)].right - st[L(root)].left + 1);
        st[R(root)].sum = st[root].delta * (st[R(root)].right - st[R(root)].left + 1);
        st[root].delta = 0;
    }

    int m = st[root].left + ((st[root].right - st[root].left) >> 1);
    if (r <= m)
    {
        update(L(root), l, r, v);
    }
    else if (l > m)
    {
        update(R(root), l, r, v);
    }
    else
    {
        update(L(root), l, m, v);
        update(R(root), m + 1, r, v);
    }
    // 同时一定要记得修正当前节点区间的总和
    st[root].sum = st[L(root)].sum + st[R(root)].sum;
}

int main()
{

    int T,N,Q;
    int X,Y,Z;
    __int64 ans;
    int C=0;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);
        build(1,1,N);

        scanf("%d",&Q);
        for(int i=0;i<Q;++i){
            scanf("%d%d%d",&X,&Y,&Z);
            update(1,X,Y,Z);
        }

        ans=query(1,1,N);

        printf("Case %d: The total value of the hook is %I64d.
",++C,ans);

    }

    return 0;
}
View Code

c2.一个map写的代码，思想不错。不过最坏是O(MQ)

#include<stdio.h>
const int n = 1000005;
int map[n][3];
int main()
{
    int i,M,z,N,sum,v;
    scanf("%d",&N);
    for(i=1; i<=N; i++)
    {
        sum = 0;
        int Q,j;
        scanf("%d%d",&M,&Q);
        for(j=1; j<=Q; j++)
            scanf("%d%d%d",&map[j][0],&map[j][1],&map[j][2]);
        for(j=1; j<=M; j++)
        {
            v = 1;
            for(int k=Q; k>=0; k--)//从末尾开始 即从更新的最后一次算起
                if(map[k][0]<=j && j<=map[k][1])
                {
                    v = map[k][2];
                    break;//覆盖便弹出
                }
                sum += v;
        }
        printf("Case %d: The total value of the hook is %d.
",i,sum);
    }
}
View Code

105 / 305 Problem F ZOJ 1610 Count the Colors

hint.解题报告见之前博客


120 / 176 Problem G POJ 3264 Balanced Lineup

d.区间最大值最小值的差

/*
POJ 3264  Balanced Lineup
题目意思：给定Q（1<=Q<=200000)个数A1,A2,```,AQ,
多次求任一区间Ai-Aj中最大数和最小数的差 
*/
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 200005
#define INF 10000000
int nMax,nMin;//记录最大最小值 
struct Node
{
    int l,r;//区间的左右端点 
    int nMin,nMax;//区间的最小值和最大值 
}segTree[MAXN*3];
int a[MAXN];
void Build(int i,int l,int r)//在结点i上建立区间为(l,r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    if(l==r)//叶子结点 
    {
        segTree[i].nMin=segTree[i].nMax=a[l];
        return;
    } 
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    segTree[i].nMin=min(segTree[i<<1].nMin,segTree[i<<1|1].nMin);
    segTree[i].nMax=max(segTree[i<<1].nMax,segTree[i<<1|1].nMax);   
}
void Query(int i,int l,int r)//查询结点i上l-r的最大值和最小值
{
    if(segTree[i].nMax<=nMax&&segTree[i].nMin>=nMin)  return;
    if(segTree[i].l==l&&segTree[i].r==r)
    {
        nMax=max(segTree[i].nMax,nMax);
        nMin=min(segTree[i].nMin,nMin);
        return;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if(r<=mid)   Query(i<<1,l,r);
    else if(l>mid)  Query(i<<1|1,l,r);
    else
    {
        Query(i<<1,l,mid);
        Query(i<<1|1,mid+1,r);
    }      
}
int main()
{
    int n,q;
    int l,r;
    int i;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(i=1;i<=n;i++)
          scanf("%d",&a[i]);
        Build(1,1,n);
        for(i=1;i<=q;i++)
        {
            scanf("%d%d",&l,&r);
            nMax=-INF;nMin=INF;
            Query(1,l,r);
            printf("%d
",nMax-nMin);
        }    
    }  
    return 0;  
}
View Code

93 / 406 Problem H HDU 4027 Can you answer these queries?

题意：给你N个数，有M个操作，操作有两类，

（1）"0 l r"，表示将区间[l,r]里的每个数都开根号。

（2）"1 l r"，表示查询区间[l,r]里所有数的和。

关键就是一个数开根号几次后很快就可以变成1了。
如果都是1就不需要往下更新了。
还有就是输入的X,Y大小是不一定的，，这个坑了好久
/*
HDU 4027 Can you answer these queries?

*/
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
const int MAXN=5000100;
struct Node
{
    int l,r;
    long long sum;
}segTree[MAXN*3];
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    if(l==r)
    {
        scanf("%I64d",&segTree[i].sum);
        return;
    }
    int mid=((l+r)>>1);
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid+1,r);
    segTree[i].sum=segTree[i<<1].sum+segTree[(i<<1)|1].sum;
}
void action(int i,int l,int r)
{
    if(segTree[i].l==l && segTree[i].r==r && segTree[i].sum==r-l+1) return;
    if(segTree[i].l==segTree[i].r)
    {
        segTree[i].sum=sqrt(segTree[i].sum*1.0);
        return;
    }
    int mid=((segTree[i].l+segTree[i].r)>>1);
    if(r<=mid) action(i<<1,l,r);
    else if(l>mid)  action((i<<1)|1,l,r);
    else
    {
        action(i<<1,l,mid);
        action((i<<1)|1,mid+1,r);
    }
    segTree[i].sum=segTree[i<<1].sum+segTree[(i<<1)|1].sum;
}
long long SUM(int i,int l,int r)
{
    if(l==segTree[i].l && r==segTree[i].r) return segTree[i].sum;

    int mid=((segTree[i].l+segTree[i].r)/2);
    long long ans=0;

    if(r<=mid) ans=SUM(i<<1,l,r);
    else if(l>mid) ans=SUM((i<<1)|1,l,r);
    else
    {
        ans+=SUM(i<<1,l,mid);
        ans+=SUM((i<<1)|1,mid+1,r);
    }
    return ans;
}
int main()
{
  //  freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    int n;
    int T,X,Y;
    int iCase=0;
    int M;
    while(scanf("%d",&n)!=EOF)
    {
        iCase++;
        Build(1,1,n);
        scanf("%d",&M);
        printf("Case #%d:
",iCase);
        while(M--)
        {
            scanf("%d%d%d",&T,&X,&Y);
            if(X>Y)swap(X,Y);//这个很重要
            if(T==0) action(1,X,Y);
            //else printf("%I64d
",sum(1,X,Y));
            else printf("%I64d
",SUM(1,X,Y));
        }
        printf("
");
    }
    return 0;
}
View Code

73 / 183 Problem I HDU 1540 Tunnel Warfare

题意是一条线上的点，D x是破坏这个点，Q x是表示查询以x所在的最长的连续的点的个数（即连续的完好的村庄的个数），R是恢复上一次破坏的点。
线段树结点 设置一个  ll 记录区间左端点开始的最大连续个数，  rl 记录区间右端点开始的最大的连续个数,
ml表示该区间最大的连续点的个数。
主要是更新和查询两个操作。
有点像分治的意思，大区间的最优解由两个小区间的最优解以及小区间中间相连的那部分决定。
 
/*
HDU 1540 Tunnel Warfare
题义是对于一段线段，D x 表示破坏x点，
R 表示回复最近一次被破坏的点，Q x表示
询问以x点为中心的两头的最长的连续区间。

*/


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=50050;
struct Node
{
    int l,r;
    int ll,rl,ml;
    //左端点开始向左连续的最大长度和右端点开始向左最大的连续长度
    //以及这个区间最大连续长度
}segTree[MAXN*3];
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].ll=segTree[i].rl=segTree[i].ml=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid+1,r);
}
void update(int i,int t,int val)
{
    if(segTree[i].l==segTree[i].r)
    {
        if(val==1)segTree[i].ll=segTree[i].rl=segTree[i].ml=1;
        else segTree[i].ll=segTree[i].rl=segTree[i].ml=0;
        return;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if(t<=mid)update(i<<1,t,val);
    else update((i<<1)|1,t,val);
    segTree[i].ll=segTree[i<<1].ll;
    segTree[i].rl=segTree[(i<<1)|1].rl;
    segTree[i].ml=max(segTree[i<<1].ml,segTree[(i<<1)|1].ml);
    segTree[i].ml=max(segTree[i].ml,segTree[i<<1].rl+segTree[(i<<1)|1].ll);//解还有可能在中间那部分

    if(segTree[i<<1].ll==segTree[i<<1].r-segTree[i<<1].l+1)segTree[i].ll+=segTree[(i<<1)|1].ll;
    if(segTree[(i<<1)|1].rl==segTree[(i<<1)|1].r-segTree[(i<<1)|1].l+1)
        segTree[i].rl+=segTree[i<<1].rl;
}
int query(int i,int t)
{
    if(segTree[i].l==segTree[i].r||segTree[i].ml==0||segTree[i].ml==segTree[i].r-segTree[i].l+1)
    {
        return segTree[i].ml;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if(t<=mid)
    {
        if(t>=segTree[i<<1].r-segTree[i<<1].rl+1)//仔细想想
           return query(i<<1,t)+query((i<<1)|1,mid+1);
        else return query(i<<1,t);
    }
    else
    {
        if(t<=segTree[(i<<1)|1].l+segTree[(i<<1)|1].ll-1)
           return query((i<<1)|1,t)+query(i<<1,mid);
        else return query((i<<1)|1,t);
    }
}
int que[MAXN];
int top;
int main()
{
   // freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    int n,m;
    char str[10];
    int x;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Build(1,1,n);
        top=0;
        while(m--)
        {
            scanf("%s",&str);
            if(str[0]=='D')
            {
                scanf("%d",&x);
                que[top++]=x;

                update(1,x,0);


            }
            else if(str[0]=='Q')
            {
                scanf("%d",&x);
                printf("%d
",query(1,x));
            }
            else
            {
                if(x>0)
                {
                    x=que[--top];

                    update(1,x,1);
                }

            }
        }
    }
    return 0;
}
View Code

61 / 164 Problem J HDU 3974 Assign the task

d.N个员工，N-1条有向边，构成一颗树，边v->u表示v是u的直接上属。有两种操作，

C x表示查询x员工当前的任务

T x y表示给x员工安排y任务

新的任务会覆盖前面的任务。

怎么转换成线段树的？从根节点开始进行一次dfs，上下属关系转换成区间包含关系。比较巧妙。

然后就是区间更新，单点查询。

/* ***********************************************
Author        :kuangbin
Created Time  :2013-11-17 19:50:24
File Name     :E:2013ACM比赛练习2013-11-17C.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 50010;
struct Edge
{
    int to,next;
}edge[MAXN];
int head[MAXN],tot;
int cnt;
int start[MAXN],_end[MAXN];
void init()
{
    cnt = 0;
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs(int u)
{
    ++cnt;
    start[u] = cnt;
    for(int i = head[u];i != -1;i = edge[i].next)
    {
        dfs(edge[i].to);
    }
    _end[u] = cnt;
}
struct Node
{
    int l,r;
    int val;
    int lazy;
}segTree[MAXN*4];
void Update_Same(int r,int v)
{
    if(r)
    {
        segTree[r].val = v;
        segTree[r].lazy = 1;
    }
}
void push_down(int r)
{
    if(segTree[r].lazy)
    {
        Update_Same(r<<1,segTree[r].val);
        Update_Same((r<<1)|1,segTree[r].val);
        segTree[r].lazy = 0;
    }
}
void Build(int i,int l,int r)
{
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].val = -1;
    segTree[i].lazy = 0;
    if(l == r)return;
    int mid = (l+r)/2;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid+1,r);
}
void update(int i,int l,int r,int v)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        Update_Same(i,v);
        return;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    if(r <= mid)update(i<<1,l,r,v);
    else if(l > mid)update((i<<1)|1,l,r,v);
    else
    {
        update(i<<1,l,mid,v);
        update((i<<1)|1,mid+1,r,v);
    }
}
int query(int i,int u)
{
    if(segTree[i].l == u && segTree[i].r == u)
        return segTree[i].val;
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    if(u <= mid)return query(i<<1,u);
    else return query((i<<1)|1,u);
}
bool used[MAXN];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    int T;
    scanf("%d",&T);
    int iCase = 0;
    while(T--)
    {
        iCase++;
        printf("Case #%d:
",iCase);
        int u,v;
        memset(used,false,sizeof(used));
        init();
        scanf("%d",&n);
        for(int i = 1;i < n;i++)
        {
            scanf("%d%d",&u,&v);
            used[u] = true;
            addedge(v,u);
        }
        for(int i = 1;i <= n;i++)
            if(!used[i])
            {
                dfs(i);
                break;
            }
        Build(1,1,cnt);
        char op[10];
        int m;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",op);
            if(op[0] == 'C')
            {
                scanf("%d",&u);
                printf("%d
",query(1,start[u]));
            }
            else
            {
                scanf("%d%d",&u,&v);
                update(1,start[u],_end[u],v);
            }
        }
    }
    return 0;
}
View Code

27 / 105 Problem K HDU 4578 Transformation

很裸的线段树的题目。但是做起来比较麻烦。

我用sum1,sum2,sum3分别代表和、平方和、立方和。

懒惰标记使用三个变量：

lazy1:是加的数

lazy2:是乘的倍数

lazy3:是赋值为一个常数，为0表示没有。

更新操作需要注意很多细节。

/* **********************************************
Author      : kuangbin
Created Time: 2013/8/10 13:24:03
File Name   : F:2013ACM练习比赛练习2013杭州邀请赛重现1003.cpp
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int MOD = 10007;
const int MAXN = 100010;
struct Node
{
    int l,r;
    int sum1,sum2,sum3;
    int lazy1,lazy2,lazy3;
}segTree[MAXN*3];
void build(int i,int l,int r)
{
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].sum1 = segTree[i].sum2 = segTree[i].sum3 = 0;
    segTree[i].lazy1 = segTree[i].lazy3 = 0;
    segTree[i].lazy2 = 1;
    int mid = (l+r)/2;
    if(l == r)return;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
}
void push_up(int i)
{
    if(segTree[i].l == segTree[i].r)//这个判断以前都没用过啊。。。不用会出错吗？
        return;
    segTree[i].sum1 = (segTree[i<<1].sum1 + segTree[(i<<1)|1].sum1)%MOD;
    segTree[i].sum2 = (segTree[i<<1].sum2 + segTree[(i<<1)|1].sum2)%MOD;
    segTree[i].sum3 = (segTree[i<<1].sum3 + segTree[(i<<1)|1].sum3)%MOD;

}

void push_down(int i)
{
    if(segTree[i].l == segTree[i].r) return;//
    if(segTree[i].lazy3 != 0)//为什么先看lazy3呢？想了下，这个置数优先级更高。
    {
        segTree[i<<1].lazy3 = segTree[(i<<1)|1].lazy3 = segTree[i].lazy3;
        segTree[i<<1].lazy1 = segTree[(i<<1)|1].lazy1 = 0;
        segTree[i<<1].lazy2 = segTree[(i<<1)|1].lazy2 = 1;
        segTree[i<<1].sum1 = (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i<<1].lazy3%MOD;
        segTree[i<<1].sum2 = (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i<<1].lazy3%MOD*segTree[i<<1].lazy3%MOD;
        segTree[i<<1].sum3 = (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i<<1].lazy3%MOD*segTree[i<<1].lazy3%MOD*segTree[i<<1].lazy3%MOD;
        segTree[(i<<1)|1].sum1 = (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[(i<<1)|1].lazy3%MOD;
        segTree[(i<<1)|1].sum2 = (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[(i<<1)|1].lazy3%MOD*segTree[(i<<1)|1].lazy3%MOD;
        segTree[(i<<1)|1].sum3 = (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[(i<<1)|1].lazy3%MOD*segTree[(i<<1)|1].lazy3%MOD*segTree[(i<<1)|1].lazy3%MOD;
        segTree[i].lazy3 = 0;
    }
    if(segTree[i].lazy1 != 0 || segTree[i].lazy2 != 1)
    {
        segTree[i<<1].lazy1 = ( segTree[i].lazy2*segTree[i<<1].lazy1%MOD + segTree[i].lazy1 )%MOD;
        segTree[i<<1].lazy2 = segTree[i<<1].lazy2*segTree[i].lazy2%MOD;
        int sum1,sum2,sum3;
        sum1 = (segTree[i<<1].sum1*segTree[i].lazy2%MOD + (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i].lazy1%MOD)%MOD;
        sum2 = (segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i<<1].sum2 % MOD + 2*segTree[i].lazy1*segTree[i].lazy2%MOD * segTree[i<<1].sum1%MOD + (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i].lazy1%MOD*segTree[i].lazy1%MOD)%MOD;
        sum3 = segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i<<1].sum3 % MOD;
        sum3 = (sum3 + 3*segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i<<1].sum2) % MOD;
        sum3 = (sum3 + 3*segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[i<<1].sum1) % MOD;
        sum3 = (sum3 + (segTree[i<<1].r - segTree[i<<1].l + 1)*segTree[i].lazy1%MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
        segTree[i<<1].sum1 = sum1;
        segTree[i<<1].sum2 = sum2;
        segTree[i<<1].sum3 = sum3;
        segTree[(i<<1)|1].lazy1 = ( segTree[i].lazy2*segTree[(i<<1)|1].lazy1%MOD + segTree[i].lazy1 )%MOD;
        segTree[(i<<1)|1].lazy2 = segTree[(i<<1)|1].lazy2 * segTree[i].lazy2 % MOD;
        sum1 = (segTree[(i<<1)|1].sum1*segTree[i].lazy2%MOD + (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[i].lazy1%MOD)%MOD;
        sum2 = (segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[(i<<1)|1].sum2 % MOD + 2*segTree[i].lazy1*segTree[i].lazy2%MOD * segTree[(i<<1)|1].sum1%MOD + (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[i].lazy1%MOD*segTree[i].lazy1%MOD)%MOD;
        sum3 = segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[(i<<1)|1].sum3 % MOD;
        sum3 = (sum3 + 3*segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[(i<<1)|1].sum2) % MOD;
        sum3 = (sum3 + 3*segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[(i<<1)|1].sum1) % MOD;
        sum3 = (sum3 + (segTree[(i<<1)|1].r - segTree[(i<<1)|1].l + 1)*segTree[i].lazy1%MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
        segTree[(i<<1)|1].sum1 = sum1;
        segTree[(i<<1)|1].sum2 = sum2;
        segTree[(i<<1)|1].sum3 = sum3;
        segTree[i].lazy1 = 0;
        segTree[i].lazy2 = 1;

    }
}
void update(int i,int l,int r,int type,int c)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        c %= MOD;
        if(type == 1)
        {
            segTree[i].lazy1 += c;
            segTree[i].lazy1 %= MOD;
            segTree[i].sum3 = (segTree[i].sum3 + 3*segTree[i].sum2%MOD*c%MOD + 3*segTree[i].sum1%MOD*c%MOD*c%MOD + (segTree[i].r - segTree[i].l + 1)*c%MOD*c%MOD*c%MOD)%MOD;
            segTree[i].sum2 = (segTree[i].sum2 + 2*segTree[i].sum1%MOD*c%MOD + (segTree[i].r - segTree[i].l + 1)*c%MOD*c%MOD)%MOD;
            segTree[i].sum1 = (segTree[i].sum1 + (segTree[i].r - segTree[i].l + 1)*c%MOD)%MOD;
        }
        else if(type == 2)
        {
            segTree[i].lazy1 = segTree[i].lazy1*c%MOD;
            segTree[i].lazy2 = segTree[i].lazy2*c%MOD;
            segTree[i].sum1 = segTree[i].sum1*c%MOD;
            segTree[i].sum2 = segTree[i].sum2*c%MOD*c%MOD;
            segTree[i].sum3 = segTree[i].sum3*c%MOD*c%MOD*c%MOD;
        }
        else
        {
            segTree[i].lazy1 = 0;
            segTree[i].lazy2 = 1;
            segTree[i].lazy3 = c%MOD;
            segTree[i].sum1 = c*(segTree[i].r - segTree[i].l + 1)%MOD;
            segTree[i].sum2 = c*(segTree[i].r - segTree[i].l + 1)%MOD*c%MOD;
            segTree[i].sum3 = c*(segTree[i].r - segTree[i].l + 1)%MOD*c%MOD*c%MOD;
        }
        return;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    if(r <= mid)update(i<<1,l,r,type,c);
    else if(l > mid)update((i<<1)|1,l,r,type,c);
    else
    {
        update(i<<1,l,mid,type,c);
        update((i<<1)|1,mid+1,r,type,c);
    }
    push_up(i);
}
int query(int i,int l,int r,int p)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        if(p == 1)return segTree[i].sum1;
        else if(p== 2)return segTree[i].sum2;
        else return segTree[i].sum3;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r )/2;
    if(r <= mid)return query(i<<1,l,r,p);
    else if(l > mid)return query((i<<1)|1,l,r,p);
    else return (query(i<<1,l,mid,p)+query((i<<1)|1,mid+1,r,p))%MOD;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m;
    while(scanf("%d%d",&n,&m) == 2)
    {
        if(n == 0 && m == 0)break;
        build(1,1,n);
        int type,x,y,c;
        while(m--)
        {
            scanf("%d%d%d%d",&type,&x,&y,&c);
            if(type == 4)printf("%d
",query(1,x,y,c));
            else update(1,x,y,type,c);
        }
    }
    return 0;
}
View Code

32 / 103 Problem L HDU 4614 Vases and Flowers

很裸的线段树。但是写起来很麻烦。

1~N 的区间，用1表示空的，0表示放了花的。

维护一个sum,就是和

first : 区间最左边的1

last: 区间最右边的1

然后一个更新操作，一个求区间和操作。

查询区间第一个1，和最后一个1.

二分确定区间。

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <math.h>
using namespace std;
const int MAXN = 50010;
struct Node
{
    int l,r;
    int sum;
    int lazy;
    int first;
    int last;
}segTree[MAXN*3];
void push_up(int i)
{
    if(segTree[i].l==segTree[i].r)return;
    segTree[i].sum = segTree[i<<1].sum+segTree[(i<<1)|1].sum;
    if(segTree[i<<1].first != -1)segTree[i].first = segTree[i<<1].first;
    else segTree[i].first = segTree[(i<<1)|1].first;
    if(segTree[(i<<1)|1].last != -1)segTree[i].last = segTree[(i<<1)|1].last;
    else segTree[i].last = segTree[(i<<1)].last;
}
void push_down(int i)
{
    if(segTree[i].r == segTree[i].l)return;
    if(segTree[i].lazy==1)
    {
        segTree[i<<1].first = segTree[i<<1].l;
        segTree[i<<1].last = segTree[i<<1].r;
        segTree[i<<1].sum = segTree[i<<1].r-segTree[i<<1].l+1;
        segTree[i<<1].lazy=1;
        segTree[(i<<1)|1].first = segTree[(i<<1)|1].l;
        segTree[(i<<1)|1].last = segTree[(i<<1)|1].r;
        segTree[(i<<1)|1].sum = segTree[(i<<1)|1].r-segTree[(i<<1)|1].l+1;
        segTree[(i<<1)|1].lazy=1;
    }
    if(segTree[i].lazy == -1)
    {
        segTree[i<<1].first = -1;
        segTree[i<<1].last = -1;
        segTree[i<<1].sum = 0;
        segTree[i<<1].lazy=-1;
        segTree[(i<<1)|1].first = -1;
        segTree[(i<<1)|1].last = -1;
        segTree[(i<<1)|1].sum = 0;
        segTree[(i<<1)|1].lazy=-1;
    }
    segTree[i].lazy = 0;
}
void build(int i,int l,int r)
{
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].sum = r-l+1;
    segTree[i].lazy = 0;
    segTree[i].first = l;
    segTree[i].last = r;
    if(l==r)return ;
    int mid = (l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
}
void update(int i,int l,int r,int type)
{
    if(segTree[i].l == l && segTree[i].r==r)
    {
        if(type == 0)
        {
            if(segTree[i].sum == 0)return;
            segTree[i].sum = 0;
            segTree[i].lazy = -1;
            segTree[i].first = -1;
            segTree[i].last = -1;
            return;
        }
        else if(type == 1)
        {
            if(segTree[i].sum == segTree[i].r-segTree[i].l+1)return;
            segTree[i].sum = segTree[i].r-segTree[i].l+1;
            segTree[i].lazy = 1;
            segTree[i].first = segTree[i].l;
            segTree[i].last = segTree[i].r;
            return;
        }

    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    if(r <= mid)update(i<<1,l,r,type);
    else if(l > mid)update((i<<1)|1,l,r,type);
    else
    {
        update(i<<1,l,mid,type);
        update((i<<1)|1,mid+1,r,type);
    }
    push_up(i);
}
int sum(int i,int l,int r)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        return segTree[i].sum;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    if(r <= mid)return sum(i<<1,l,r);
    else if(l > mid)return sum((i<<1)|1,l,r);
    else return sum((i<<1)|1,mid+1,r)+sum(i<<1,l,mid);
}
int n,m;
int query1(int i,int l,int r)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        return segTree[i].first;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    int ans1,ans2;
    if(r <= mid)return query1(i<<1,l,r);
    else if(l > mid)return query1((i<<1)|1,l,r);
    else
    {
        ans1 = query1(i<<1,l,mid);
        if(ans1 != -1)return ans1;
        return query1((i<<1)|1,mid+1,r);
    }
}
int query2(int i,int l,int r)
{
    if(segTree[i].l == l && segTree[i].r == r)
    {
        return segTree[i].last;
    }
    push_down(i);
    int mid = (segTree[i].l + segTree[i].r)/2;
    int ans1,ans2;
    if(r <= mid)return query2(i<<1,l,r);
    else if(l > mid)return query2((i<<1)|1,l,r);
    else
    {
        ans1 = query2((i<<1)|1,mid+1,r);
        if(ans1 != -1)return ans1;
        return query2(i<<1,l,mid);
    }
}
int bisearch(int A,int F)
{
    if(sum(1,A,n)==0)return -1;
    if(sum(1,A,n)<F)return n;
    int l= A,r = n;
    int ans=A;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(sum(1,A,mid)>=F)
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        build(1,1,n);
        int op,u,v;
        while(m--)
        {
            scanf("%d%d%d",&op,&u,&v);
            if(op == 1)
            {
                u++;
                int t = bisearch(u,v);
                //printf("t:%d
",t);
                if(t==-1)
                {
                    printf("Can not put any one.
");
                    continue;
                }
                printf("%d %d
",query1(1,u,t)-1,query2(1,u,t)-1);
                update(1,u,t,0);
            }
            else
            {
                u++;v++;
                //printf("sum:%d
",sum(1,u,v));
                printf("%d
",v-u+1-sum(1,u,v));
                update(1,u,v,1);
            }
        }
        printf("
");
    }
    return 0;
}
View Code

29 / 139 Problem M HDU 4553 约会安排

就是线段树。。。
进行两段区间合并操作
c.不得不说代码太帅了。。我是想不到这么写的。。学习了
//============================================================================
// Name        : C.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
const int MAXN=100010;
struct Node
{
    int l,r;
    int Max,Lmax,Rmax;
    int Max1,Lmax1,Rmax1;
}segTree[MAXN*4];
void push_up(int x)
{
    if(segTree[x].l==segTree[x].r)return;
    int lson=2*x;
    int rson=2*x+1;

    segTree[x].Lmax=segTree[lson].Lmax;
    if(segTree[lson].Lmax==segTree[lson].r-segTree[lson].l+1)segTree[x].Lmax+=segTree[rson].Lmax;
    segTree[x].Rmax=segTree[rson].Rmax;
    if(segTree[rson].Rmax==segTree[rson].r-segTree[rson].l+1)segTree[x].Rmax+=segTree[lson].Rmax;
    segTree[x].Max=max(segTree[lson].Max,segTree[rson].Max);
    segTree[x].Max=max(segTree[x].Max,max(segTree[x].Lmax,segTree[x].Rmax));
    segTree[x].Max=max(segTree[x].Max,segTree[lson].Rmax+segTree[rson].Lmax);

    segTree[x].Lmax1=segTree[lson].Lmax1;
    if(segTree[lson].Lmax1==segTree[lson].r-segTree[lson].l+1)segTree[x].Lmax1+=segTree[rson].Lmax1;
    segTree[x].Rmax1=segTree[rson].Rmax1;
    if(segTree[rson].Rmax1==segTree[rson].r-segTree[rson].l+1)segTree[x].Rmax1+=segTree[lson].Rmax1;
    segTree[x].Max1=max(segTree[lson].Max1,segTree[rson].Max1);
    segTree[x].Max1=max(segTree[x].Max1,max(segTree[x].Lmax1,segTree[x].Rmax1));
    segTree[x].Max1=max(segTree[x].Max1,segTree[lson].Rmax1+segTree[rson].Lmax1);
}
void push_down(int x)
{
    if(segTree[x].l==segTree[x].r)return;
    int lson=2*x,rson=2*x+1;
    if(segTree[x].Max==0)
    {
        segTree[lson].Max=segTree[lson].Lmax=segTree[lson].Rmax=0;
        segTree[rson].Max=segTree[rson].Lmax=segTree[rson].Rmax=0;
    }
    if(segTree[x].Max==segTree[x].r-segTree[x].l+1)
    {
        segTree[lson].Max=segTree[lson].Lmax=segTree[lson].Rmax=segTree[lson].r-segTree[lson].l+1;
        segTree[rson].Max=segTree[rson].Lmax=segTree[rson].Rmax=segTree[rson].r-segTree[rson].l+1;
    }


    if(segTree[x].Max1==0)
    {
        segTree[lson].Max1=segTree[lson].Lmax1=segTree[lson].Rmax1=0;
        segTree[rson].Max1=segTree[rson].Lmax1=segTree[rson].Rmax1=0;
    }
    if(segTree[x].Max1==segTree[x].r-segTree[x].l+1)
    {
        segTree[lson].Max1=segTree[lson].Lmax1=segTree[lson].Rmax1=segTree[lson].r-segTree[lson].l+1;
        segTree[rson].Max1=segTree[rson].Lmax1=segTree[rson].Rmax1=segTree[rson].r-segTree[rson].l+1;
    }

}
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].Max=segTree[i].Lmax=segTree[i].Rmax=r-l+1;
    segTree[i].Max1=segTree[i].Lmax1=segTree[i].Rmax1=r-l+1;
    if(l==r)return;
    int mid=(l+r)/2;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid+1,r);
}
int query(int i,int x)
{
    if(segTree[i].Max<x)return 0;
    if(segTree[i].Lmax>=x)return segTree[i].l;
    if(segTree[i<<1].Max>=x)return query(i<<1,x);
    if(segTree[i<<1].Rmax+segTree[(i<<1)|1].Lmax>=x)return segTree[i<<1].r-segTree[i<<1].Rmax+1;
    return query((i<<1)|1,x);
}
int query1(int i,int x)
{
    if(segTree[i].Max1<x)return 0;
    if(segTree[i].Lmax1>=x)return segTree[i].l;
    if(segTree[i<<1].Max1>=x)return query1(i<<1,x);
    if(segTree[i<<1].Rmax1+segTree[(i<<1)|1].Lmax1>=x)return segTree[i<<1].r-segTree[i<<1].Rmax1+1;
    return query1((i<<1)|1,x);
}
void update(int i,int l,int r)
{
    if(segTree[i].l==l && segTree[i].r==r)
    {
        segTree[i].Max=segTree[i].Lmax=segTree[i].Rmax=segTree[i].r-segTree[i].l+1;
        segTree[i].Max1=segTree[i].Lmax1=segTree[i].Rmax1=segTree[i].r-segTree[i].l+1;
        return;
    }
    push_down(i);
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(r<=mid)update(i<<1,l,r);
    else if(l>mid) update((i<<1)|1,l,r);
    else
    {
        update(i<<1,l,mid);
        update((i<<1)|1,mid+1,r);
    }
    push_up(i);
}
void zhan1(int i,int l,int r)
{
    if(segTree[i].l==l && segTree[i].r==r)
    {
        segTree[i].Max=segTree[i].Lmax=segTree[i].Rmax=0;
        return;
    }
    push_down(i);
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(r<=mid)zhan1(i<<1,l,r);
    else if(l>mid) zhan1((i<<1)|1,l,r);
    else
    {
        zhan1(i<<1,l,mid);
        zhan1((i<<1)|1,mid+1,r);
    }
    push_up(i);
}
void zhan2(int i,int l,int r)
{
    if(segTree[i].l==l && segTree[i].r==r)
    {
        segTree[i].Max=segTree[i].Lmax=segTree[i].Rmax=0;
        segTree[i].Max1=segTree[i].Lmax1=segTree[i].Rmax1=0;
        return;
    }
    push_down(i);
    int mid=(segTree[i].l+segTree[i].r)/2;
    if(r<=mid)zhan2(i<<1,l,r);
    else if(l>mid) zhan2((i<<1)|1,l,r);
    else
    {
        zhan2(i<<1,l,mid);
        zhan2((i<<1)|1,mid+1,r);
    }
    push_up(i);
}

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int T;
    int n,m;
    int l,r;
    int x;
    char op[20];
    scanf("%d",&T);
    int iCase=0;
    while(T--)
    {
        iCase++;
        printf("Case %d:
",iCase);
        scanf("%d%d",&n,&m);
        Build(1,1,n);
        while(m--)
        {
            scanf("%s",op);
            if(op[0]=='D')
            {
                scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp==0)printf("fly with yourself
");
                else
                {
                    zhan1(1,tmp,tmp+x-1);
                    printf("%d,let's fly
",tmp);
                }
            }
            else if(op[0]=='N')
            {
                scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp!=0)
                {
                    zhan2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi
",tmp);
                    continue;
                }
                tmp=query1(1,x);
                if(tmp!=0)
                {
                    zhan2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi
",tmp);
                    continue;
                }
                printf("wait for me
");
            }
            else
            {
                scanf("%d%d",&l,&r);
                printf("I am the hope of chinese chengxuyuan!!
");
                update(1,l,r);
            }
        }
    }
    return 0;
}
View Code

35 / 52 Problem N POJ 1177 Picture

这题是很经典的线段树题目了。
抄一下别人的思路，按照这个实现的：

总体思路:

1.沿X轴离散化建树

2.按Y值从小到大排序平行与X轴的边,然后顺序处理

    如果遇到矩形下面那条边则插入到线段树中,遇到矩形上面的边则将相应的边删除掉

    根据线段树当前的状态统计长度

第二点是本题的核心思想,偶再举个例:


  第一次求出的部分很好理解.

  第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的长度,将这个值再减去上次的就少了中间那部分

  第三次因为是矩形的上边,所以要删除在那条长的线段.此时的线段树返回的则是第一次的长度,将此值减去第二次返回值,再取其负值就是红色X轴那部分了

  最后那条X轴的,再补上就行了.

需要注意的就是离散化以后一定要去掉重复元素，否则会出错的。

ps：不懂这种离散化的时候为什么去除重复元素？好像懂了一点点。。不过还是先记住吧，日后有机会再细细研究。

/*
POJ 1177
矩形周长并，求轮廓周长
这题可以不离散化做的，我做的是离散化以后的
这题和矩形面积并有类似的地方
把矩形变成一条条平行于x轴的线段（当然弄成平行于y轴的也是可以的）
要累加的一个是覆盖的线段长度的变化，还有就是竖直的线段。
离散化以后一定要进行去掉重复的点，因为会影响后面合并的时候。
STL中的unique()函数可以快速去掉相同元素
*/


#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=10010;
struct Node
{
    int l,r;
    int cnt;//有效长度
    int lf,rf;//实际的左右端点
    int numseg;//分支数，一个分支对应两条竖线
    int c;//记录覆盖情况
    bool lcover,rcover;
}segTree[MAXN*4];
struct Line
{
    int y;
    int x1,x2;
    int f;
}line[MAXN];
bool cmp(Line a,Line b)
{
    return a.y<b.y;
}
int x[MAXN];
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].lf=x[l];
    segTree[i].rf=x[r];
    segTree[i].cnt=0;
    segTree[i].numseg=0;
    segTree[i].c=0;
    segTree[i].lcover=segTree[i].rcover=false;
    if(l+1==r)return;
    int mid=(l+r)/2;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid,r);
}
void calen(int i)
{
    if(segTree[i].c>0)
    {
        segTree[i].cnt=segTree[i].rf-segTree[i].lf;
        segTree[i].numseg=1;
        segTree[i].lcover=segTree[i].rcover=true;
        return;
    }
    if(segTree[i].l+1==segTree[i].r)
    {
        segTree[i].cnt=0;
        segTree[i].numseg=0;
        segTree[i].lcover=segTree[i].rcover=false;
    }
    else
    {
        segTree[i].cnt=segTree[i<<1].cnt+segTree[(i<<1)|1].cnt;
        segTree[i].lcover=segTree[i<<1].lcover;
        segTree[i].rcover=segTree[(i<<1)|1].rcover;
        segTree[i].numseg=segTree[i<<1].numseg+segTree[(i<<1)|1].numseg;
        if(segTree[i<<1].rcover&&segTree[(i<<1)|1].lcover)segTree[i].numseg--;
    }
}
void update(int i,Line e)
{
    if(segTree[i].lf==e.x1&&segTree[i].rf==e.x2)
    {
        segTree[i].c+=e.f;
        calen(i);
        return;
    }
    if(e.x2<=segTree[i<<1].rf)update(i<<1,e);
    else if(e.x1>=segTree[(i<<1)|1].lf)update((i<<1)|1,e);
    else
    {
        Line temp=e;
        temp.x2=segTree[i<<1].rf;
        update(i<<1,temp);
        temp=e;
        temp.x1=segTree[(i<<1)|1].lf;
        update((i<<1)|1,temp);
    }
    calen(i);
}
int main()
{
    int x1,y1,x2,y2;
    int n;
    while(scanf("%d",&n)==1)
    {
        int t=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            line[t].x1=x1;
            line[t].x2=x2;
            line[t].y=y1;
            line[t].f=1;
            x[t++]=x1;
            line[t].x1=x1;
            line[t].x2=x2;
            line[t].y=y2;
            line[t].f=-1;
            x[t++]=x2;
        }
        sort(line,line+t,cmp);

        sort(x,x+t);
        int m=unique(x,x+t)-x;//合并相同元素，这里一点要合并相同元素，否则会WA.
        Build(1,0,m-1);
        int ans=0;
        int last=0;
        for(int i=0;i<t-1;i++)
        {
            update(1,line[i]);
            ans+=segTree[1].numseg*2*(line[i+1].y-line[i].y);
            ans+=abs(segTree[1].cnt-last);
            last=segTree[1].cnt;
        }
        update(1,line[t-1]);
        ans+=abs(segTree[1].cnt-last);
        printf("%d
",ans);
    }
    return 0;
}
View Code

37 / 67 Problem O HDU 1255 覆盖的面积

d.求面积交

hint.解题报告见之前博客


40 / 88 Problem P HDU 1542 Atlantis

d.求面积并，比求面积交简单

/*
POJ 1151 Atlantis
求矩形并的面积（线段树+离散化） 
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 201
struct Node
{
    int l,r;//线段树的左右整点
    int c;//c用来记录重叠情况
    double cnt,lf,rf;//
    //cnt用来计算实在的长度，rf,lf分别是对应的左右真实的浮点数端点 
}segTree[MAXN*3];     
struct Line
{
    double x,y1,y2;
    int f;
}line[MAXN];
//把一段段平行于y轴的线段表示成数组 ，
//x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标 
//一个矩形 ，左边的那条边f为1，右边的为-1，
//用来记录重叠情况，可以根据这个来计算，nod节点中的c 

bool cmp(Line a,Line b)//sort排序的函数
{
    return a.x < b.x;
}     

double y[MAXN];//记录y坐标的数组
void Build(int t,int l,int r)//构造线段树
{
    segTree[t].l=l;segTree[t].r=r;
    segTree[t].cnt=segTree[t].c=0;
    segTree[t].lf=y[l];
    segTree[t].rf=y[r];
    if(l+1==r)  return;
    int mid=(l+r)>>1;
    Build(t<<1,l,mid);
    Build(t<<1|1,mid,r);//递归构造 
}     
void calen(int t)//计算长度
{
    if(segTree[t].c>0)
    {
        segTree[t].cnt=segTree[t].rf-segTree[t].lf;
        return;
    }    
    if(segTree[t].l+1==segTree[t].r)  segTree[t].cnt=0;
    else  segTree[t].cnt=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
}     
void update(int t,Line e)//加入线段e，后更新线段树
{
    if(e.y1==segTree[t].lf&&e.y2==segTree[t].rf)
    {
        segTree[t].c+=e.f;
        calen(t);
        return;
    }    
    if(e.y2<=segTree[t<<1].rf)  update(t<<1,e);
    else if(e.y1>=segTree[t<<1|1].lf)  update(t<<1|1,e);
    else
    {
        Line tmp=e;
        tmp.y2=segTree[t<<1].rf;
        update(t<<1,tmp);
        tmp=e;
        tmp.y1=segTree[t<<1|1].lf;
        update(t<<1|1,tmp);
    }    
    calen(t);
}    
int main()
{
    int i,n,t,iCase=0;
    double x1,y1,x2,y2;
    while(scanf("%d",&n),n)
    {
        iCase++;
        t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=1;
            y[t]=y1;
            t++;
            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=-1;
            y[t]=y2;
            t++;
        } 
        sort(line+1,line+t,cmp);
        sort(y+1,y+t);   
        Build(1,1,t-1);
        update(1,line[1]);
        double res=0;
        for(i=2;i<t;i++)
        {
            res+=segTree[1].cnt*(line[i].x-line[i-1].x);
            update(1,line[i]);
        }    
        printf("Test case #%d
Total explored area: %.2f

",iCase,res);
        //看来POJ上%.2f可以过，%.2lf却不行了 
    }    
    return 0;
}
View Code

7 / 15 Problem Q HDU 3642 Get The Treasury

求立方体相交至少3次的体积。

枚举z

然后求矩形面积交。

常规的线段树题目。

较麻烦

/*
*HDU 3642
给定一些长方体，求这些长方体相交至少3次的体积
z坐标的绝对值不超过500，所以枚举z坐标，然后求矩形面积并
*/

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN=2010;
struct Node
{
    int l,r;
    int lf,rf;//实际的左右端点
    int c;
    int once,twice,more;
}segTree[MAXN*3];
int y[MAXN];
int z[MAXN];
struct Line
{
    int x;
    int y1,y2;
    int z1,z2;//这两个是枚举的时候判断使用的
    int f;
}line[MAXN];
bool cmp(Line a,Line b)
{
    return a.x<b.x;
}
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].lf=y[l];
    segTree[i].rf=y[r];
    segTree[i].c=0;
    segTree[i].once=segTree[i].twice=segTree[i].more=0;
    if(r==l+1)return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid,r);
}
void push_up(int i)
{
    if(segTree[i].c>2)
    {
        segTree[i].more=segTree[i].rf-segTree[i].lf;
        segTree[i].once=segTree[i].twice=0;
    }
    else if(segTree[i].c==2)
    {
        if(segTree[i].l+1==segTree[i].r)//叶子结点
        {
            segTree[i].more=0;
            segTree[i].twice=segTree[i].rf-segTree[i].lf;
            segTree[i].once=0;
            return;
        }
        segTree[i].more=segTree[i<<1].once+segTree[i<<1].twice+segTree[i<<1].more
                       +segTree[(i<<1)|1].once+segTree[(i<<1)|1].twice+segTree[(i<<1)|1].more;
        segTree[i].twice=segTree[i].rf-segTree[i].lf-segTree[i].more;
        segTree[i].once=0;
    }
    else if(segTree[i].c==1)
    {
        if(segTree[i].l+1==segTree[i].r)
        {
            segTree[i].more=0;
            segTree[i].twice=0;
            segTree[i].once=segTree[i].rf-segTree[i].lf;
            return;
        }
        segTree[i].more=segTree[i<<1].more+segTree[i<<1].twice
                    +segTree[(i<<1)|1].more+segTree[(i<<1)|1].twice;
        segTree[i].twice=segTree[i<<1].once+segTree[(i<<1)|1].once;
        segTree[i].once=segTree[i].rf-segTree[i].lf-segTree[i].more-segTree[i].twice;
    }
    else
    {
        if(segTree[i].l+1==segTree[i].r)
        {
            segTree[i].more=segTree[i].once=segTree[i].twice=0;
            return;
        }
        segTree[i].more=segTree[i<<1].more+segTree[(i<<1)|1].more;
        segTree[i].twice=segTree[i<<1].twice+segTree[(i<<1)|1].twice;
        segTree[i].once=segTree[i<<1].once+segTree[(i<<1)|1].once;
    }
}
void update(int i,Line e)
{
    if(segTree[i].lf>=e.y1 && segTree[i].rf<=e.y2)
    {
        segTree[i].c+=e.f;
        push_up(i);
        return;
    }
    if(e.y2<=segTree[i<<1].rf) update(i<<1,e);
    else if(e.y1>=segTree[(i<<1)|1].lf) update((i<<1)|1,e);
    else
    {
        Line temp=e;
        temp.y2=segTree[i<<1].rf;
        update(i<<1,temp);
        temp=e;
        temp.y1=segTree[(i<<1)|1].lf;
        update((i<<1)|1,temp);
    }
    push_up(i);
}
Line temp[MAXN];
int main()
{
    int T;
    int n;
    int x1,y1,z1,x2,y2,z2;
    scanf("%d",&T);
    int iCase=0;
    while(T--)
    {
        iCase++;
        scanf("%d",&n);
        int t=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].z1=z1;
            line[t].z2=z2;
            line[t].f=1;
            y[t]=y1;
            z[t++]=z1;

            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].z1=z1;
            line[t].z2=z2;
            line[t].f=-1;
            y[t]=y2;
            z[t++]=z2;
        }
        sort(line,line+t,cmp);
        sort(y,y+t);
        int t1=unique(y,y+t)-y;
        Build(1,0,t1-1);
        sort(z,z+t);
        int t2=unique(z,z+t)-z;
        long long ans=0;
        long long area=0;
        for(int i=0;i<t2-1;i++)
        {
            int m=0;
            for(int j=0;j<t;j++)
              if(line[j].z1<=z[i]&&line[j].z2>z[i])
                 temp[m++]=line[j];
            area=0;
            update(1,temp[0]);
            for(int j=1;j<m;j++)
            {
                area+=(long long)segTree[1].more*(temp[j].x-temp[j-1].x);
                update(1,temp[j]);
            }
            ans+=area*(z[i+1]-z[i]);
        }
        printf("Case %d: %I64d
",iCase,ans);
    }
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/gongpixin/p/5360647.html