---

title: hdu-5023线段树刷题

date: 2018-10-18 13:32:13

tags:

• acm
• 刷题
  
  categories:
• ACM-线段树

---

概述

这道题和上次做的那道染色问题一样，，，这次主要是看看我再过去两三天之后，，大概凭借以前的记忆敲出来得多长的时间，，，，

结果是，，，大体的框架没问题了，，，，一遍下来编译也没问题，，，但是，，细节问题有两个，，，

• 数组写成了1e6而不是1e6+10虽然对本题没什么影响，，
• 建树中的初始化操作时染色初始化为2，，，所以应该是从右往左数的第二个bit记为1，，，然后我就少算了一位，，，因为bitset可以看作是一个从右向左并且从0开始的数组，，所以是col[1] = 1，，，这样wa了一发
• 最后一个，，，，输出格式错误，，，，噗噗噗噗

代码

思路与poj那一道一模一样，，直接扔代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <bitset>

using namespace std;

const int maxn = 1e6 + 10;

struct node

{

    int l;

    int r;

    int laz;

    bitset<30> col;

}node[maxn << 2];

#define aaa cout << node[rt].col << endl;

void build(int rt , int l , int r)

{

    node[rt].l = l;

    node[rt].r = r;

    node[rt].laz = 0;

    node[rt].col = 0;

    if(node[rt].l == node[rt].r)

    {

        bitset<30> t;

        t.set(1);

        node[rt].col = t;

        return;

    }

    int mid = (node[rt].l + node[rt].r) >> 1;

    build(rt << 1 , l , mid);

    build(rt << 1 | 1 , mid + 1 , r);

    node[rt].col = node[rt << 1].col | node[rt << 1 | 1].col;

    return;

}

void pushdown(int rt)

{

    if(node[rt].laz)

    {

        node[rt << 1].col = node[rt].col;

        node[rt << 1 | 1].col = node[rt].col;

        node[rt << 1].laz = node[rt].laz;

        node[rt << 1 | 1].laz = node[rt].laz;

        node[rt].laz = 0;

    }

}

void update(int rt , int L , int R , int C)

{

    if(L <= node[rt].l && node[rt].r <= R)

    {

        bitset<30> t;

        t.set(C - 1);

        node[rt].col = t;

        node[rt].laz = C;

        return;

    }

    pushdown(rt);

    int mid = (node[rt].l + node[rt].r) >> 1;

    if(L <= mid)    update(rt << 1 , L , R , C);

    if(R >  mid)    update(rt << 1 | 1 , L , R , C);

    node[rt].col = node[rt << 1].col | node[rt << 1 | 1].col;

    return;

}

bitset<30> query(int rt , int L , int R)

{

    if(L <= node[rt].l && node[rt].r <= R)

    {

        return node[rt].col;

    }

    pushdown(rt);

    bitset<30> ans(0);

    int mid = (node[rt].l + node[rt].r) >> 1;

    if(L <= mid)    ans |= query(rt << 1 , L , R);

    if(R >  mid)    ans |= query(rt << 1 | 1 , L , R);

    return ans;

}

int main()

{

    int n , m;

    while(scanf("%d%d" , &n , &m) && n && m)

    {

        build(1 , 1 , n);

        while(m--)

        {

            char c;

            scanf(" %c" , &c);

            if(c == 'P')

            {

                int l , r , v;

                scanf("%d%d%d" , &l , &r , &v);

                update(1 , l , r , v);

            }

            else

            {

                int l , r;

                scanf("%d%d" , &l , &r);

                bitset<30> ans = query(1 , l , r);

                bool flag = true;

                for(int i = 1; i <= 30; ++i , ans>>=1)

                    if(ans[0] == 1)

                        if(flag)

                        printf("%d" , i) , flag = false;

                        else

                        printf(" %d" , i);

                printf("\n");

            }

        }

    }

}

先水一题，，，下午继续QAQ

(end)