线段树全WA求调~
查看原帖
线段树全WA求调~
513326
阿哲朗读楼主2022/10/27 22:01
#include<bits/stdc++.h>
using namespace std;
long long n,w,t[400040];
void build(long long left,long long right,long long node)
{
	if(left==right) return;
	long long mid=(left+right)/2;
	t[node]=0;
	build(left,mid,node*2);
	build(mid+1,right,node*2+1);
}
void update(long long left,long long right,long long node,long long no,long long add)
{
	if(left==right)
	{
		t[node]+=add;
		return;
	}
	long long mid=(left+right)/2;
	if(no<=mid) update(left,mid,node*2,no,add);
	else update(mid+1,right,node*2+1,no,add);
	t[node]=t[node*2]+t[node*2+1];
}
long long query(long long left,long long right,long long node,long long a,long long b)
{
	if(left>b||right<a) return 0;
	if(left>=a&&left<=b) return t[node];
	long long mid=(left+right)/2;
	return query(left,mid,node*2,a,b)+query(mid+1,right,node*2+1,a,b);
}	
int main()
{
	cin>>n>>w;
	build(1,n,1);
	for(long long i=1;i<=w;i++)
	{
		char c;
		cin>>c;
		if(c=='x')
		{
			long long a,b;
			cin>>a>>b;
			update(1,n,1,a,b);
		}
		if(c=='y')
		{
			long long a,b;
			cin>>a>>b;
			cout<<query(1,n,1,a,b)<<endl;
		}
	}
	return 0;
}
2022/10/27 22:01
加载中...