锐客网

  1. 首页 > it技术 > >

-----------|POJ 2777 Count Color 线段树 区间更新

【-----------|POJ 2777 Count Color 线段树 区间更新】题目链接： http://poj.org/problem?id=2777
代码：

#include #include #include #include #define sf scanf #define pf printf using namespace std; typedef long long LL; const int maxn = 100000 + 5; int col[maxn * 4],laze[4 * maxn]; void init(int n){ for(int i = 0; i <= 4 * n + 50; ++i) col[i] = 2; memset(laze,0,sizeof(laze)); }void PushUp(int rt){ col[rt] = col[rt << 1] | col[rt << 1 | 1]; }void PushDown(int rt){ if(laze[rt]){ col[rt << 1] = 1 << laze[rt]; col[rt << 1 | 1] = 1 << laze[rt]; laze[rt << 1] = laze[rt << 1 | 1] = laze[rt]; laze[rt] = 0; } }void update(int rt,int cl,int cr,int l,int r,int v){ if(l > cr || r < cl) return; //当前区间完全不包含目标区间 if(l <= cl && r >= cr){//当前区间被目标区间完全包含 laze[rt] = v; col[rt] = 1ll << v; return; } PushDown(rt); int mid = (cl + cr) / 2; update(rt << 1,cl,mid,l,r,v); update(rt << 1|1,mid + 1,cr,l,r,v); PushUp(rt); }int query(int rt,int cl,int cr,int l,int r){ if(l > cr || r < cl) return 0; if(l <= cl && r >= cr){//当前区间被目标区间完全包含 return col[rt]; } PushDown(rt); int mid = (cl + cr) / 2,ret = 0; ret = query(rt << 1,cl,mid,l,r); ret = ret | query(rt << 1|1,mid + 1,cr,l,r); returnret; }int main(){ int n,t,o; while( ~sf("%d%d%d",&n,&t,&o) ){ getchar(); init(n); char op; int x,y,z; for(int i = 0; i < o; ++i){ sf("%c %d %d",&op,&x,&y); if(x > y) swap(x,y); if(op == 'C'){ sf("%d",&z); update(1,1,n,x,y,z); } else{ int ret = query(1,1,n,x,y),ans = 0; for(int i = 1; i <= t; ++i){ ans += (ret >> i & 1); } pf("%d\n",ans); }getchar(); } } }

    推荐阅读


    上一篇：SQL|Worktable大量逻辑读

    下一篇：曹向辉（她，爱我如初）