萌新初学分块,0分求助
查看原帖
萌新初学分块,0分求助
371927
REAL_曼巴楼主2022/3/19 22:48
#include<iostream>
#include<cmath>
using namespace std ;
int n,len,a[200001],s[200001] ;
int pos[200001],tag[200001];
void do_sum_part(int x,int y,int k) {
	for(int i=x;i<=min(pos[x]*len,y);i++)a[i]+=k,s[pos[x]]+=k ; 
	if(pos[x]!=pos[y])for(int i=(pos[y]-1)*len+1;i<=y;i++) a[i]+=k,s[pos[y]]+=k; 
	for(int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
long long get_sum_part(int x,int y){
	long long ans=0;
	for(int i=x;i<=min(pos[x]*len,y);i++)ans+=a[i]+tag[pos[x]];
	if(pos[x]!=pos[y])for(int i=(pos[y]-1)*len+1;i<=y;i++) ans+=a[i]+tag[pos[y]];
	for(int i=pos[x]+1;i<=pos[y]-1;i++)ans+=s[i]+tag[i]*len;
	return ans ;
}
void get_blocks(){
    len=sqrt(n);
	for(int i=1;i<=n;i++)pos[i]=(i-1)/len+1 ;
}
int main(){
    int q;
	cin>>n>>q;
    get_blocks();
	while(q--){
		char c;
        int l,r;
		cin>>c;
		if(c=='x'){
			cin>>l>>r;
			do_sum_part(l,l,r);
		}
        else{
			cin>>l>>r;
			cout<<get_sum_part(l,r)<<endl;
		} 
	}
	return 0 ;
}

样例过了,求调

2022/3/19 22:48
加载中...