线段树-小学期考核

女爷i 2022-09-25 14:20 138阅读 0赞

题目大意 ：本题为POJ2777的改编题 ：[poj2777][]  数据比poj弱了点，可以不用状压 ！   给你n个花盆（n<=100000  ），这里有30种花， 初始时没盆花都种的种类为1的花，现在给你 q 个操作 1， P a,b,c  （把区间\[a,b\]的花改为种类为c的花） 2，Q a b （查询区间\[a,b\]中有多少种花并输出）

题目思路：首先看到题目第一想到的是线段树，然后就想线段树的节点维护的是什么，容易想到的是区间的花的种类数，但是一般的方法不好实现满足区间的减法，这里就有一个相对暴力的方法，用一个标记数组和种类计数的数组，当然我不推荐这种做法，因为我当时也不是这样想的。因为种类只有30，所以就不难想到用状态压缩，用30位的二进制位表示花的种类，0表示没有该种花，1表示有，这里有一个二进制的或运算的技巧，0|1=1 ,1|1=1;  所以就可以实现花的种类的加法，因此就不难想到用线段树的节点来维护这个值！

定义：

sto\[\] 数组为线段树节点数组 cover\[\]数组为懒惰标记数组

建树：

cover\[\]数组初始化为1  二进制 为  1（前面的0省略了）  第一位为1表示种类为1的花  ，向上更新函数为 两个子节点的或运算结果---实现种类的加法！

void Push(int rt)
    {
        sto[rt]=sto[rt<<1]|sto[rt<<1|1];
    }
    void BuildTree(int l,int r,int rt)
    {
        cover[rt]=0;
        if(l==r)
        {
            sto[rt]=1;
            return ;
        }
        int mid=(l+r)>>1;
        BuildTree(lson);
        BuildTree(rson);
        Push(rt);
    }

更新函数：

向下更新函数：因为更新的是整个区间都改为同一种种类，所以直接把父节点的caver值赋值给子节点，子节点的值就是父节点的cover值（这里用十进制表示）

区间更新：和普通的线段树的区间更新函数一样，只要改向上向下更新函数即可！

void PushDown(int rt,int cnt)
    {
        if(cover[rt])
        {
            cover[rt<<1]=cover[rt];
            cover[rt<<1|1]=cover[rt];
            sto[rt<<1]=cover[rt];
            sto[rt<<1|1]=cover[rt];
            cover[rt]=0;
        }
    }
    
    void Update(int L,int R,int v,int l,int r,int rt)
    {
        if(L<=l&&r<=R)
        {
            cover[rt]=v;
            sto[rt]=v;
            return ;
        }
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        if(L<=mid) Update(L,R,v,lson);
        if(mid<R)Update(L,R,v,rson);
        Push(rt);
    }

查询函数：

和普通的区间查询函数相似，只是把区间加法运算改为或运算来实现区间的加法！

int query(int L,int R,int l,int r,int rt)
    {
        if(L <=l && r<=R) return sto[rt];
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        int  res=0;
        if(L<=mid)res=query(L,R,lson)|res;
        if(mid<R) res=query(L,R,rson)|res;
        return res;
    }

主函数：

前面是题目的输入要求，输入 P a,b,c 时   因为c为种类十进制数，所以要把转换成二进制的种类数   比如种类2为 10  种类3为 100 种类4 为1000  ......   然后在把二进制的种类数转换成十进制的数，10为2^1=2 ,100为2^2=4， 1000为2^3 = 8 ......这个只要用个循环就可以算出，，！   输入 Q a b 时    此时调用查询函数，返回的是一个十进制数，然后转换成二进制数（本身就可以当成二进制数进行计数，这里只是一种说法），这里用到了与运算来计数，因为0&1 = 0  1&1 = 1 ,所以就可以拿返回的值与1进行与运算，如果为1就表示当前位置上有该种类的花否则没有，也就是下面的代码的那个while循环，最后统计出来的就是要的答案！

int main()
    {
        int n,q;
         while(~scanf("%d%d",&n,&q))
         {
    
              BuildTree(1,n,1);
              while(q--)
              {
                   char str[5];
                   scanf("%s",str);
                   if(str[0]=='Q')
                   {
                        int l,r;
                        scanf("%d%d",&l,&r);
                        int x=query(l,r,1,n,1);
                        int ans=0;
                        while(x){
                            if(x&1==1)ans++;
                            x=x/2;
                        }
                       printf("%d\n",ans);
                   }
                   else
                   {
                        int  x,y,z;
                        scanf("%d%d%d",&x,&y,&z);
                        int ans=0;
                        int ss=1;
                        for(int i=1;i<z;i++){
                            ss*=2;
                        }
                        ans+=ss;
                        Update(x,y,ans,1,n,1);
                   }
              }
         }
        return 0;
    }

