初学线段树求调!
  • 板块P2068 统计和
  • 楼主Lvyuze
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/12 10:57
  • 上次更新2023/10/27 15:49:24
查看原帖
初学线段树求调!
541408
Lvyuze楼主2022/8/12 10:57
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
long long n,w,a,b,ans;
string op;
struct Tree{
	int l,r,w;
	int f;
}tree[maxn*4];
inline void build(int k,int ll,int rr){
	tree[k].l=ll,tree[k].r=rr;
	if(tree[k].l==tree[k].r){
		tree[k].w=0;
		return;
	}
	int mid=(ll+rr)/2;
	build(k*2,ll,mid);
	build(k*2+1,mid+1,rr);
}
inline void add(int k){
	if(tree[k].l==a && tree[k].r==a){
		tree[k].w+=b;
		tree[k].f+=b;
		return;
	}
	int mid=(tree[k].l+tree[k].r)/2;
	if(a<=mid) add(k*2);
	else if(a>mid)add(k*2+1);
	tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void sum(int k){
	if(tree[k].l>=a && tree[k].r<=b){
		ans+=tree[k].w;
		return;
	}
	int mid=(tree[k].l+tree[k].r)/2;
	if(a<=mid) sum(k*2);
	if(b>mid) sum(k*2+1);
}
signed main()
{
scanf("%lld%lld",&n,&w);
build(1,1,n);
while(w--){
    cin>>op;
    scanf("%lld%lld",&a,&b);
    if(op=="x"){
    	add(1);
	}
	else if(op=="y"){
		ans=0;
		sum(1);
		printf("%lld\n",ans);
	}
}
return 0;
}
2022/8/12 10:57
加载中...