动态开点线段树MLE?
  • 板块P4939 Agent2
  • 楼主f_hxr_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/16 18:57
  • 上次更新2023/11/2 13:25:31
查看原帖
动态开点线段树MLE?
754467
f_hxr_楼主2023/10/16 18:57

rt,95pts。刚刚把longlong换成int才90的

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
LL NOI,M;
struct SegmentTree{
	struct Node{Node* ls,* rs;LL dat=0,addv=0;}root;
	#define ls(p) p.ls
	#define rs(p) p.rs
	void pushup(Node& p){p.dat=p.ls->dat+p.rs->dat;}
	void pushdown(Node& p,LL Len,LL Ren){
		if(!ls(p))ls(p)=new Node();
		if(!rs(p))rs(p)=new Node();
		if(p.addv){
			p.ls->dat+=Len*p.addv;p.rs->dat+=Ren*p.addv;
			p.ls->addv+=p.addv;p.rs->addv+=p.addv;
			p.addv=0;
		}
	}
	void ModifyRange(Node& p,LL L,LL R,LL ql,LL qr,LL xx){
		if(ql<=L&&R<=qr){p.dat+=(R-L+1)*xx;p.addv+=xx;return;}
		LL mid=(L+R)>>1;
		pushdown(p,mid-L+1,R-(mid+1)+1);
		if(ql<=mid)ModifyRange(*(p.ls),L,mid,ql,qr,xx);
		if(mid+1<=qr)ModifyRange(*(p.rs),mid+1,R,ql,qr,xx);
		pushup(p);
	}
	void ModifyRange(LL ql,LL qr,LL xx){ModifyRange(root,1,NOI,ql,qr,xx);}
	LL QueryPoint(Node& p,LL L,LL R,LL inx){
		if(L>=R)return p.dat;
		LL mid=(L+R)>>1;
		pushdown(p,mid-L+1,R-(mid+1)+1);
		if(inx<=mid)return QueryPoint(*(p.ls),L,mid,inx);
		else return QueryPoint(*(p.rs),mid+1,R,inx);
	}
	LL QueryPoint(LL inx){return QueryPoint(root,1,NOI,inx);}
}Seg;
int main(){
	scanf("%d%d",&NOI,&M);
	while(M--){
		LL op;scanf("%d",&op);
		if(op==0){
			LL LHQ,RMJ;scanf("%d%d",&LHQ,&RMJ);
			Seg.ModifyRange(LHQ,RMJ,1);
		}
		else if(op==1){
			LL Inx;scanf("%d",&Inx);
			printf("%d\n",Seg.QueryPoint(Inx));
		}
	}
	return 0;
}
2023/10/16 18:57
加载中...