线段树TLE20pts求调
  • 板块P2068 统计和
  • 楼主Form_mula
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/7 15:44
  • 上次更新2024/9/7 19:10:30
查看原帖
线段树TLE20pts求调
467411
Form_mula楼主2024/9/7 15:44
#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=100010;
int n,w;
long long t[MAXN<<2];

void pushup(int k){
	t[k]=t[k<<1]+t[k<<1|1];
}

void change(int k,int l,int r,int add,int p){
	if(l==r) t[k]+=add;
	else {
		int m=l+((r-l)>>1);
		if(p<=m) change(k<<1,l,m,add,p);
		else change(k<<1|1,m+1,r,add,p);
		pushup(k);
	}
	return ;
}

long long find_out(int L,int R,int l,int r,int k){
	if(l>=L&&r<=R) return t[k];
	if(l==r) return 0;
	//cout<<l<<" "<<r<<endl;
	int m=l+((r-l)>>1);
	long long ans=0;
	if(L<=m) ans=ans+find_out(L,R,l,m,k<<1);
	if(r>m) ans=ans+find_out(L,R,m+1,r,k<<1|1);
	return ans;
}

int main(){
	cin>>n>>w;
	for(int i=1;i<=w;i++){
		char c;
		int x,y;
		cin>>c>>x>>y;
		if(c=='x'){
			change(1,1,n,y,x);
		} else {
			cout<<find_out(x,y,1,n,1)<<endl;
		}
	}
	return 0;
}

线段树TLE20pts求调

2024/9/7 15:44
加载中...