线段树

参考资料

• 线段树 - OI Wiki

实现

struct SEG
{
	ll a[N],val[N<<2],tag[N<<2];
	void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
	void push_up(int u){val[u]=val[ls]+val[rs];}
	void push_down(int u,int l,int r)
	{
		gx(ls,tag[u],mid-l+1);
		gx(rs,tag[u],r-mid);
		tag[u]=0;
	}
	void build(int u,int l,int r)
	{
		if(l==r){val[u]=a[l];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(u);
	}
	void update(int u,int l,int r,int x,int y,ll v)
	{
		if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
		push_down(u,l,r);
		if(x<=mid)update(ls,l,mid,x,y,v);
		if(y>mid)update(rs,mid+1,r,x,y,v);
		push_up(u);
	}
	ll query(int u,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return val[u];
		push_down(u,l,r);
		ll res=0;
		if(x<=mid)res+=query(ls,l,mid,x,y);
		if(y>mid)res+=query(rs,mid+1,r,x,y);
		return res;
	}
};

例题

洛谷 P3372 【模板】线段树 1

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 $\{a_i\}$，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

代码（5）

三叉树

#include <bits/stdc++.h>
#define s1 (u*3)
#define s2 (u*3+1)
#define s3 (u*3+2)
#define m1 (l+(r-l)/3)
#define m2 (r-(r-l)/3)
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<4],tag[N<<4];
void gx(int u,ll v,int len)
{
	val[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	val[u]=val[s1]+val[s2]+val[s3];
}
void push_down(int u,int l,int r)
{
	if(!tag[u])return;
	if(l<=m1)gx(s1,tag[u],m1-l+1);
	if(m1<m2)gx(s2,tag[u],m2-m1);
	if(r>m2)gx(s3,tag[u],r-m2);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	if(l<=m1)build(s1,l,m1);
	if(m1<m2)build(s2,m1+1,m2);
	if(r>m2)build(s3,m2+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x>r||y<l)return;
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(l<=m1)update(s1,l,m1,x,y,v);
	if(m1<m2)update(s2,m1+1,m2,x,y,v);
	if(r>m2)update(s3,m2+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(l<=m1)res+=query(s1,l,m1,x,y);
	if(m1<m2)res+=query(s2,m1+1,m2,x,y);
	if(r>m2)res+=query(s3,m2+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

分块

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],b[N],s[N];
int id[N],len;
void update(int l,int r,ll v)
{
	int x=id[l],y=id[r];
	if(x==y)
	{
		for(int i=l;i<=r;i++){a[i]+=v;s[x]+=v;}
		return;
	}
	for(int i=l;id[i]==x;i++){a[i]+=v;s[x]+=v;}
	for(int i=r;id[i]==y;i--){a[i]+=v;s[y]+=v;}
	for(int i=x+1;i<y;i++){b[i]+=v;s[i]+=v*len;}
}
ll query(int l,int r)
{
	int x=id[l],y=id[r];
	ll res=0;
	if(x==y)
	{
		for(int i=l;i<=r;i++)res+=a[i]+b[x];
		return res;
	}
	for(int i=l;id[i]==x;i++)res+=a[i]+b[x];
	for(int i=r;id[i]==y;i--)res+=a[i]+b[y];
	for(int i=x+1;i<y;i++)res+=s[i];
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		id[i]=(i-1)/len+1;
		s[id[i]]+=a[i];
	}
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(x,y)<<'\n';
		}
	}
	return 0;
}

四叉树

