求助P1558
  • 板块学术版
  • 楼主Reunite
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/8/24 22:39
  • 上次更新2023/11/4 09:08:08
查看原帖
求助P1558
377760
Reunite楼主2021/8/24 22:39

为什么我的query函数第二行的pushdowm删掉就不对,而加上就过了呢。这里的pushdown有什么作用? 代码:

#include <bits/stdc++.h>
#define N 100005
using namespace std;

struct node{
    int sum,lazy;
}tree[N<<2];
int n,m,x,y,z,q;
char c[2];

void pushup(int u){
    tree[u].sum=tree[u<<1].sum|tree[u<<1|1].sum;
    return ;
}

void build(int l,int r,int u){
    if(l==r){
        tree[u].sum=1;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pushup(u);
}

void pushdown(int u){
    if(tree[u].lazy){
        tree[u<<1].lazy=tree[u].lazy;
        tree[u<<1|1].lazy=tree[u].lazy;
        tree[u<<1].sum=tree[u].lazy;
        tree[u<<1|1].sum=tree[u].lazy;
        tree[u].lazy=0;
    }
}

void updata(int L,int R,int x,int l,int r,int u){
    if(L<=l&&r<=R){
        tree[u].lazy=(1<<(x-1));
        tree[u].sum=(1<<(x-1));
        pushdown(u);
        return ;
    }
    pushdown(u);
    int mid=l+r>>1;
    if(L<=mid) updata(L,R,x,l,mid,u<<1);
    if(mid<R) updata(L,R,x,mid+1,r,u<<1|1);
    pushup(u);
}

int query(int L,int R,int l,int r,int u){
    if(L<=l&&r<=R) return tree[u].sum;
    pushdown(u);
    int sum=0;
    int mid=l+r>>1;
    if(L<=mid) sum=sum|query(L,R,l,mid,u<<1);
    if(mid<R) sum=sum|query(L,R,mid+1,r,u<<1|1);
    return sum;
}

int work(int num){
    int s=0;
    while(num){
        s+=(num%2);
        num/=2;
    }
    return s;
}

int main(){
    scanf("%d%d%d",&n,&q,&m);
    build(1,n,1);
    while(m--){
        scanf("%s",c);
        if(c[0]=='C'){
            scanf("%d%d%d",&x,&y,&z);
            if(x>y) swap(x,y);
            updata(x,y,z,1,n,1);
        }
        else{
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            printf("%d\n",work(query(x,y,1,n,1)));
        }
    }

    return 0;
}

2021/8/24 22:39
加载中...