貌似很久没有更新blog了?这次对上个学期敲的线段树题目汇个总。 其中关于线段树的内容请移步这篇文章

引子

这些题都是我在上个学期OI“退役”以后在机房苦逼敲的,一直想写个题解总结下啥的但苦于没有时间,现在正好趁着寒假完成这个任务… 在这套题解里包含着HDU,POJ,POI等的各种线段树基本题,实现全部采用链表,欢迎来看。

HDU 1166 敌兵布阵

题目大意

简单的单个节点操作,查询区间和,线段树一敲很容易实现。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=200000+10;
struct Node
{
    int left,right;
    int sum;
}tree[maxn*10];
int T,n,m,a,b,num[maxn];
char s[10];
int build(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    if(left==right)
        return tree[root].sum=num[left];
    int mid=(left+right)>>1;
    int x=build(root*2,left,mid);
    int y=build(root*2+1,mid+1,right);
    return tree[root].sum=x+y;
}
int query(int root,int left,int right)
{
    if(tree[root].right<left||tree[root].left>right)
        return 0;
    if(left<=tree[root].left&&tree[root].right<=right)
        return tree[root].sum;
    int x=query(root*2,left,right);
    int y=query(root*2+1,left,right);
    return x+y;
}
int update(int root,int pos,int val)
{
    if(pos<tree[root].left||pos>tree[root].right)
        return tree[root].sum;
    if(tree[root].left==tree[root].right&&tree[root].left==pos)
        return tree[root].sum=val;
    int x=update(root*2,pos,val);
    int y=update(root*2+1,pos,val);
    return tree[root].sum=x+y;
}
int main()
{
//  freopen("1.sb","r",stdin);
    scanf("%d",&T);
    for(int cnt=1;cnt<=T;cnt++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        build(1,1,n);
        printf("Case %d:\n",cnt);
        while(1)
        {
            scanf("%s",&s);
            if(s[0]=='E')
                break;
            int x,y;
            if(s[0]=='A')   //Add
            {
                scanf("%d%d",&x,&y);
                num[x]+=y;
                update(1,x,num[x]);
            }
            if(s[0]=='S')   //Sub
            {
                scanf("%d%d",&x,&y);
                num[x]-=y;
                update(1,x,num[x]);
            }
            if(s[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",query(1,x,y));
            }
        }
    }
    return 0;
}

HDU 1757 I Hate It

题目大意

单个节点的操作外加查询区间最值,同样容易实现。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=200000+10;
struct Node
{
    int left,right;
    int max;
}tree[maxn*10];
int n,m,a,b,num[maxn];
char s;
inline int max1(int a,int b)
{
    if(a<b)
        return b;
    return a;
}
int bulid(int root,int left,int right)
{
    tree[root].left=left;
    tree[root].right=right;
    if(left==right)
        return tree[root].max=num[left];
    int mid=(left+right)>>1;
    int x=bulid(root*2,left,mid);
    int y=bulid(root*2+1,mid+1,right);
    return tree[root].max=max1(x,y);
}
int query(int root,int left,int right)
{
    if(tree[root].right<left||tree[root].left>right)
        return 0;
    if(left<=tree[root].left&&tree[root].right<=right)
        return tree[root].max;
    int x=query(root*2,left,right);
    int y=query(root*2+1,left,right);
    return max1(x,y);
}
int update(int root,int pos,int val)
{
    if(pos<tree[root].left||pos>tree[root].right)
        return tree[root].max;
    if(tree[root].left==tree[root].right&&tree[root].left==pos)
        return tree[root].max=val;
    int x=update(root*2,pos,val);
    int y=update(root*2+1,pos,val);
    return tree[root].max=max1(x,y);
}
int main()
{
//  freopen("1.sb","r",stdin);
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        bulid(1,1,n);
        while(m--)
        {
            cin>>s;
              
            scanf("%d %d",&a,&b);
            if(s=='Q')
            {
                printf("%d\n",query(1,a,b));
            }
            else
            {
                num[a]=b;
                update(1,a,b);
            }
        }
    }
    return 0;
}

HDU 1698 Just a Hook

题目大意

