萌新求助卡常

Spasmodic @ 2020-10-30 22:54:54

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=100005;
int n,k,m;
bitset<31>sum[N<<2],tag1[N<<2],tag2[N<<2];
void pushup(int k){sum[k]=sum[k<<1]|sum[k<<1|1];}
void lazy(int k,int l,int r,int v,int id){
    tag1[k][id]=v,tag2[k][id]=1;
    sum[k][id]=v;
}
void pushdown(int k,int l,int r,int mid,int id){
    if(!tag2[k][id])return;
    lazy(k<<1,l,mid,tag1[k][id],id);
    lazy(k<<1|1,mid+1,r,tag1[k][id],id);
    tag2[k][id]=0;
}
void pushdown(int k,int l,int r,int mid){
    for(int i=1;i<=30;i++)pushdown(k,l,r,mid,i);
}
void modify(int k,int l,int r,int x,int y,int id){
    if(x<=l&&r<=y){
        for(int i=1;i<=30;i++)lazy(k,l,r,i==id,i);
        return;
    }
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid)modify(k<<1,l,mid,x,y,id);
    if(mid<y)modify(k<<1|1,mid+1,r,x,y,id);
    pushup(k);
}
bitset<31> query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y)return sum[k];
    int mid=l+r>>1;
    bitset<31>ret(0);
    pushdown(k,l,r,mid);
    if(x<=mid)ret|=query(k<<1,l,mid,x,y);
    if(mid<y)ret|=query(k<<1|1,mid+1,r,x,y);
    return ret;
}
char op[2];
int main(){
    scanf("%d%d%d",&n,&k,&m);
    lazy(1,1,n,1,1);
    for(int a,b,c;m--;){
        scanf("%s%d%d",op,&a,&b);
        if(a>b)swap(a,b);
        if(op[0]=='C'){
            scanf("%d",&c);
            modify(1,1,n,a,b,c);
        }else{
            printf("%d\n",query(1,1,n,a,b).count());
        }
    }
    return 0;
}

by RainsAFO @ 2020-10-30 22:58:37

这是51nod？

by RainsAFO @ 2020-10-30 22:59:33

你把三十种颜色压成一个二进制数就能过了

by RainsAFO @ 2020-10-30 23:00:04

哦对了这题odt能过

by RainsAFO @ 2020-10-30 23:00:21

@happydef

by ez_lcw @ 2020-10-30 23:06:38

@happydef 魔改了一发，您康康对不对

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=100005;
int n,k,m;
int sum[N<<2],tag1[N<<2];
bool tag2[N<<2];
void pushup(int k){sum[k]=sum[k<<1]|sum[k<<1|1];}
void lazy(int k,int l,int r,int v){
    tag1[k]=v,tag2[k]=1;
    sum[k]=v;
}
void pushdown(int k,int l,int r,int mid){
    if(!tag2[k])return;
    lazy(k<<1,l,mid,tag1[k]);
    lazy(k<<1|1,mid+1,r,tag1[k]);
    tag2[k]=0;
}
void modify(int k,int l,int r,int x,int y,int id){
    if(x<=l&&r<=y){
        lazy(k,l,r,1<<id);
        return;
    }
    int mid=l+r>>1;
    pushdown(k,l,r,mid);
    if(x<=mid)modify(k<<1,l,mid,x,y,id);
    if(mid<y)modify(k<<1|1,mid+1,r,x,y,id);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y)return sum[k];
    int mid=l+r>>1,ret=0;
    pushdown(k,l,r,mid);
    if(x<=mid)ret|=query(k<<1,l,mid,x,y);
    if(mid<y)ret|=query(k<<1|1,mid+1,r,x,y);
    return ret;
}
char op[2];
int main(){
    scanf("%d%d%d",&n,&k,&m);
    lazy(1,1,n,1,1);
    for(int a,b,c;m--;){
        scanf("%s%d%d",op,&a,&b);
        if(a>b)swap(a,b);
        if(op[0]=='C'){
            scanf("%d",&c);
            modify(1,1,n,a,b,c);
        }else{
            int tmp=query(1,1,n,a,b),ret=0;
            while(tmp){
                ret+=tmp&1;
                tmp>>=1;
            }
            printf("%d\n",ret);
        }
    }
    return 0;
}

by ez_lcw @ 2020-10-30 23:08:03

已经极力模仿您的码风了（

by Spasmodic @ 2020-10-30 23:14:14

@ez_lcw orz thx

终于 A 了

by ez_lcw @ 2020-10-30 23:24:21

@happydef sto hpdf

所以是哪道题啊

by Spasmodic @ 2020-10-30 23:31:14

@ez_lcw 校内（？模拟赛

反正就 P4690 弱化版，值域缩小到 30。

by ez_lcw @ 2020-10-30 23:33:34

@happydef thx

我去康康（