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

色板游戏

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

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

\("C A B C"\) 指在\(A\)到 \(B\) 号方格中涂上颜色 \(C\)。
\("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 色板游戏

色板游戏

最新文章

热门文章