他怎么知道我打dota(逃…)。 将整个区间赋值为同一个数,这里需要用到lazy-tag。额外维护两个域en来表示一个区间是否为统一的数,若en有效,则data表示区间统一的值。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1000+10;
struct Node
{
    int left,right;
    int delta,data,sum;
    bool en;
    Node *leftchild,*rightchild;
};
int T,n,q,x,y,z;
void build(Node *cur,int l,int r)
{
    cur->left=l;
    cur->right=r;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
    }
    else
        cur->leftchild=cur->rightchild=NULL;
}
void clear(Node *cur)
{
    if(cur->left!=cur->right)
    {
        clear(cur->leftchild);
        clear(cur->rightchild);
    }
    free(cur);
}
int calcsum(Node *cur)
{
    if(cur->en)
        return (cur->right-cur->left+1)*cur->data;
    else
        return cur->sum;
}
void update(Node *cur,int l,int r,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->en)
    {
        if(lc!=NULL)
        {
            lc->data=cur->data;
            lc->en=true;
        }
        if(rc!=NULL)
        {
            rc->data=cur->data;
            rc->en=true;
        }
        cur->en=false;
    }
    if((l<=cur->left)&&(cur->right<=r))
    {
        cur->en=true;
        cur->data=num;
    }
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,num);
        if(r>(cur->left+cur->right)/2)
            update(rc,l,r,num);
        cur->sum=calcsum(lc)+calcsum(rc);
    }
}
int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=calcsum(cur);
    else
    {
        if(cur->en)
        {
            lc->data=cur->data;
            lc->en=true;
            rc->data=cur->data;
            rc->en=true;
            cur->en=false;
        }
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
        cur->sum=lc->sum+rc->sum;
    }
    return ret;
}
int main()
{
//    freopen("1.sb","r",stdin);
    scanf("%d",&T);
    for(int cnt=1;cnt<=T;cnt++)
    {
        scanf("%d%d",&n,&q);
//        root=NULL;
        Node *root=new Node;
        build(root,1,n);
        update(root,1,n,1);
        while(q--)
        {
            scanf("%d%d%d",&x,&y,&z);
            update(root,x,y,z);
        }
        printf("Case %d: The total value of the hook is %d.\n",cnt,querysum(root,1,n));
        clear(root);
    }
    return 0;
}

POJ 3468 A Simple Problem with Integers

题目大意

虽然题干是英文但应该也好懂,将区间整体加上一个数并且询问区间和,同样可以使用lazy-tag进行维护,但注意数据貌似会爆int?

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100000+10;
typedef long long LL;
struct Node
{
    int left,right;
    LL delta,sum;
    Node *leftchild,*rightchild;
};
int T,n,q,x,y,z,num[maxn];
char s;
void build(Node *cur,int l,int r)
{
    cur->left=l;
    cur->right=r;
    cur->delta=0;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
        cur->sum=cur->leftchild->sum+cur->rightchild->sum;
        //cout<<cur->sum<<endl;
    }
    else
    {
        cur->sum=num[l];
        //cout<<cur->sum<<endl;
        cur->leftchild=cur->rightchild=NULL;
    }
         
}
void update(Node *cur,int l,int r,int delta)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if((l<=cur->left)&&(cur->right<=r))
        cur->delta+=delta;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,delta);
        if(r>(cur->left+cur->right)/2)
            update(rc,l,r,delta);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
}
LL query(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    LL ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=cur->sum+cur->delta*(cur->right-cur->left+1);
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->delta=0;
        if(l<=(cur->left+cur->right)/2)
            ret+=query(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=query(rc,l,r);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
    return ret;
}
int main()
{
//  freopen("1.sb","r",stdin);
    scanf("%d%d",&n,&q);
    Node *root=new Node;
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    build(root,1,n);
    for(int i=1;i<=q;i++)
    {
        cin>>s;
        if(s=='Q')
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(root,x,y));
        }
        else
        {
            scanf("%d%d%d",&x,&y,&z);
            update(root,x,y,z);
        }
    }
     
    return 0;
}

POI 2001 Railways

题目大意

