为什么我的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;
}