首页 > 代码库 > poj 2777
poj 2777
题意:两个操作:c l r x l到r之间的颜色变成x
q l r 询问l到r有多少种颜色
思路:记一个整数表示哪种颜色是否取了
这里真的是煞笔了,看到这一题第一直觉是异或,但是A^A=0,相同的肿么办..然后搜题解....反应了一个下午,发现有按位或这样神气的存在
1|1=1
1|0=1
0|1=1
0|0=0
代码
#include "stdio.h"#include "string.h"#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#include "algorithm"#define MAX 100010using namespace std;int sum[MAX<<2],col[MAX<<2];void pushup(int rt){ sum[rt]=(sum[rt<<1]|sum[rt<<1|1]);}void pushdown(int rt){ if(col[rt]) { col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=sum[rt<<1|1]=1<<(col[rt]-1); col[rt]=0; }}void build(int l,int r,int rt){ col[rt]=0; if(l==r) { sum[rt]=1; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt);}void update(int L,int R,int c,int l,int r,int rt){ if(l>=L&&r<=R) { col[rt]=c; sum[rt]=1<<(c-1); return; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); pushup(rt);}int query(int L,int R,int l,int r,int rt){ if(l>=L&&r<=R) { return sum[rt]; } pushdown(rt); int ans=0; int m=(l+r)>>1; if(L<=m) ans=(ans|query(L,R,lson)); if(R>m) ans=(ans|query(L,R,rson)); return ans;}int main(){ int n,l,r,col,x; int q; char s[10]; while(scanf("%d%d%d",&n,&col,&q)==3) { build(1,n,1); while(q--) { scanf("%s",s); if(s[0]==‘C‘) { scanf("%d%d%d",&l,&r,&x); if(l>r) l^=r^=l^=r; update(l,r,x,1,n,1); } else { scanf("%d%d",&l,&r); if(l>r) l^=r^=l^=r; int temp=query(l,r,1,n,1); int ans=0; while(temp) { if(temp&1) ans++; temp/=2; } printf("%d\n",ans); } } } return 0;}
poj 2777
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。