传说中的POI原题哦。同样的可以转化成区间整体加数并且询问区间和的问题。然而这个题目有点坑,一开始提交总是a不掉,最后去POI摸了数据手工对照才发现如果两个区间出现这种情况:[1,3],[3,6],这样的话即使3这个节点超过了最大值,那么还是可行的。这里我用的处理方法是将区间的上介减1,然后再insert()的方法,具体看代码。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct Node
{
    int left,right;
    int max,delta;
    Node *leftchild,*rightchild;
};
int n,m,r,k1,k2,v;
void build(Node *cur,int l,int r)
{
    cur->left=l,cur->right=r,cur->max=0,cur->delta=0;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
    }
    else
        cur->leftchild=cur->rightchild=NULL;
}
void update(Node *cur,int l,int r,int delta)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if((l<=cur->left)&&(cur->right<=r))
        cur->delta+=delta;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,delta);
        if(r>(cur->left+cur->right)/2)
            update(rc,l,r,delta);
        //\cur->max+=cur->delta;
        //cout<<cur->max<<endl;
        cur->max=max(cur->max,lc->max+lc->delta);
        cur->max=max(cur->max,rc->max+rc->delta);
    }
}
int query(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret=cur->max+cur->delta;
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->max+=cur->delta;
        cur->delta=0;
        if(l<=(cur->left+cur->right)/2)
        {
            int x=query(lc,l,r);
            ret=max(ret,x);
        }
        if(r>(cur->left+cur->right)/2)
        {
            int x=query(rc,l,r);
            ret=max(ret,x);
        }
        cur->max=max(cur->max,lc->max+lc->delta);
        cur->max=max(cur->max,rc->max+rc->delta);
    }
    return ret;
}
int main()
{
    //freopen("1.sb","r",stdin);
    scanf("%d%d%d",&n,&m,&r);
    Node *root=new Node;
    build(root,1,n-1);
    while(r--)
    {
        scanf("%d%d%d",&k1,&k2,&v);
        //update(root,k1,k2,v);
        //cout<<query(root,1,4)<<endl;
        int maxx=query(root,k1,k2-1);
        //cout<<maxx<<endl;
        if(maxx+v<=m)
        {
            printf("T\n");
            update(root,k1,k2-1,v);
        }
        else
            printf("F\n");
    }
    return 0;
}

POJ 2777 Count Color

题目大意

英文题,但仍然很好懂。将区间整体赋值,并且查询区间中不同数的个数。这个题的技巧在于颜色总共只有30种,那么我们可以用位操作表示每一种颜色,父节点的颜色即为子节点的按位或(or),最后1的个数即为不同颜色的个数。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
struct Node
{
    int left,right,data;
    int color;
    Node *leftchild,*rightchild;
    bool cover;
};
int n,t,o,x,y,z,cnt;
void build(Node *cur,int l,int r)
{
    cur->left=l;
    cur->right=r;
    cur->color=1;
    cur->cover=false;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
    }
    else
        cur->leftchild=cur->rightchild=NULL;
}
void update(Node *cur,int l,int r,int value)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==l&&cur->right==r)
    {
        cur->color=(1<<(value-1));
        cur->cover=true;
        return;
    }
    if(cur->cover)
    {
        cur->cover=false;
        lc->cover=true;
        rc->cover=true;
        lc->color=cur->color;
        rc->color=cur->color;
    }
    int mid=(cur->left+cur->right)/2;
    if(r<=mid)
        update(lc,l,r,value);
    else if(l>mid)
        update(rc,l,r,value);
    else
    {
        update(lc,l,mid,value);
        update(rc,mid+1,r,value);  
    }
    cur->color=lc->color|rc->color;
}
void query(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->cover||(cur->left==l&&cur->right==r))
    {
        cnt|=cur->color;
        return;
    }
    int mid=(cur->left+cur->right)/2;
    if(r<=mid)
        query(lc,l,r);
    else if(l>mid)
        query(rc,l,r);
    else
    {
        query(lc,l,mid);
        query(rc,mid+1,r); 
    }  
}
int main()
{
//  freopen("1.sb","r",stdin);
    scanf("%d%d%d",&n,&t,&o);
    Node *root=new Node;
    build(root,1,n);
    while(o--)
    {
        char ch;
        scanf(" %c ",&ch);
        //cout<<ch<<endl;
        //cin>>ch;
        if(ch=='C')
        {
            scanf("%d%d%d",&x,&y,&z);
            if(x>y)
                swap(x,y);
            update(root,x,y,z);
        }
        else
        {
            scanf("%d%d",&x,&y);
            if(x>y)
                swap(x,y);
            cnt=0;
            int ans=0;
            query(root,x,y);
            for(int i=0;i<t;i++)
                if(cnt&(1<<i))
                    ans++;
            printf("%d\n",ans);
        }
    }
    return 0;
}

结语

这些题主要都属于一些模板类的题,但其中也不乏技巧类的东西。而线段树的精髓也在于,当线段完全覆盖一个节点区间时可以直接对这个节点打上标记,而不需要一直做下去。