【有关注为回报/dk】【分块】样例都过不去的sb求调代码/dk
  • 板块P2357 守墓人
  • 楼主houpingze
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/12/27 22:09
  • 上次更新2023/11/5 05:34:59
查看原帖
【有关注为回报/dk】【分块】样例都过不去的sb求调代码/dk
253765
houpingze楼主2020/12/27 22:09
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define int long long 
using namespace std;
int read(){
	int res=0,fs=1; char c=getchar();
	while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
	while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
	return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int S;
int lazy[200005]; 
int n,cnt,m,a[200005],ans,tmp,l,r,k,z,x[200005],y[200005],id[200005],v[1010];
inline void sh(int l,int r,int k){ 
	
	int ll=id[l],rr=id[r]; 
    if(ll==rr){
    	for(int i=l;i<=r;i++) a[i]+=k,v[ll]+=k;
    	return ;
	} 
	for(int i=ll+1;i<=rr-1;++i) {
		v[i]+=k*S;
		lazy[i]+=k;		
	} 
	for(int i=l;i<=y[ll];++i) a[i]+=k,v[ll]+=k;
	for(int i=x[rr];i<=r;++i) a[i]+=k,v[rr]+=k;
}
inline int cx(int l,int r){
    //l~~r
    int ll=id[l],rr=id[r];
	int ret=0;
    if(ll==rr){
    	for(int i=l;i<=r;i++) ret+=a[i]+lazy[ll];
    	return ret;
	} 
	for(int i=ll+1;i<=rr-1;++i) ret+=v[i];
	
	for(int i=l;i<=x[ll];++i) ret+=a[i]+lazy[id[i]];
	for(int i=y[rr];i<=r;++i) ret+=a[i]+lazy[id[i]];
	return ret; 
}

signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;  
	for(int i=1;i<=n;i++) cin>>a[i];
	S=sqrt(n);
	for(int i=1;i<=n;i++){
		id[i]=(i-1)/S+1;
	} 
	for(int i=1;i<=S;i++){
		x[i]=(i-1)*S+1,y[i]=min(i*S,n);
	} 
	if(x[S]<n) S++,x[S]=y[S-1]+1,y[S]=n; 
	for(int i=1;i<=S;i++){ 
		for(int j=x[i];j<=y[i];j++) v[i]+=a[j];
	} 
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			cin>>l>>r>>k; 
			sh(l,r,k); 
		}else if(op==2){
			cin>>k; 
			a[1]+=k; 
		}else if(op==3){
			cin>>k; 
			a[1]-=k;
		}else if(op==4){
			cin>>l>>r; 
			cout<<cx(l,r)<<endl;
		}else if(op==5){ 

			cout<<a[1]<<endl; 
		} 
		
	}
    return 0;
}


或者哪位神仙给我讲讲lazy标记具体怎么用的也可以qwq谢谢

2020/12/27 22:09
加载中...