#include <bits/stdc++.h>
#define s1 (u<<2)
#define s2 (u<<2|1)
#define s3 (u<<2|2)
#define s4 (u<<2|3)
#define m1 (l+(r-l>>2))
#define m2 (l+r>>1)
#define m3 (r-(r-l>>2))
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<5],tag[N<<5];
void gx(int u,ll v,int len)
{
	val[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	val[u]=val[s1]+val[s2]+val[s3]+val[s4];
}
void push_down(int u,int l,int r)
{
	if(!tag[u])return;
	if(l<=m1)gx(s1,tag[u],m1-l+1);
	if(m1<m2)gx(s2,tag[u],m2-m1);
	if(m2<m3)gx(s3,tag[u],m3-m2);
	if(r>m3)gx(s4,tag[u],r-m3);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	if(l<=m1)build(s1,l,m1);
	if(m1<m2)build(s2,m1+1,m2);
	if(m2<m3)build(s3,m2+1,m3);
	if(r>m3)build(s4,m3+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x>r||y<l)return;
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(l<=m1)update(s1,l,m1,x,y,v);
	if(m1<m2)update(s2,m1+1,m2,x,y,v);
	if(m2<m3)update(s3,m2+1,m3,x,y,v);
	if(r>m3)update(s4,m3+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(l<=m1)res+=query(s1,l,m1,x,y);
	if(m1<m2)res+=query(s2,m1+1,m2,x,y);
	if(m2<m3)res+=query(s3,m2+1,m3,x,y);
	if(r>m3)res+=query(s4,m3+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

树状数组

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
ll c1[N],c2[N];
void add(int u,ll v)
{
	ll w=u*v;
	while(u<N)
	{
		c1[u]+=v;
		c2[u]+=w;
		u+=u&-u;
	}
}
ll sum(ll *c,int u)
{
	ll res=0;
	while(u)
	{
		res+=c[u];
		u-=u&-u;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		add(i,x);
		add(i+1,-x);
	}
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<sum(c1,y)*(y+1)-sum(c1,x-1)*x-(sum(c2,y)-sum(c2,x-1))<<'\n';
		}
	}
	return 0;
}

线段树

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<2],tag[N<<2];
void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
void push_up(int u){val[u]=val[ls]+val[rs];}
void push_down(int u,int l,int r)
{
	gx(ls,tag[u],mid-l+1);
	gx(rs,tag[u],r-mid);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(x<=mid)update(ls,l,mid,x,y,v);
	if(y>mid)update(rs,mid+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(x<=mid)res+=query(ls,l,mid,x,y);
	if(y>mid)res+=query(rs,mid+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

洛谷 P13825 【模板】线段树 1.5

洛谷 P13825 【模板】线段树 1.5

如题，已知一个长度为 $n$ 的数列 $\{a_i\}$（$1 \leq i \leq n$），初始时 $a$ 序列满足 $a_i = i$。你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

代码（1）

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

using ull=unsigned long long;
const int N=100005;
ull val[N*120],tag[N*120];
int son[N*120][2];
int cnt=0;
void gx(int u,ull v,int len)
{
	val[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	val[u]=(son[u][0]?val[son[u][0]]:0)+(son[u][1]?val[son[u][1]]:0);
}
void push_down(int u,int l,int r)
{
	if(l==r||!tag[u])return;
	if(!son[u][0])son[u][0]=++cnt;
	if(!son[u][1])son[u][1]=++cnt;
	gx(son[u][0],tag[u],mid-l+1);
	gx(son[u][1],tag[u],r-mid);
	tag[u]=0;
}
void update(int &u,int l,int r,int x,int y,ull v)
{
	if(!u)u=++cnt;
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(x<=mid)update(son[u][0],l,mid,x,y,v);
	if(y>mid)update(son[u][1],mid+1,r,x,y,v);
	push_up(u);
}
ull query(int u,int l,int r,int x,int y)
{
	if(!u)return 0;
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ull res=0;
	if(x<=mid)res+=query(son[u][0],l,mid,x,y);
	if(y>mid)res+=query(son[u][1],mid+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,rt=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int op,x,y,k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(rt,1,1e9,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(rt,1,1e9,x,y)+1ll*(x+y)*(y-x+1)/2<<'\n';
		}
	}
	return 0;
}

洛谷 P3373 【模板】线段树 2

洛谷 P3373 【模板】线段树 2

如题，已知一个数列 $a$，你需要进行下面三种操作：

• 将某区间每一个数乘上 $x$；
• 将某区间每一个数加上 $x$；
• 求出某区间每一个数的和。

代码（1）

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<2],mul[N<<2],add[N<<2];
int mod;
void gx(int u,ll v1,ll v2,int len)
{
	val[u]=(val[u]*v1+len*v2)%mod;
	mul[u]=(mul[u]*v1)%mod;
	add[u]=(add[u]*v1+v2)%mod;
}
void push_up(int u)
{
	val[u]=(val[ls]+val[rs])%mod;
}
void push_down(int u,int l,int r)
{
	gx(ls,mul[u],add[u],mid-l+1);
	gx(rs,mul[u],add[u],r-mid);
	mul[u]=1;
	add[u]=0;
}
void build(int u,int l,int r)
{
	mul[u]=1;
	if(l==r){val[u]=a[l]%mod;return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v1,ll v2)
{
	if(x<=l&&r<=y){gx(u,v1,v2,r-l+1);return;}
	push_down(u,l,r);
	if(x<=mid)update(ls,l,mid,x,y,v1,v2);
	if(y>mid)update(rs,mid+1,r,x,y,v1,v2);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return val[u]%mod;
	push_down(u,l,r);
	ll res=0;
	if(x<=mid)res=(res+query(ls,l,mid,x,y))%mod;
	if(y>mid)res=(res+query(rs,mid+1,r,x,y))%mod;
	return res%mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,q;
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(q--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k,0);
		}
		else if(op==2)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,1,k);
		}
		else if(op==3)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

洛谷 P4588 [TJOI2018] 数学计算

洛谷 P4588 [TJOI2018] 数学计算

小豆现在有一个数 $x$，初始值为 $1$。小豆有 $Q$ 次操作，操作有两种类型：

1 m：将 $x$ 变为 $x \times m$，并输出 $x \bmod M$

2 pos：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $pos$ 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 $x \bmod M$。

代码（1）

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=400005;
ll val[N];
int mod;
void push_up(int u)
{
	val[u]=val[ls]*val[rs]%mod;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=1;return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,ll v)
{
	if(l==r){val[u]=v;return;}
	if(x<=mid)update(ls,l,mid,x,v);
	else update(rs,mid+1,r,x,v);
	push_up(u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int q;
		cin>>q>>mod;
		build(1,1,q);
		for(int i=1;i<=q;i++)
		{
			int op,x;
			cin>>op>>x;
			if(op==1)update(1,1,q,i,x);
			else if(op==2)update(1,1,q,x,1);
			cout<<val[1]<<'\n';
		}
	}
	return 0;
}

洛谷 P1471 方差

洛谷 P1471 方差

第一行包含两个正整数 $N,M$，分别表示数列中实数的个数和操作的个数。

第二行包含 $N$ 个实数，其中第 $i$ 个实数表示数列的第 $i$ 项。

接下来 $M$ 行，每行为一条操作，格式为以下三种之一：

操作 $1$：1 x y k，表示将第 $x$ 到第 $y$ 项每项加上 $k$，$k$ 为一实数。 操作 $2$：2 x y，表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。 操作 $3$：3 x y，表示求出第 $x$ 到第 $y$ 项这一子数列的方差。

代码（1）

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=1000005;
double a[N],v1[N<<2],v2[N<<2],tag[N<<2];
void gx(int u,double v,int len)
{
	v2[u]+=v1[u]*v*2+v*v*len;
	v1[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	v1[u]=v1[ls]+v1[rs];
	v2[u]=v2[ls]+v2[rs];
}
void push_down(int u,int l,int r)
{
	gx(ls,tag[u],mid-l+1);
	gx(rs,tag[u],r-mid);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){v1[u]=a[l];v2[u]=a[l]*a[l];return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,double v)
{
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(x<=mid)update(ls,l,mid,x,y,v);
	if(y>mid)update(rs,mid+1,r,x,y,v);
	push_up(u);
}
double query1(int u,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return v1[u];
	push_down(u,l,r);
	double ans=0;
	if(x<=mid)ans+=query1(ls,l,mid,x,y);
	if(y>mid)ans+=query1(rs,mid+1,r,x,y);
	return ans;
}
double query2(int u,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return v2[u];
	push_down(u,l,r);
	double ans=0;
	if(x<=mid)ans+=query2(ls,l,mid,x,y);
	if(y>mid)ans+=query2(rs,mid+1,r,x,y);
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		double k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else
		{
			cin>>x>>y;
			double ave=query1(1,1,n,x,y)/(y-x+1);
			double ans=op==2?ave:query2(1,1,n,x,y)/(y-x+1)-ave*ave;
			cout<<fixed<<setprecision(4)<<ans<<'\n';
		}
	}
	return 0;
}

洛谷 P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

洛谷 P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

村落里一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$ 次发放，每次选择两个房屋 $(x, y)$，然后对于 $x$ 到 $y$ 的路径上（含 $x$ 和 $y$）每座房子里发放一袋 $z$ 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

代码（1）

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=100005;
int root[N],son[N*80][2],val[N*80];
ll tag[N*80];
int cnt=0;
void push_up(int u)
{
	bool t=val[son[u][0]]<val[son[u][1]];
	val[u]=val[son[u][t]];
	tag[u]=tag[son[u][t]];
}
void update(int &u,int l,int r,int x,int v)
{
	if(!u)u=++cnt;
	if(l==r){val[u]+=v;tag[u]=l;return;}
	if(x<=mid)update(son[u][0],l,mid,x,v);
	else update(son[u][1],mid+1,r,x,v);
	push_up(u);
}
int merge(int u1,int u2,int l,int r)
{
	if(!u1||!u2)return u1|u2;
	if(l==r){val[u1]+=val[u2];return u1;}
	son[u1][0]=merge(son[u1][0],son[u2][0],l,mid);
	son[u1][1]=merge(son[u1][1],son[u2][1],mid+1,r);
	push_up(u1);
	return u1;
}
vector<int> G[N];
ll ans[N];
void dfs(int u,int fa)
{
	for(auto v:G[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		root[u]=merge(root[u],root[v],1,100000);
	}
	ans[u]=val[root[u]]>0?tag[root[u]]:0;
}
int siz[N],fa[N],top[N],dep[N],sonn[N];
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[sonn[u]])sonn[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	if(sonn[u])dfs2(sonn[u],t);
	for(auto v:G[u])
	{
		if(v==fa[u]||v==sonn[u])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		int l=lca(x,y);
		update(root[x],1,100000,z,1);
		update(root[y],1,100000,z,1);
		update(root[l],1,100000,z,-1);
		if(l!=1)update(root[fa[l]],1,100000,z,-1);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<'\n';
	}
	return 0;
}

洛谷 CF786B Legacy

洛谷 CF786B Legacy

Rick 和他的同事们做出了一种新的放射性配方，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。

在宇宙中一共有 $n$ 个星球标号为 $1\sim n$。Rick 现在身处于标号为 $s$ 的星球（地球）但是他不知道 Morty 在哪里。

众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球（也包括自己所在的星球）的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。

默认情况下他不能用这把枪开启任何传送门。在网络上有 $q$ 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它，但是每次购买后只能使用一次。每个方案的购买次数都是无限的。

网络上一共有三种方案可供购买：

• 开启一扇从星球 $v$ 到星球 $u$ 的传送门；
• 开启一扇从星球 $v$ 到标号在 $[l,r]$ 区间范围内任何一个星球的传送门。（即这扇传送门可以从一个星球出发通往多个星球）；
• 开启一扇从标号在 $[l,r]$ 区间范围内任何一个星球到星球 $v$ 的传送门。（即这扇传送门可以从多个星球出发到达同一个星球）；

Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具体位置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球（包括地球本身）他想要知道从地球到那个星球所需的最小钱数。

代码（1）

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=100005;
const int K=N<<2;
int a[N];
vector<pair<int,int>> G[N<<3];
void build(int u,int l,int r)
{
	if(l==r){a[l]=u;return;}
	G[u].push_back({ls,0});
	G[u].push_back({rs,0});
	G[ls+K].push_back({u+K,0});
	G[rs+K].push_back({u+K,0});
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void modify(int u,int l,int r,int x,int y,int v,int w,int type)
{
	if(x<=l&&r<=y)
	{
		if(type==2)G[v+K].push_back({u,w});
		else G[u+K].push_back({v,w});
		return;
	}
	if(x<=mid)modify(ls,l,mid,x,y,v,w,type);
	if(y>mid)modify(rs,mid+1,r,x,y,v,w,type);
}
ll dis[N<<3];
bool vis[N<<3];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	priority_queue<pair<ll,int>> q;
	q.push({dis[s]=0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,s;
	cin>>n>>m>>s;
	build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		G[a[i]].push_back({a[i]+K,0});
		G[a[i]+K].push_back({a[i],0});
	}
	while(m--)
	{
		int op,v,u,l,r,w;
		cin>>op;
		if(op==1)
		{
			cin>>v>>u>>w;
			G[a[v]+K].push_back({a[u],w});
		}
		else
		{
			cin>>v>>l>>r>>w;
			modify(1,1,n,l,r,a[v],w,op);
		}
	}
	dijkstra(a[s]+K);
	for(int i=1;i<=n;i++)
	{
		cout<<(dis[a[i]]!=inf?dis[a[i]]:-1)<<' ';
	}
	return 0;
}