70分求调(用的树状数组)
查看原帖
70分求调(用的树状数组)
305735
Jean_Gunnhildr楼主2024/8/5 09:49

WA了三个点,关键是错误样例我本地测没问题

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100001
typedef long long ll;
int n,m;
ll d[MAXN];
__int128 di[MAXN];
ll lowbit(ll x){
	return x&(-x);
}
void update(int pos,ll num){//用树状数组维护 差 和 差*i 
	d[pos]+=num;
	ll v=pos*num;
	di[pos]+=v;
	while(pos+lowbit(pos)<=n){
		pos+=lowbit(pos);
		d[pos]+=num;
		di[pos]+=v;
	}
}
__int128 sum(int pos){
	__int128 ans=0;
	for(int i=pos;i>=1;i-=lowbit(i)){
		ans+=(pos+1)*d[i]-di[i];//带入公式,公式附在图里 
	}
	return ans;
}

inline void write(__int128 x){//快写 
	if(x/10) write(x/10);
	putchar((x%10)^48);
	return ;
}

int main(){
	scanf("%d%d",&n,&m);
	ll a=0,b=0;
	for(int i=1;i<=n;i++){//反正存差分,只要上一个和这一个就行 
		swap(a,b);//使a的值成为当前输入的上一个的值 
		scanf("%lld",&b);
		update(i,b-a);//更新差分 
	}
	while(m--){
		int type,l,r,k;
		scanf("%d",&type);
		if(type==1){
			scanf("%d%d%d",&l,&r,&k);
			update(l,k);//区间修改 
			update(r+1,-k);
		}
		else{
			scanf("%d%d",&l,&r);
			__int128 res= sum(r)-sum(l-1);//区间查询 
			if(res<0){//__int128 的输出 
				printf("-");
				res*=-1;
			}
			write(res);
			printf("\n");
		}
	} 
	return 0;
}

代码里关于sum函数的推导

思路来源:

https://blog.csdn.net/qq_37656398/article/details/128934622?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522172282221616800182169317%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=172282221616800182169317&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-128934622-null-null.142^v100^pc_search_result_base7&utm_term=%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E5%8C%BA%E9%97%B4%E4%BF%AE%E6%94%B9%E5%8C%BA%E9%97%B4%E6%9F%A5%E8%AF%A2&spm=1018.2226.3001.4187

2024/8/5 09:49
加载中...