題目鏈接：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|1int 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; }

轉載于:https://www.cnblogs.com/MisakaAzusa/p/9889890.html

總結

以上是生活随笔為你收集整理的【luogu P1558 色板游戏】 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。