神奇的c++
查看原帖
神奇的c++
1061049
lin_er楼主2024/7/18 20:36

请看这两份代码

#include"bits/stdc++.h"
#define int long long 
using namespace std;
const int N=3e5;
int n,m,a[N];
struct ss{
	int tp,add,b[51];
}tr[N<<2];
ss addx(ss x,int v){
	if(x.tp==0){
		x.add+=v;
		return x;
	}
	for(int i=0;i<=50;i++){
		x.b[i]+=v;
	}
	return x;
}
ss addp(ss x){
	if(x.tp==0){
	    x.tp=1;
		for(int i=0;i<=50;i++){
			x.b[i]=i;
		}
		return x;
	}
	for(int i=0;i<=50;i++) x.b[i]=__builtin_popcountll(x.b[i]);
	return x;
}
ss merge(ss x,ss y){
	if(y.tp==0){
		return addx(x,y.add);
	}
	if(x.tp==0){
		y.add+=x.add;
		return y;
	}
	for(int i=0;i<=50;i++) x.b[i]=y.b[__builtin_popcountll(x.b[i]+y.add)];
	return x;
}
void push_down(int p){
	tr[p<<1]=merge(tr[p<<1],tr[p]);
	tr[p<<1|1]=merge(tr[p<<1|1],tr[p]);
	tr[p].add=tr[p].tp=0;
}
void change1(int p,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R){
		tr[p]=addx(tr[p],v);
		return;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(L<=mid) change1(p<<1,l,mid,L,R,v);
	if(R>mid) change1(p<<1|1,mid+1,r,L,R,v);
}
void change2(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){
		tr[p]=addp(tr[p]);
		return;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(L<=mid) change2(p<<1,l,mid,L,R);
	if(R>mid) change2(p<<1|1,mid+1,r,L,R);
}
ss ask(int p,int l,int r,int pos){
	if(l==r) return tr[p];
	push_down(p);
	int mid=(l+r)>>1;
	if(pos<=mid) return ask(p<<1,l,mid,pos);
	if(pos>mid) return ask(p<<1|1,mid+1,r,pos);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int q; cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(q--){
		char c;
		int l,r,x;
		cin>>c;
		if(c=='J'){
		   cin>>x;
	           ss tmp=ask(1,1,n,x);
		   if(tmp.tp==0) cout<<a[x]+tmp.add<<"\n";
			else cout<<tmp.b[__builtin_popcountll(a[x]+tmp.add)]<<"\n";
		}
		else if(c=='A'){
			 cin>>l>>r>>x;
			change1(1,1,n,l,r,x);
		}
		else{
		 cin>>l>>r;
			change2(1,1,n,l,r);
		}
	}
	return 0;
}
#include"bits/stdc++.h"
#define int long long 
using namespace std;
const int N=3e5;
int n,m,a[N];
struct ss{
	int tp,add,b[51];
}tr[N<<2];
ss addx(ss x,int v){
	if(x.tp==0){
		x.add+=v;
		return x;
	}
	for(int i=0;i<=50;i++){
		x.b[i]+=v;
	}
	return x;
}
ss addp(ss x){
	if(x.tp==0){
	    x.tp=1;
		for(int i=0;i<=50;i++){
			x.b[i]=i;
		}
		return x;
	}
	for(int i=0;i<=50;i++) x.b[i]=__builtin_popcountll(x.b[i]);
	return x;
}
ss merge(ss x,ss y){
	if(y.tp==0){
		return addx(x,y.add);
	}
	if(x.tp==0){
		y.add+=x.add;
		return y;
	}
	for(int i=0;i<=50;i++) x.b[i]=y.b[__builtin_popcountll(x.b[i]+y.add)];
	return x;
}
void push_down(int p){
	tr[p<<1]=merge(tr[p<<1],tr[p]);
	tr[p<<1|1]=merge(tr[p<<1|1],tr[p]);
	tr[p].add=tr[p].tp=0;
}
void change1(int p,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R){
		tr[p]=addx(tr[p],v);
		return;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(L<=mid) change1(p<<1,l,mid,L,R,v);
	if(R>mid) change1(p<<1|1,mid+1,r,L,R,v);
}
void change2(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){
		tr[p]=addp(tr[p]);
		return;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(L<=mid) change2(p<<1,l,mid,L,R);
	if(R>mid) change2(p<<1|1,mid+1,r,L,R);
}
ss ask(int p,int l,int r,int pos){
	if(l==r) return tr[p];
	push_down(p);
	int mid=(l+r)>>1;
	if(pos<=mid) return ask(p<<1,l,mid,pos);
	if(pos>mid) return ask(p<<1|1,mid+1,r,pos);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		char opt;
		int l,r,x;cin>>opt;
		if(opt=='A'){
			cin>>l>>r>>x;
			change1(1,1,n,l,r,x);
		}
		else if(opt=='J'){
			cin>>x;
			ss t=ask(1,1,n,x);
			if(t.tp==0) cout<<a[x]+t.add<<'\n';
			else cout<<t.b[__builtin_popcountll(a[x]+t.add)]<<'\n';
		}
		else{
			cin>>l>>r;
			change2(1,1,n,l,r);
		}
	}
}

只是n和m的定义位置不同,第一份代码就能过,后者就不行,这是为什么?

2024/7/18 20:36
加载中...