完整的AC代码：

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
    const int maxn=2e5+100;
    int  sto[maxn<<2];
    int  cover[maxn<<2];
    
    void PushDown(int rt,int cnt)
    {
        if(cover[rt])
        {
            cover[rt<<1]=cover[rt];
            cover[rt<<1|1]=cover[rt];
            sto[rt<<1]=cover[rt];
            sto[rt<<1|1]=cover[rt];
            cover[rt]=0;
        }
    }
    void Push(int rt)
    {
        sto[rt]=sto[rt<<1]|sto[rt<<1|1];
    }
    void BuildTree(int l,int r,int rt)
    {
        cover[rt]=0;
        if(l==r)
        {
            sto[rt]=1;
            return ;
        }
        int mid=(l+r)>>1;
        BuildTree(lson);
        BuildTree(rson);
        Push(rt);
    }
    void Update(int L,int R,int v,int l,int r,int rt)
    {
        if(L<=l&&r<=R)
        {
            cover[rt]=v;
            sto[rt]=v;
            return ;
        }
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        if(L<=mid) Update(L,R,v,lson);
        if(mid<R)Update(L,R,v,rson);
        Push(rt);
    }
    int query(int L,int R,int l,int r,int rt)
    {
        if(L <=l && r<=R) return sto[rt];
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        int  res=0;
        if(L<=mid)res=query(L,R,lson)|res;
        if(mid<R) res=query(L,R,rson)|res;
        return res;
    }
    int main()
    {
        int n,q;
         while(~scanf("%d%d",&n,&q))
         {
    
              BuildTree(1,n,1);
              while(q--)
              {
                   char str[5];
                   scanf("%s",str);
                   if(str[0]=='Q')
                   {
                        int l,r;
                        scanf("%d%d",&l,&r);
                        int x=query(l,r,1,n,1);
                        int ans=0;
                        while(x){
                            if(x&1==1)ans++;
                            x=x/2;
                        }
                       printf("%d\n",ans);
                   }
                   else
                   {
                        int  x,y,z;
                        scanf("%d%d%d",&x,&y,&z);
                        int ans=0;
                        int ss=1;
                        for(int i=1;i<z;i++){
                            ss*=2;
                        }
                        ans+=ss;
                        Update(x,y,ans,1,n,1);
                   }
              }
         }
        return 0;
    }

POJ上的AC代码：

只要在输入时多加个种类变量T  其实没有啥用 ，只需考虑最多为30种  还有就是它的区间输入不一定是从左往右的，所以还要做个判断！！！

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
    const int maxn=2e5+100;
    int  sto[maxn<<2];
    int  cover[maxn<<2];
    
    void PushDown(int rt,int cnt)
    {
        if(cover[rt])
        {
            cover[rt<<1]=cover[rt];
            cover[rt<<1|1]=cover[rt];
            sto[rt<<1]=cover[rt];
            sto[rt<<1|1]=cover[rt];
            cover[rt]=0;
        }
    }
    void Push(int rt)
    {
        sto[rt]=sto[rt<<1]|sto[rt<<1|1];
    }
    void BuildTree(int l,int r,int rt)
    {
        cover[rt]=0;
        if(l==r)
        {
            sto[rt]=1;
            return ;
        }
        int mid=(l+r)>>1;
        BuildTree(lson);
        BuildTree(rson);
        Push(rt);
    }
    void Update(int L,int R,int v,int l,int r,int rt)
    {
        if(L<=l&&r<=R)
        {
            cover[rt]=v;
            sto[rt]=v;
            return ;
        }
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        if(L<=mid) Update(L,R,v,lson);
        if(mid<R)Update(L,R,v,rson);
        Push(rt);
    }
    int query(int L,int R,int l,int r,int rt)
    {
        if(L <=l && r<=R) return sto[rt];
        PushDown(rt,r-l+1);
        int mid=(l+r)>>1;
        int  res=0;
        if(L<=mid)res=query(L,R,lson)|res;
        if(mid<R) res=query(L,R,rson)|res;
        return res;
    }
    int main()
    {
        int n,q,t;
         while(~scanf("%d%d%d",&n,&t,&q))
         {
    
              BuildTree(1,n,1);
              while(q--)
              {
                   char str[5];
                   scanf("%s",str);
                   if(str[0]=='P')
                   {
                        int l,r;
                        scanf("%d%d",&l,&r);
                        if(l>r)swap(l,r);
                        int x=query(l,r,1,n,1);
                        int ans=0;
                        while(x){
                            if(x&1==1)ans++;
                            x=x/2;
                        }
                       printf("%d\n",ans);
                   }
                   else
                   {
                        int  x,y,z;
                        scanf("%d%d%d",&x,&y,&z);
                        if(x>y)swap(x,y);
                        int ans=0;
                        int ss=1;
                        for(int i=1;i<z;i++){
                            ss*=2;
                        }
                        ans+=ss;
                        Update(x,y,ans,1,n,1);
                   }
              }
         }
        return 0;
    }

[poj2777]: http://poj.org/problem?id=2777