全RE
  • 板块P2068 统计和
  • 楼主WsW_花逝爆零人
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/12/20 15:51
  • 上次更新2023/11/5 05:52:50
查看原帖
全RE
349824
WsW_花逝爆零人楼主2020/12/20 15:51
#include<bits/stdc++.h>
using namespace std;
struct node{
	int r,l,id;
	long long sum;
};
node tree[400000];
int m,n,tl,a,b,k[100003];
char x;
int rson(int f){
	return f*2+1;
}
int lson(int f){
	return f*2;
}
void pushup(int id){
	tree[id].sum=tree[rson(id)].sum+tree[lson(id)].sum;
}
void build(int id,int l,int r){
	tree[id].id=id;
	tree[id].r=r;
	tree[id].l=l;
	if(l==r){
		tree[id].sum=k[l];
		return ;
	}
	int m=(l+r)/2;
	build(lson(id),l,m);
	build(rson(id),m+1,r);
	pushup(id);
}
void update(int w,int x,int id){
	if(tree[id].l==tree[id].r){
		tree[id].sum+=x;
		return ;
	}
	if(tree[lson(id)].r>=a)update(lson(id),w,x);
	else update(rson(id),w,x);
	pushup(id);
}
int query(int l,int r,int id){
	if(l<=tree[id].l&&tree[id].r<=r)return tree[id].sum;
	long long ans;
	if((l<=tree[m].l&&tree[m].l<=r)||(r<=tree[m].r&&tree[m].l<=l))ans=query(lson(id),l,r);
	int m=rson(id);
	if((l<=tree[m].l&&tree[m].l<=r)||(r<=tree[m].r&&tree[m].l<=l))ans+=query(rson(id),l,r);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--){
		cin>>x;
		scanf("%d%d",&a,&b);
		if(x=='y')printf("%d\n",query(a,b,1));
		else update(a,b,1);
	}
	return 0;
}
2020/12/20 15:51
加载中...