《高手训练》解题报告 4.1 树状数组

树状数组练习题。

对应 OJ 的传送门

《高手训练》解题报告集合:信息学奥赛一本通·高手训练

树状数组

树状数组是一个查询和修改复杂度都为 \( \Theta ( \log _ 2 n ) \) 的数据结构。 主要用于数组的单点修改和区间求和。

树状数组和下面的线段树可是亲兄弟了,但他俩毕竟还有一些区别:

  • 树状数组能有的操作,线段树一定有;
  • 线段树有的操作,树状数组不一定有。

这么看来选择线段树不就 「得天下了」 ,怎么会有人用树状数组呢?

事实上,树状数组的代码要比线段树短得多,思维也更清晰,在解决一些单点修改的问题时,树状数组是不二之选。

电子速度 Kurisu

题目描述

选取显像管的任意一个平面,一开始平面内有 \( n \) 个电子,初始速度分别为 \( \vec { v _ i } \) ,定义飘升系数为:
\[ \sum _ { l \leq i < j \leq r } \left | \vec { v _ i } \times \vec { v _ j } \right | ^ 2 \]

电子的速度常常会发生变化。也就是说,有两种类型的操作:

  • 1 p x y 将 \( \vec { v _ p } \) 改为 \( ( x , y ) \);
  • 2 l r 询问 \( \left [ l , r \right ] \) 这段区间内的电子的飘升系数。

答案对 \( 20170927 \) 取模即可。

数据范围

对于 \(100\%\) 的数据,\(1\leq n,m\leq 10^6\)。

题解

\[
\begin {aligned}
& \sum _ { l \leq i < j \leq r } \left | \vec { v _ i } \times \vec { v _ j } \right | ^ 2 \\
=&\sum_{l\leq i\leq j\leq r}\left|\vec{v_i}\times\vec{v_j}\right|^2\\
=&\sum_{l\leq i\leq j\leq r}\left(x_iy_j-x_jy_i\right)^2\\
=&\sum_{l\leq i\leq j\leq r}\left[(x_iy_j)^2-2x_ix_jy_iy_j+(x_jy_i)^2\right]\\
=&\sum_{l\leq i\leq j\leq r}(x_iy_j)^2-\sum_{l\leq i\leq j\leq r}2x_ix_jy_iy_j+\sum_{l\leq i\leq j\leq r}(x_jy_i)^2\\
=&\frac{1}{2}\sum_{l\leq i,j\leq r}(x_iy_j)^2-\sum_{l\leq i,j\leq r}x_ix_jy_iy_j+\frac{1}{2}\sum_{l\leq i,j\leq r}(x_jy_i)^2\\
=&\frac{1}{2}\sum_{l\leq i,j\leq r}(x_iy_j)^2+\frac{1}{2}\sum_{l\leq i,j\leq r}(x_jy_i)^2-\sum_{l\leq i,j\leq r}x_ix_jy_iy_j\\
=&\sum^r_{i=l}x^2_i\times\sum^r_{i=l}y^2_i-\sum^r_{i=l}(x_iy_i)^2\\
\end{aligned}
\]

