欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

洛谷P1558 色板游戏

发布时间:2024/7/5 编程问答 2 豆豆
如意编程网 收集整理的这篇文章主要介绍了 洛谷P1558 色板游戏 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目背景

阿宝上学了,今天老师拿来了一块很长的涂色板。

题目描述

色板长度为\(L\)\(L\)是一个正整数,所以我们可以均匀地将它划分成\(L\)\(1\)厘米长的小方格。并从左到右标记为\(1, 2, ... L\)

现在色板上只有一个颜色,老师告诉阿宝在色板上只能做两件事:

  • "\(C\) \(A\) \(B\) \(C\)" 指在\(A\)\(B\) 号方格中涂上颜色 \(C\)
  • "\(P\) \(A\) \(B\)"指老师的提问:\(A\)\(B\)号方格中有几种颜色。
  • 学校的颜料盒中一共有 \(T\) 种颜料。为简便起见,我们把他们标记为 \(1, 2, ... T\). 开始时色板上原有的颜色就为\(1\)号色。 面对如此复杂的问题,阿宝向你求助,你能帮助他吗?

    输入输出格式

    输入格式:

    第一行有\(3\)个整数 \(L (1 \leq L \leq 100000)\), \(T (1 \leq T \leq 30)\)\(O (1 \leq O \leq 100000)\)。 在这里\(O\)表示事件数。
    接下来 \(O\) 行, 每行以 "\(C\) \(A\) \(B\) \(C\)" 或 "\(P\) \(A\) \(B\)" 得形式表示所要做的事情(这里 \(A\), \(B\), \(C\) 为整数, 可能\(A\)> \(B\),这样的话需要你交换\(A\)\(B\))

    输出格式:

    对于老师的提问,做出相应的回答。每行一个整数。

    输入输出样例

    输入样例#1:

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

    输出样例#1:

    2 1

    思路:正解貌似是基于二进制来建线段树,但是我不会……于是我就非常暴力的建了\(t\)棵线段树,因为\(t\)只有\(30\)嘛,所以建\(30\)棵线段树也不会爆,没棵线段树代表一个颜色,然后对于每一个\(C\)操作,就是修改要修改的那个颜色的对应线段树的对应修改区间为\(1\),其余线段树的对应修改区间修改为\(0\),然后查询就是把每棵线段树的区间颜色数加起来。但是代码可能因为常数优化的不太好等原因,不开\(O(2)\)\(TLE\)一个点。

    代码:

    #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; }

    转载于:https://www.cnblogs.com/grcyh/p/10172894.html

    总结

    以上是如意编程网为你收集整理的洛谷P1558 色板游戏的全部内容,希望文章能够帮你解决所遇到的问题。

    如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。