【luogu P1558 色板游戏】 题解

题目链接：https://www.luogu.org/problemnew/show/P1558

我知道三十棵线段树很暴力，可是我们可以状压啊。

颜色最多30，不会爆int

另外 吐槽评测机

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100010;

int n, k, c, q;

class Segment_Tree{

    public:

        #define lson l, mid, rt<<1

        #define rson mid+1, r, rt<<1|1

        int tree[maxn<<2], lazy[maxn<<2];

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

        {

            if(l == r)

            {

                tree[rt] = 1<<1;

                return;

            }

            int mid = (l + r) >> 1;

            build(lson);

            build(rson);

            PushUP(rt);

        }

        void update(int left, int right, int add, int l, int r, int rt)

        {

            if(l >= left && r <= right)

            {

                lazy[rt] = add;

                tree[rt] = (1 << add);

                return;

            }

            int mid = (l + r) >> 1;

            PushDOWN(l, r, rt);

            if(left <= mid) update(left, right, add, lson);

            if(right > mid) update(left, right, add, rson);

            PushUP(rt);

        }

        int query(int left, int right, int l, int r, int rt)

        {

            int res = 0;

            if(l >= left && r <= right)

            {

                return tree[rt];

            }

            int mid = (l + r) >> 1;

            PushDOWN(l, r, rt);

            if(left <= mid) res |= query(left, right, lson);

            if(right > mid) res |= query(left, right, rson);

            return res;

        }

    private:

        void PushUP(int rt)

        {

            tree[rt] = tree[rt<<1] | tree[rt<<1|1];

        }

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

        {

            if(lazy[rt])

            {

                tree[rt<<1] = (1 << lazy[rt]);

                tree[rt<<1|1] = (1 << lazy[rt]);

                lazy[rt<<1] = lazy[rt];

                lazy[rt<<1|1] = lazy[rt];

                lazy[rt] = 0;

            }

        }

}T;

int main()

{

    scanf("%d%d%d",&n,&c,&q);

    T.build(1,n,1);

    for(int i = 1; i <= q; i++)

     {

     	char opt;

     	int x, y, k;

        cin>>opt;

        if(opt=='C')

          {

            scanf("%d%d%d",&x, &y, &k);

            if (x > y) swap(x, y);

            T.update(x, y, k, 1, n, 1);

        }

        else

          {

            scanf("%d%d",&x,&y);

            if (x > y) swap(x, y);

            int res = T.query(x,y,1,n,1), ans=0;

            for (int j = 1; j <= c; j++) if (res & (1 << j)) ans++;

            printf("%d\n",ans);

        }

    }

    return 0;

}