首页 > 其他 > 详细

luogu 1558 色板游戏

时间:2018-09-26 11:23:17      阅读:187      评论:0      收藏:0      [点我收藏+]

写这篇博客不是为了总结我的算法,而是为了纪念让我爆零的套路.....

色板游戏

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

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

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

这道题一看数据范围,emmm,可以状压。
然后,一眼切

/*
全wa代码
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 100001;
struct edge {
    int l,r,w,f,size;
} tree[N<<2];
void up(int k) {
    tree[k].w=tree[k<<1].w|tree[k<<1|1].w;
}
void build(int k,int ll,int rr) {
    tree[k].l=ll,tree[k].r=rr,tree[k].size=rr-ll+1;
    tree[k].f=0;
    if(ll==rr) {
        tree[k].w=1;
        return;
    }
    int m=(ll+rr)>>1;
    build(k<<1,ll,m);
    build(k<<1|1,m+1,rr);
    up(k);
}
void down(int k) {
    if(tree[k].f) {
        tree[k<<1].f=tree[k].f;
        tree[k<<1|1].f=tree[k].f;
        tree[k<<1].w=tree[k].f;
        tree[k<<1|1].w=tree[k].f;
        tree[k].f=0;
    }
}
void C_interval(int k,int ll,int rr,int val) {
    if(tree[k].l>=ll && tree[k].r<=rr) {
        tree[k].f=val;
        tree[k].w=val;
        return ;
    }
    down(k);
    int m=(tree[k].l+tree[k].r)>>1;
    if(ll<=m) C_interval(k<<1,ll,rr,val);
    if(rr>m) C_interval(k<<1|1,ll,rr,val);
    up(k);
}
int ask_interval(int k,int ll,int rr) {
    int ans=0;
    if(tree[k].l>=ll && tree[k].r<=rr) {
        ans|=tree[k].w;
        return ans;
    }
    down(k);
    int m=(tree[k].l+tree[k].r)>>1;
    if(ll<=m) ans|=ask_interval(k<<1,ll,rr);
    if(rr>m) ans|=ask_interval(k<<1|1,ll,rr);
    up(k);
    return ans;
}
int n,m,q;
int calc(int x) {
    int ans=0;
    while(x) {
        if(x&1)ans++;
        x>>=1;
    }
    return ans;
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    build(1,1,n);

    while(q--) {
        int a,b,c;
        char s;
        cin >> s;
        if(s=='C') {
            scanf("%d%d%d",&a,&b,&c);
            C_interval(1,a,b,(1<<(c-1))) ;
        }
        if(s=='P') {
            scanf("%d%d",&a,&b);
            printf("%d\n",calc(ask_interval(1,a,b)));
        }
    }
}

知道为啥吗??
因为
它a和b的大小压根不能确定!

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 100001;
struct edge {
    int l,r,w,f,size;
} tree[N<<2];
void up(int k) {
    tree[k].w=tree[k<<1].w|tree[k<<1|1].w;
}
void build(int k,int ll,int rr) {
    tree[k].l=ll,tree[k].r=rr,tree[k].size=rr-ll+1;
    tree[k].f=0;
    if(ll==rr) {
        tree[k].w=1;
        return;
    }
    int m=(ll+rr)>>1;
    build(k<<1,ll,m);
    build(k<<1|1,m+1,rr);
    up(k);
}
void down(int k) {
    if(tree[k].f) {
        tree[k<<1].f=tree[k].f;
        tree[k<<1|1].f=tree[k].f;
        tree[k<<1].w=tree[k].f;
        tree[k<<1|1].w=tree[k].f;
        tree[k].f=0;
    }
}
void C_interval(int k,int ll,int rr,int val) {
    if(tree[k].l>=ll && tree[k].r<=rr) {
        tree[k].f=val;
        tree[k].w=val;
        return ;
    }
    down(k);
    int m=(tree[k].l+tree[k].r)>>1;
    if(ll<=m) C_interval(k<<1,ll,rr,val);
    if(rr>m) C_interval(k<<1|1,ll,rr,val);
    up(k);
}
int ask_interval(int k,int ll,int rr) {
    int ans=0;
    if(tree[k].l>=ll && tree[k].r<=rr) {
        ans|=tree[k].w;
        return ans;
    }
    down(k);
    int m=(tree[k].l+tree[k].r)>>1;
    if(ll<=m) ans|=ask_interval(k<<1,ll,rr);
    if(rr>m) ans|=ask_interval(k<<1|1,ll,rr);
    up(k);
    return ans;
}
int n,m,q;
int calc(int x) {
    int ans=0;
    while(x) {
        if(x&1)ans++;
        x>>=1;
    }
    return ans;
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    build(1,1,n);
    while(q--) {
        int a,b,c;
        char s;
        cin >> s;
        if(s=='C') {
            scanf("%d%d%d",&a,&b,&c);
            C_interval(1,min(a,b),max(a,b),(1<<(c-1))) ;
        }
        if(s=='P') {
            scanf("%d%d",&a,&b);
            printf("%d\n",calc(ask_interval(1,min(a,b),max(a,b))));
        }
    }
    return 0;
}

luogu 1558 色板游戏

原文:https://www.cnblogs.com/ifmyt/p/9705763.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!