poj-2777セグメントツリーブラシ問題

title:poj-2777セグメントツリーブラシ問題date:2018-10-16 20:01:07 tags:

acm

ブラシ問題categories:

ACM-線分ツリー

概要

この問題は線分樹の染色問題で、、、
いくつかの染色の问题をして、だんだん熟知している染色の问题の大まかな解体の考え方のようで、、、もう最初の时のようにぼんやりしていないで、、、ブログをめくって他の人の考えを见るしかなくて、、、どうやら今回他の人のブログを见て自分で书いて、、(いくつかの细部を除いてwaの1発を考えていないで、、、逃げます

分析と構想

問題面

1つの区間に1~n、、、そして最大30色、、、q回の操作で[l,r]という区間を染色し、、、、真ん中にいくつかの質問区間[l,r]内に全部でいくつかの色があり、、、

ぶんせき

まず線分樹がメンテナンスしているものを考えて、、、染色問題の多くは各区間の色をメンテナンスして、、、、この問題に対してその区間の色をメンテナンスする種類で、、、それから2つのサブ区間ごとに上へ色をマージする種類に対して、、、、同じ無視側の違いに1を加えて、、、親区間の種類数を求めて、、、、つまり更新操作、、问い合わせは再问の区间[L,R]で直接上海に戻る区间の种类数、、、区间をまたぐ再帰を下に探し続け、、、

それから色を考えて、、、せいぜい全部で30種類、、、、、もし区間ごとに1つの30長の配列col[30]で各色の種類を保存していたら、col[i]==1はこの区間にi番目の色があることを示しています逆にないと、、、、空間消費が大きく、、、しかも関連する操作も表現しにくいです.だから状態圧縮を選んで実現するのが比較的に良くて、、、ここで私はこの間見た1つのとても良い状圧stl--bitsetを思って、、、、利点はたくさんあって、、、例えば:彼はboolの配列のようですが、1人1 bitしか占めていません.

もう一つ注意しなければならないのは、セグメントツリーがlazyを選択することです.
区間の併合には、更新や問い合わせの初期時を含むすべての区間が1である区間全体が染色されたときに当該区間をnode[rt]とする.colをcに変更して、、、ではなくて、あるいはもう一人の最も穴の人の、、、、テーマはl<=rを保証しないで、、(pojの上の問題はすべてこのようにしますか、、プププププププププププププププププププププププププププププププププププププププププププ

コード#コード#

今回はまたnode構造体と書いて実現したのですが、、、やはりこれが分かりやすいので、、、
しかし欠点は占有する空間が比較的に大きいことで、、、
今度この問題を書くときはもう一つの裸QQQに変えなければなりません.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define aaa cout << node[rt].col << endl;
const int maxn = 1e5 + 10;
struct node
{
    int l;
    int r;
    int laz;
    bitset<30> col;         //bitset,, 
}node[maxn << 2];

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)
    {
        node[rt].col = 1;   // 1
        return;
    }
    int mid = (node[rt].l + node[rt].r) >> 1;
    build(lson);
    build(rson);
    node[rt].col = node[rt << 1].col | node[rt << 1 | 1].col; // ，， 
    return;
}
void pushdown(int rt)
{
    if(node[rt].laz)
    {
        bitset<30> t;
        t.set(node[rt].laz - 1);    // laz 
        node[rt << 1].col = t;      // 
        node[rt << 1 | 1].col = t;

        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)
{
    // ，，， ，，， bitset<30>
    //   .count()
    if(L <= node[rt].l && node[rt].r <= R)
    {
        return node[rt].col;
    }
    pushdown(rt);
    int mid = (node[rt].l + node[rt].r) >> 1;

    bitset<30> ans (0);
    if(L <= mid)    ans |= query(rt << 1 , L , R);      // 
    if(R >  mid)    ans |= query(rt << 1 | 1 , L , R);
    //cout << ans << endl;
    return ans;
}
int main()
{
    int n , t , m;
    while(scanf("%d%d%d" , &n , &t , &m) != EOF)
    {
        build(1 , 1 , n);
        while(m--)
        {
            char q;
            scanf(" %c" , &q);
            if(q == 'C')
            {
                int l , r , c;
                scanf("%d%d%d", &l , &r , &c);
                if(l > r)   swap(l , r);        // ！！！！
                update(1 , l , r , c);
            }
            else
            {
                int l , r;
                scanf("%d%d" , &l , &r);
                if(l > r)   swap(l , r);
                printf("%d
" , query(1 , l , r).count());
            }
        }
    }
}

感想

もういいQQQは言わない
(end)