大数据过不去,貌似是线段树的问题(蒟蒻求助)
查看原帖
大数据过不去,貌似是线段树的问题(蒟蒻求助)
845460
Harmonic_qwq楼主2023/9/17 15:45

这个线段树有问题吗

struct tree_node
{
	int lazy,l,r,data;
}tr[maxn<<2];
int n,m,ans[maxn];
inline int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch<'0'||ch>'9')f *= ch == '-'?-1:1,ch = getchar();
	while(ch>='0'&&ch<='9')x = x*10+ch-'0',ch = getchar();
	return x*f;
}
void build(int l,int r,int u)
{
	tr[u] = {0,l,r,0};
	if(l == r)return;
	build(l,(l+r)>>1,u<<1);
	build(((l+r)>>1)+1,r,u<<1|1);
}
void push_down(int u)
{
	if(tr[u].l == tr[u].r)return;
	tr[u<<1].lazy+=tr[u].lazy,tr[u<<1].data+=tr[u].lazy*(tr[u<<1].r-tr[u<<1].l+1);
	tr[u<<1|1].lazy+=tr[u].lazy,tr[u<<1|1].data+=tr[u].lazy*(tr[u<<1|1].r-tr[u<<1|1].l+1);
	tr[u].lazy = 0;
}
int query(int l,int r,int u)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].data;
	push_down(u);
	int mid  = (tr[u].l+tr[u].r)>>1,ret = 0;
	if(l<=mid)ret+=query(l,r,u<<1);
	if(r>mid)ret+=query(l,r,u<<1|1);
	return ret;
}
void modify(int l,int r,int k,int u)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].lazy+=k,tr[u].data+=k*(tr[u].r-tr[u].l+1);
		return;
	}
	push_down(u);
	int mid = (tr[u].r+tr[u].l)>>1;
	if(l<=mid)modify(l,r,k,u<<1);
	if(r>mid)modify(l,r,k,u<<1|1);
}
2023/9/17 15:45
加载中...