題目背景

阿寶上學(xué)了，今天老師拿來(lái)了一塊很長(zhǎng)的涂色板。

題目描述

色板長(zhǎng)度為\(L\)，\(L\)是一個(gè)正整數(shù)，所以我們可以均勻地將它劃分成\(L\)塊\(1\)厘米長(zhǎng)的小方格。并從左到右標(biāo)記為\(1, 2, ... L\)。

現(xiàn)在色板上只有一個(gè)顏色，老師告訴阿寶在色板上只能做兩件事：

"\(C\) \(A\) \(B\) \(C\)" 指在\(A\)到 \(B\) 號(hào)方格中涂上顏色 \(C\)。

"\(P\) \(A\) \(B\)"指老師的提問(wèn)：\(A\)到 \(B\)號(hào)方格中有幾種顏色。

學(xué)校的顏料盒中一共有 \(T\) 種顏料。為簡(jiǎn)便起見(jiàn)，我們把他們標(biāo)記為 \(1, 2, ... T\). 開(kāi)始時(shí)色板上原有的顏色就為\(1\)號(hào)色。 面對(duì)如此復(fù)雜的問(wèn)題，阿寶向你求助，你能幫助他嗎？

輸入輸出格式

輸入格式：

第一行有\(3\)個(gè)整數(shù) \(L (1 \leq L \leq 100000)\), \(T (1 \leq T \leq 30)\) 和 \(O (1 \leq O \leq 100000)\)。 在這里\(O\)表示事件數(shù)。
接下來(lái) \(O\) 行, 每行以 "\(C\) \(A\) \(B\) \(C\)" 或 "\(P\) \(A\) \(B\)" 得形式表示所要做的事情(這里 \(A\), \(B\), \(C\) 為整數(shù), 可能\(A\)> \(B\)，這樣的話(huà)需要你交換\(A\)和\(B\))

輸出格式：

對(duì)于老師的提問(wèn)，做出相應(yīng)的回答。每行一個(gè)整數(shù)。

輸入輸出樣例

輸入樣例#1：

2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2

輸出樣例#1：

2 1

思路：正解貌似是基于二進(jìn)制來(lái)建線段樹(shù)，但是我不會(huì)……于是我就非常暴力的建了\(t\)棵線段樹(shù)，因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(t\)只有\(30\)嘛，所以建\(30\)棵線段樹(shù)也不會(huì)爆，沒(méi)棵線段樹(shù)代表一個(gè)顏色，然后對(duì)于每一個(gè)\(C\)操作，就是修改要修改的那個(gè)顏色的對(duì)應(yīng)線段樹(shù)的對(duì)應(yīng)修改區(qū)間為\(1\)，其余線段樹(shù)的對(duì)應(yīng)修改區(qū)間修改為\(0\)，然后查詢(xún)就是把每棵線段樹(shù)的區(qū)間顏色數(shù)加起來(lái)。但是代碼可能因?yàn)槌?shù)優(yōu)化的不太好等原因，不開(kāi)\(O(2)\)會(huì)\(TLE\)一個(gè)點(diǎn)。

代碼：

#include<cstdio> #include<algorithm> #define maxn 100007 #define ls rt<<1 #define rs rt<<1|1 #define re register using namespace std; int n,t,m,sum[31][maxn<<2],lazy[31][maxn<<2]; char s[2]; inline void pushup(int i, int rt) {sum[i][rt]=sum[i][ls]+sum[i][rs]; } inline void pushdown(int i, int rt) {if(lazy[i][rt]==-1) {sum[i][ls]=sum[i][rs]=0;lazy[i][ls]=lazy[i][rs]=-1; }else {lazy[i][ls]=lazy[i][rs]=lazy[i][rt];sum[i][ls]=sum[i][rs]=lazy[i][rt];}lazy[i][rt]=0; } void build(int rt, int l, int r) {if(l==r) {sum[1][rt]=1;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(1,rt); } void modify(int i, int rt, int l, int r, int L, int R, int val) {if(L>r||R<l) return;if(L<=l&&r<=R) {sum[i][rt]=val;if(!val) lazy[i][rt]=-1;else lazy[i][rt]=val;return;}if(lazy[i][rt]) pushdown(i,rt);int mid=(l+r)>>1;if(L<=mid) modify(i,ls,l,mid,L,R,val);if(R>mid) modify(i,rs,mid+1,r,L,R,val);pushup(i,rt); } int csum(int i, int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return sum[i][rt];if(lazy[i][rt]) pushdown(i,rt);int mid=(l+r)>>1;return csum(i,ls,l,mid,L,R)+csum(i,rs,mid+1,r,L,R); } int main() {scanf("%d%d%d",&n,&t,&m);build(1,1,n);for(re int i=1,l,r,v;i<=m;++i) {scanf("%s%d%d",s,&l,&r);if(l>r) swap(l,r);if(s[0]=='C') {scanf("%d",&v);for(re int k=1;k<=t;++k) {if(k!=v) modify(k,1,1,n,l,r,0);else modify(k,1,1,n,l,r,1);}}else {int zrj=0;for(re int k=1;k<=t;++k) if(csum(k,1,1,n,l,r)) zrj++;printf("%d\n",zrj);}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/grcyh/p/10172894.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1558 色板游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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