用树状数组维护即可,时间复杂度 \(\Theta((n+m)\log_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 20170927
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=1000000+5;
const int MAXM=1000000+5;

struct TreeArray{
	#define lowbit(x) ( (x) & ( - (x) ) )
	int n;
	ll unit[MAXN];
	inline void Init(reg int size){
		n=size;
		memset(unit,0,sizeof(unit));
		return;
	}
	inline void Update(reg int ID,reg ll val){
		val%=MOD;
		while(ID<=n){
			unit[ID]=(unit[ID]+val)%MOD;
			ID+=lowbit(ID);
		}
		return;
	}
	inline ll Query(reg int ID){
		reg ll res=0;
		while(ID){
			res=(res+unit[ID])%MOD;
			ID-=lowbit(ID);
		}
		return res;
	}
	#undef lowbit
};

int n,m;
ll x[MAXN],y[MAXN],xy[MAXN];
TreeArray Tx,Ty,Txy;

inline void Read(void);
inline void Work(void);

int main(void){
	Read();
	Work();
	return 0;
}

inline void Read(void){
	n=read(),m=read();
	Tx.Init(n),Ty.Init(n),Txy.Init(n);
	for(reg int i=1;i<=n;++i){
		x[i]=read(),y[i]=read();
		xy[i]=x[i]*y[i]%MOD;
		Tx.Update(i,x[i]*x[i]);
		Ty.Update(i,y[i]*y[i]);
		Txy.Update(i,xy[i]);
	}
	return;
}

inline void Work(void){
	while(m--){
		static int opt,p,l,r;
		static ll u,v;
		opt=read();
		if(opt==1){
			p=read(),u=read(),v=read();
			Tx.Update(p,-(x[p]*x[p]%MOD)+MOD);
			Ty.Update(p,-(y[p]*y[p]%MOD)+MOD);
			Txy.Update(p,-(xy[p]%MOD)+MOD);
			x[p]=u,y[p]=v,xy[p]=u*v%MOD;
			Tx.Update(p,x[p]*x[p]);
			Ty.Update(p,y[p]*y[p]);
			Txy.Update(p,xy[p]);
		}
		if(opt==2){
			l=read(),r=read();
			ll temp1=((Tx.Query(r)-Tx.Query(l-1))%MOD+MOD)%MOD;
			ll temp2=((Ty.Query(r)-Ty.Query(l-1))%MOD+MOD)%MOD;
			ll temp3=((Txy.Query(r)-Txy.Query(l-1))%MOD+MOD)%MOD;
			temp3=temp3*temp3%MOD;
			ll ans=((temp1*temp2%MOD-temp3)%MOD+MOD)%MOD;
			printf("%lld\n",ans);
		}
	}
	return;
}

导线问题 hamon

题目描述

哈蒙有 \(n\) 条导线排成一排,每条导线有一个电阻值,神奇的电光只能从一根导线传到电阻比它大的上面,而且必须从左边向右传导,当然导线不必是连续的。

哈蒙想知道电光最多能通过多少条导线,还想知道这样的方案有多少,方案数对 \(123456789\) 取模。

数据范围

对于 \(100\%\) 的数据,\(1\leq n\leq 10^5\),电阻值不超过 \(10^5\)。

题解

求单调递增序列长度和方案数,用树状数组 + 动态开点线段树即可。

时间复杂度为 \(\Theta(n\log_2n)\)。

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

const int MAXN=1e5+5;
const int MAXR=1e5+5;
const int p=123456789;

inline int add(int a,int b){
	int sum=a+b;
	return sum>=p?sum-p:sum;
}

namespace SegmentTree{
	#define mid ( ( (l) + (r) ) >> 1 )
	const int MAXSIZE=MAXN*40;
	struct Node{
		int lson,rson;
		int val;
		#define lson(x) unit[(x)].lson
		#define rson(x) unit[(x)].rson
		#define val(x) unit[(x)].val
	};
	int tot;
	int root[MAXN];
	Node unit[MAXSIZE];
	inline void update(int &k,int l,int r,int pos,int Val){
		if(!k)
			k=++tot;
		val(k)=add(val(k),Val);
		if(l!=r){
			if(pos<=mid)
				update(lson(k),l,mid,pos,Val);
			else
				update(rson(k),mid+1,r,pos,Val);
		}
		return;
	}
	inline int query(int k,int l,int r,int pos){
		if(r<=pos)
			return val(k);
		if(pos<=mid)
			return query(lson(k),l,mid,pos);
		else
			return add(val(lson(k)),query(rson(k),mid+1,r,pos));
	}
	#undef mid
}

namespace BIT{
	inline int lowbit(int x){
		return x&(-x);
	}
	int n,unit[MAXR];
	inline void Init(int s){
		n=s;
		memset(unit,0,sizeof(unit));
		return;
	}
	inline void update(int id,int val){
		for(int i=id;i<=n;i+=lowbit(i))
			unit[i]=max(unit[i],val);
		return;
	}
	inline int query(int id){
		int res=0;
		for(int i=id;i;i-=lowbit(i))
			res=max(res,unit[i]);
		return res;
	}
}

int n,type;
int f[MAXN],g[MAXN];

int main(void){
	scanf("%d%d",&n,&type);
	BIT::Init(1e5);
	int ans1=0,ans2=0;
	for(int i=1;i<=n;++i){
		static int r;
		scanf("%d",&r);
		f[i]=BIT::query(r-1);
		if(f[i]==0)
			g[i]=1;
		else
			g[i]=SegmentTree::query(SegmentTree::root[f[i]],0,1e5,r-1);
		++f[i];
		if(f[i]>ans1)
			ans1=f[i],ans2=0;
		if(f[i]==ans1)
			ans2=add(ans2,g[i]);
		SegmentTree::update(SegmentTree::root[f[i]],0,1e5,r,g[i]);
		BIT::update(r,f[i]);
	}
	if(!type)
		printf("%d\n",ans1);
	else
		printf("%d\n%d\n",ans1,ans2);
	return 0;
}

数羊 insomnia

题目描述

小明每天晚上都在数羊。

对于每只羊 \(i\),都有一个吵闹程度 \(a_i\),每只羊的吵闹程度都不同。

小明要数的是对于羊 \(i,j,k(i<j<k)\) 满足 \(a_i<a_k\) 而且 \(a_k<a_j\) 的羊的 \(3\) 元排列 \((i,j,k)\) 组数。

现在小明想请你帮他数这样的羊的组数。

数据范围

对于 \(100\%\),\(n\leq 2\times 10^5\),保证 \(\{a_n\}\) 是 \(1\sim n\) 的排列。

题解

显然 \(f\left(\overline{1xx}\right)=f\left(\overline{123}\right)+f\left(\overline{132}\right)\)。

那么 \(f\left(\overline{132}\right)=f\left(\overline{1xx}\right)-f\left(\overline{123}\right)\)。

用树状数组求 \(f\left(\overline{1xx}\right)\),\(f\left(\overline{123}\right)\) 即可。

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

const int MAXN=2e5+5;

struct BIT{
	inline int lowbit(int x){
		return x&(-x);
	}
	int n,unit[MAXN];
	inline void Init(int s){
		n=s;
		memset(unit,0,sizeof(unit));
		return;
	}
	inline void update(int id,int val){
		for(int i=id;i<=n;i+=lowbit(i))
			unit[i]+=val;
		return;
	}
	inline int query(int id){
		int res=0;
		for(int i=id;i;i-=lowbit(i))
			res+=unit[i];
		return res;
	}
};

int n;
int a[MAXN];
BIT T;
int l[MAXN],r[MAXN];

int main(void){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	T.Init(n);
	for(int i=1;i<=n;++i){
		l[i]=T.query(a[i]-1);
		T.update(a[i],1);
	}
	T.Init(n);
	for(int i=n;i>=1;--i){
		r[i]=T.query(n)-T.query(a[i]);
		T.update(a[i],1);
	}
	ll ans=0;
	T.Init(n);
	for(int i=n;i>=1;--i){
		int tmp=T.query(n)-T.query(a[i]);
		ans+=1ll*tmp*(tmp-1)/2;
		T.update(a[i],1);
	}
	for(int i=1;i<=n;++i)
		ans-=1ll*l[i]*r[i];
	printf("%lld\n",ans);
	return 0;
}

跳台阶 sprung

题目描述

球场边有 \(N\) 个台阶排成一行,第 \(i\) 个台阶的高度是 \(H_i(0<H_i\leq 10^9)\),第 \(0\) 个台阶,也就是地面的高度为 \(0\)。Polo 打算把这 \(N\) 个台阶分成两个集合 \(S_a,S_b\)(可以为空),对于一个台阶集合 \(S=\{P_1,P_2,\cdots,P_{|S|}\}\),其中 \(P_1<P_2<\cdots<P_{|S|}\),他需要花费
\[\sum^{|S|}_{i=1}|H_{p_i}-H_{p_{i-1}}|\] 的体力值来完成。

现在他希望两次跳跃所需的总体力值最小,你能帮帮他吗?

数据范围

对于 \(100\%\) 的数据,\(1\leq N\leq 5\times 10^5\)。

题解

设 \(f_{i,j}\) 表示两集合末尾台阶编号为 \(i,j\) 时的最小体力值,那么显然有 \(i\ne j\),不妨令 \(i>j\),那么我们分类讨论:

  • \(i>j+1\Rightarrow i-1>j\),此时 \(i-1\) 必定与 \(i\) 在同一个集合,所以有
    \[f_{i,j}=f_{i-1,j}+\left|H_i-H_{i-1}\right|\]
  • \(i=j+1\Rightarrow i-1=j\),我们有
    \[f_{i,j}=\min_{k<j}\{f_{i-1,k}+\left|H_i-H_k\right|\}\]

其实我们发现后一种状态转移方程可以单独拿出来做,设 \(g_i=f_{i,j-1}\),则
\[g_i=\min\{g_j+\text{sum}_{i-1}-\text{sum}_j+\left|H_i-H_{j-1}\right|\}\]

把绝对值拿掉就好做了,用树状数组维护即可,时间复杂度为 \(\Theta(n\log_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=5e5+5;
const ll inf=0x3f3f3f3f3f3f3f3fll;

struct BIT{
	inline int lowbit(reg int x){
		return x&(-x);
	}
	int n;
	ll unit[MAXN];
	inline void Init(reg int s){
		n=s;
		memset(unit,0x3f,sizeof(unit));
		return;
	}
	inline void update(reg int id,ll val){
		for(reg int i=id;i<=n;i+=lowbit(i))
			unit[i]=min(unit[i],val);
		return;
	}
	inline ll query(reg int id){
		ll res=inf;
		for(reg int i=id;i;i-=lowbit(i))
			res=min(res,unit[i]);
		return res;
	}
};

int n;
int h[MAXN];
vector<int> V;
ll sum[MAXN];
BIT T1,T2;
int p[MAXN];
ll g[MAXN];

int main(void){
	scanf("%d",&n);
	for(reg int i=1;i<=n;++i){
		scanf("%d",&h[i]);
		V.push_back(h[i]);
		sum[i]=sum[i-1]+abs(h[i]-h[i-1]);
	}
	V.push_back(0);
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	for(reg int i=1;i<=n+1;++i)
		p[i]=lower_bound(V.begin(),V.end(),h[i-1])-V.begin()+1;
	reg int m=V.size();
	ll ans=inf;
	T1.Init(n+1),T2.Init(n+1);
	g[1]=h[1];
	T1.update(p[1],0),T2.update(m-p[1]+1,0);
	ans=min(ans,g[1]+sum[n]-sum[1]);
	for(reg int i=2;i<=n;++i){
		g[i]=min(T1.query(p[i+1])+h[i],T2.query(m-p[i+1]+1)-h[i])+sum[i-1];
		T1.update(p[i],g[i]-sum[i]-h[i-1]);
		T2.update(m-p[i]+1,g[i]-sum[i]+h[i-1]);
		ans=min(ans,g[i]+sum[n]-sum[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

分组 group

题目描述

社区有 \(n\) 个居民,每个居民有一定的地位和年龄,\(r_i\) 表示第 \(i\) 个人的地位,\(a_i\) 表示第 \(i\) 个人的年龄。

最近社区里要举行活动,要求几个人分成一个小组,小组中必须要有一个队长,要成为队长要满足以下条件:

  1. 队长在小组中的地位应该是最高的(可以并列第一);
  2. 小组中其他成员的年龄和队长的年龄差距不能超过 \(K\)。

有些人想和自己亲密的人组在同一个小组,同时希望所在的小组人越多越好。比如 \(x\) 和 \(y\) 想在同一个小组,同时希望他们所在的小组人越多越好,当然,它们也必须选一个符合上述条件的队长,那么问你,要同时包含 \(x\) 和 \(y\) 的小组,最多可以组多少人?

数据范围

对于 \(100\%\) 的数据,\(2\leq n\leq 10^5\),\(0\leq k\leq 10^9\),\(1\leq r_i,a_i\leq 10^9\),\(1\leq q\leq 10^5\),\(1\leq x,y\leq n\),\(x\ne y\)。

题解

感觉这题用到树状数组的地方不是特别多。

先预处理以每个人为队长的队伍的最多人数,使用树状数组+离散化可以做到 \(\Theta(\omega n\log_2\omega n)\) 的复杂度,其中 \(\omega=3\),是 \(a_i-K,a_i,a_i+K\) 的贡献。

然后通过 \(x,y\) 限制查询队长的年龄区间,通过排序+线段树可以做到 \(\Theta(\omega n\log_2\omega n)\) 的复杂度,其中 \(\omega=3\)。

总的时间复杂度是 \(\Theta(\omega n\log_2\omega n)\) 的复杂度,其中 \(\omega=3\)。

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

const int MAXN=1e5+5;
const int MAXQ=1e5+5;
const int MAXM=3*MAXN;

struct Node{
	int id;
	int r;
	int L,pos,R;
	int cnt;
	inline bool operator<(const Node& a)const{
		return r<a.r;
	}
};

struct querys{
	int id;
	int x,y,Min;
	inline bool operator<(const querys& a)const{
		return Min<a.Min;
	}
};

namespace BIT{
	inline int lowbit(int x){
		return x&(-x);
	}
	int n,unit[MAXM];
	inline void Init(int s){
		n=s;
		memset(unit,0,sizeof(unit));
		return;
	}
	inline void update(int id,int val){
		for(int i=id;i<=n;i+=lowbit(i))
			unit[i]+=val;
		return;
	}
	inline int query(int id){
		int res=0;
		for(int i=id;i;i-=lowbit(i))
			res+=unit[i];
		return res;
	}
}

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		int Max;
		#define Max(x) unit[(x)].Max
	};
	Node unit[MAXM<<2];
	inline void pushup(int k){
		Max(k)=max(Max(lson),Max(rson));
		return;
	}
	inline void update(int k,int l,int r,int pos,int val){
		if(l==r){
			Max(k)=max(Max(k),val);
			return;
		}
		if(pos<=mid)
			update(lson,l,mid,pos,val);
		else
			update(rson,mid+1,r,pos,val);
		pushup(k);
		return;
	}
	inline int query(int k,int l,int r,int L,int R){
		if(L<=l&&r<=R)
			return Max(k);
		int res=0;
		if(L<=mid)
			res=max(res,query(lson,l,mid,L,R));
		if(R>mid)
			res=max(res,query(rson,mid+1,r,L,R));
		return res;
	}
	#undef lson
	#undef rson
	#undef mid
}

int n,Q,K;
vector<int> V;
Node a[MAXN];
querys q[MAXQ];
int pos[MAXN];
int ans[MAXQ];

int main(void){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i].r);
	for(int i=1;i<=n;++i){
		static int age;
		scanf("%d",&age);
		a[i].id=i,a[i].L=age-K,a[i].pos=age,a[i].R=age+K;
		V.push_back(a[i].L),V.push_back(a[i].pos),V.push_back(a[i].R);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	int m=V.size();
	for(int i=1;i<=n;++i){
		a[i].L=lower_bound(V.begin(),V.end(),a[i].L)-V.begin()+1;
		a[i].pos=lower_bound(V.begin(),V.end(),a[i].pos)-V.begin()+1;
		a[i].R=lower_bound(V.begin(),V.end(),a[i].R)-V.begin()+1;
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;++i){
		q[i].id=i;
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].Min=max(a[q[i].x].r,a[q[i].y].r);
	}
	sort(a+1,a+n+1),sort(q+1,q+Q+1);
	BIT::Init(m);
	for(int l=1,r;l<=n;l=r+1){
		r=l;
		while(r<n&&a[r].r==a[r+1].r)
			++r;
		for(int i=l;i<=r;++i)
			BIT::update(a[i].pos,1);
		for(int i=l;i<=r;++i)
			a[i].cnt=BIT::query(a[i].R)-BIT::query(a[i].L-1);
	}
	for(int i=1;i<=n;++i)
		pos[a[i].id]=i;
	for(int i=Q,ptr=n;i>=1;--i){
		while(ptr>=1&&a[ptr].r>=q[i].Min){
			SegmentTree::update(1,1,m,a[ptr].pos,a[ptr].cnt);
			--ptr;
		}
		int x=pos[q[i].x],y=pos[q[i].y],l=max(a[x].L,a[y].L),r=min(a[x].R,a[y].R);
		if(l<=r)
			ans[q[i].id]=SegmentTree::query(1,1,m,l,r);
	}
	for(int i=1;i<=Q;++i)
		printf("%d\n",ans[i]?ans[i]:-1);
	return 0;
}