树状数组——守墓人
  • 板块P2357 守墓人
  • 楼主LuffyLuo
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/26 17:34
  • 上次更新2023/10/28 05:31:37
查看原帖
树状数组——守墓人
443739
LuffyLuo楼主2022/3/26 17:34

最后一个点一直WA,QWQ。一直没找出错误:

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N],n,f;
int lowbit(int x){
	return x&-x;
}
long long treesum1[N],treesum2[N];
void add(int k,long long w){
	int x=k;
	while(k<=n){
		treesum1[k]+=w;
		treesum2[k]+=(x-1)*w;
		k+=lowbit(k);
	}
}
long long query(int k){
	long long answer=0;
	int x=k;
	while(k){
		answer+=x*treesum1[k]-treesum2[k];
		k-=lowbit(k);
	}
	return answer;
}
int main(){
	scanf("%d %d",&n,&f);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=f;i++){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int l,r;long long w;
			scanf("%d %d %lld",&l,&r,&w);
			add(l,w);
			add(r+1,-w);
		}
		else if(opt==2){
			long long w;
			scanf("%lld",&w);
			add(1,w);
			add(2,-w);
		}
		else if(opt==3){
			long long w;
			scanf("%lld",&w);
			add(1,-w);
			add(2,w);
		}
		else if(opt==4){
			int l,r;
			scanf("%d %d",&l,&r);
			printf("%lld\n",query(r)-query(l-1));
		}
		else if(opt==5) printf("%lld\n",query(1)-query(0));
	} 
	return 0;
} 
2022/3/26 17:34
加载中...