《高手训练》解题报告 4.3 线段树

线段树的练习题。

对应 OJ 的传送门

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

线段树

线段树是一种优秀的维护序列的数据结构,支持所有满足结合律的操作的维护。

字符串排序 string

时空限制:\(3\texttt{s},256\texttt{MiB}\)。

题目描述

给定一个由小写字母组成的字符串 \(S\)。有 \(m\) 次操作,每次操作给定 \(3\) 个参数 \(l,r,x\)。如果 \(x=1\),将 \(S_l\sim S_r\) 升序排序;如果 \(x=0\),将 \(S_l\sim S_r\) 降序排序。你需要求出最终序列。

数据范围

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

题解

线段树套路题,用线段树维护区间修改和区间查询,时间复杂度为 \(\Theta(|S|n\log_2n)\),其中 \(|S|\) 代表字符集大小,即 \(|S|=26\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;

int n,m;
char str[MAXN];

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		int T[26];
		int tag;
		#define T(x) unit[(x)].T
		#define tag(x) unit[(x)].tag
	};
	Node unit[MAXN<<2];
	inline void pushup(reg int k){
		for(reg int i=0;i<26;++i)
			T(k)[i]=T(lson)[i]+T(rson)[i];
		return;
	}
	inline void build(reg int k,reg int l,reg int r,reg char str[]){
		tag(k)=-1;
		if(l==r){
			++T(k)[str[l]-'a'];
			return;
		}
		build(lson,l,mid,str),build(rson,mid+1,r,str);
		pushup(k);
		return;
	}
	inline void set(reg int k,reg int l,reg int r,reg int val){
		for(reg int i=0;i<26;++i)
			T(k)[i]=0;
		T(k)[val]=r-l+1;
		tag(k)=val;
		return;
	}
	inline void pushdown(reg int k,reg int l,reg int r){
		if(tag(k)!=-1){
			set(lson,l,mid,tag(k));
			set(rson,mid+1,r,tag(k));
			tag(k)=-1;
		}
		return;
	}
	inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){
		if(L<=l&&r<=R){
			set(k,l,r,val);
			return;
		}
		pushdown(k,l,r);
		if(L<=mid)
			update(lson,l,mid,L,R,val);
		if(R>mid)
			update(rson,mid+1,r,L,R,val);
		pushup(k);
		return;
	}
	inline Node query(reg int k,reg int l,reg int r,reg int L,reg int R){
		if(L<=l&&r<=R)
			return unit[k];
		pushdown(k,l,r);
		if(L<=mid&&mid<R){
			Node le=query(lson,l,mid,L,R),ri=query(rson,mid+1,r,L,R);
			for(reg int i=0;i<26;++i)
				le.T[i]+=ri.T[i];
			return le;
		}
		else if(L<=mid)
			return query(lson,l,mid,L,R);
		else
			return query(rson,mid+1,r,L,R);
	}
	inline void print(reg int k,reg int l,reg int r){
		if(l==r){
			for(reg int i=0;i<26;++i)
				if(T(k)[i]){
					putchar('a'+i);
					break;
				}
			return;
		}
		pushdown(k,l,r);
		print(lson,l,mid),print(rson,mid+1,r);
		return;
	}
	#undef lson
	#undef rson
	#undef mid
}

using namespace SegmentTree;

int main(void){
	n=read(),m=read();
	scanf("%s",str+1);
	build(1,1,n,str);
	while(m--){
		static int l,r,x;
		static Node tmp;
		l=read(),r=read(),x=read();
		if(x==1){
			tmp=query(1,1,n,l,r);
			reg int lptr=l;
			for(reg int i=0;i<26;++i)
				if(tmp.T[i]){
					update(1,1,n,lptr,lptr+tmp.T[i]-1,i);
					lptr+=tmp.T[i];
				}
		}
		else{
			tmp=query(1,1,n,l,r);
			reg int rptr=r;
			for(reg int i=0;i<26;++i)
				if(tmp.T[i]){
					update(1,1,n,rptr-tmp.T[i]+1,rptr,i);
					rptr-=tmp.T[i];
				}
		}
	}
	print(1,1,n);
	putchar('\n');
	return 0;
}

纪念碑 square

时空限制:\(3\texttt{s},256\texttt{MiB}\)。

题目描述

2034 年,某中学决定修建校庆 100 周年纪念碑,作为杰出校友的你被找了过来,帮校方确定纪念碑的选址.中学的土地可以看作是一个长为 \(n\),宽为 \(m\) 的矩形。它由 \(n\times m\) 个 \(1\times 1\) 的正方形组成,其中左下角的正方形的坐标为 \((1,1)\),右上角的正方形的坐标为 \((n,m)\)。其中有一些土地已经被用来修建建筑物,每一幢建筑物都可以看做是一个左下角为 \((x_1,y_1)\),右上角为 \((x_2,y_2)\) 的矩形。纪念碑可以看作是一个正方形。校方希望你找出一块最大的正方形区域供他们参考。

数据范围

对于 \(100\%\) 的数据,\(p\leq 4\times 10^5\),\(m,n\leq 10^6\)。

题解

扫描线的题。

考虑用线段树维护 \(y\) 轴最长空位长度,并用双指针来维护 \(x\) 轴坐标长度,当 \(y\) 轴坐标长度小于 \(x\) 坐标长度时,左指针右移。

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

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#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 char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e6+5;

struct Node{
	int l,r;
	inline Node(reg int l=0,reg int r=0):l(l),r(r){
		return;
	}
};

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		int len;
		int lMax,rMax,Max;
		int tag;
		#define len(x) unit[(x)].len
		#define lMax(x) unit[(x)].lMax
		#define rMax(x) unit[(x)].rMax
		#define Max(x) unit[(x)].Max
		#define tag(x) unit[(x)].tag
	};
	Node unit[MAXN<<2];
	inline void build(reg int k,reg int l,reg int r){
		len(k)=lMax(k)=rMax(k)=Max(k)=r-l+1;
		if(l==r)
			return;
		build(lson,l,mid),build(rson,mid+1,r);
		return;
	}
	inline void update(reg int k){
		if(tag(k))
			lMax(k)=rMax(k)=Max(k)=0;
		else if(len(k)==1)
			lMax(k)=rMax(k)=Max(k)=1;
		else{
			lMax(k)=(lMax(lson)==len(lson))?len(lson)+lMax(rson):lMax(lson);
			rMax(k)=(rMax(rson)==len(rson))?len(rson)+rMax(lson):rMax(rson);
			Max(k)=max(rMax(lson)+lMax(rson),max(Max(lson),Max(rson)));
		}
		return;
	}
	inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){
		if(L<=l&&r<=R){
			tag(k)+=val;
			update(k);
			return;
		}
		if(L<=mid)
			update(lson,l,mid,L,R,val);
		if(R>mid)
			update(rson,mid+1,r,L,R,val);
		update(k);
		return;
	}
	#undef lson
	#undef rson
	#undef mid
}

int n,m,p;
vector<Node> add[MAXN],del[MAXN];

int main(void){
	n=read(),m=read(),p=read();
	for(reg int i=1;i<=p;++i){
		static int x1,y1,x2,y2;
		x1=read(),y1=read(),x2=read(),y2=read();
		add[x1].push_back(Node(y1,y2));
		del[x2].push_back(Node(y1,y2));
	}
	int ans=0;
	SegmentTree::build(1,1,m);
	for(reg int r=1,l=1;r<=n;++r){
		for(reg int i=0,siz=add[r].size();i<siz;++i)
			SegmentTree::update(1,1,m,add[r][i].l,add[r][i].r,1);
		ans=max(ans,min(SegmentTree::unit[1].Max,r-l+1));
		while(r-l+1>SegmentTree::unit[1].Max){
			for(reg int i=0,siz=del[l].size();i<siz;++i)
				SegmentTree::update(1,1,m,del[l][i].l,del[l][i].r,-1);
			++l;
		}
	}
	printf("%d\n",ans);
	return 0;
}

区间连通性 interval

时空限制:\(1\texttt{s},256\texttt{MiB}\)。

题目描述

对于两个区间 \((a,b)\) 和 \((c,d)\),若 \(c<a<d\) 或 \(c<b<d\),则可以从 \((a,b)\) 走到 \((c,d)\),现在有以下两种操作:

  1. \(1\) \(x\) \(y\)(\(x<y\)),表示在区间集合中添加 \((x,y)\) 这个区间,保证新加入的这个区间长度一定比之前的所有区间长度长。
  2. \(2\) \(a\) \(b\)(\(a\ne b\)),表示询问是否存在一条路径能从第 \(a\) 个区间走到第 \(b\) 个区间。

初始时区间集合为空,现在请你来回答所有的询问。

数据范围

对于 \(100\%\) 的数据,\(1\leq n\leq 10^5\),区间端点在 \(32\) 位有符号整数范围内。

题解

如果区间 \(A\) 可以到 \(B\) 且 \(|A|\geq |B|\),那么显然 \(B\) 可以到 \(A\),这说明初期的连通关系是无向的。

我们不妨用并查集来维护这种无向连通关系,如果两个区间在同一个连通块内(可以互相到达),那么它们在并查集中同属一个集合。

考虑到区间长度单调递增,那么如果存在区间 \([l,r]\) 满足当前加入区间 \((u,v)\) 有一个端点(\(u+1,v-1\))在 \([l,r]\) 内,那么它们必然可以相互到达,于是我们可以用线段树来维护这种简单的重叠关系。

具体的,我们线段树上的每一个节点上开一个 \(\texttt{vector}\),表示该节点代表区间上覆盖有的区间的编号的集合。我们每次直接查询当前区间两个端点在线段树上的对应区间,直接合并即可。最后删除之前的用过的区间,更新为与当前区间重合的所有区间的并,单次修改时间复杂度为 \(\Theta(\log_2n)\)。

考虑查询,则由于没有区间大小关系(可能 \(y\) 的代表集合 包含于 \(x\) 的代表集合,此时 \(x\) 不能到 \(y\) 但 \(y\) 可以到 \(x\)),我们应该直接根据题目的定义判定:

  • \(x,y\) 属于同一个集合,显然可以相互到达。
  • \(x\to y\),符合题意。

线段树单次查询的时间复杂度为 \(\Theta(\alpha(n))\)。

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

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

inline int read(void){
	static int tmp;
	scanf("%d",&tmp);
	return tmp;
}

const int MAXN=2e5+5;

struct Node{
	int opt,l,r;
	inline Node(reg int opt=0,reg int l=0,reg int r=0):opt(opt),l(l),r(r){
		return;
	}
};

int n;
Node a[MAXN];
vector<int> V;

int fa[MAXN];
int le[MAXN],ri[MAXN];

inline int find(reg int x){
	if(x==fa[x])
		return x;
	else
		return fa[x]=find(fa[x]);
}

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		vector<int> V;
		#define V(x) unit[(x)].V
	};
	Node unit[MAXN<<2];
	inline void merge(reg int k,reg int l,reg int r,reg int pos,reg int id){
		for(reg int i=0,siz=V(k).size();i<siz;++i){
			reg int rx=find(V(k)[i]),ry=find(id);
			fa[rx]=ry;
			le[ry]=min(le[ry],le[rx]);
			ri[ry]=max(ri[ry],ri[rx]);
		}
		V(k).clear();
		if(l==r)
			return;
		if(pos<=mid)
			merge(lson,l,mid,pos,id);
		else
			merge(rson,mid+1,r,pos,id);
		return;
	}
	inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,int id){
		if(L==l&&r==R){
			V(k).push_back(id);
			return;
		}
		if(R<=mid)
			update(lson,l,mid,L,R,id);
		else if(mid<L)
			update(rson,mid+1,r,L,R,id);
		else
			update(lson,l,mid,L,mid,id),update(rson,mid+1,r,mid+1,R,id);
		return;
	}
	#undef lson
	#undef rson
	#undef mid
}

int main(void){
	n=read();
	for(reg int i=1;i<=n;++i){
		static int opt,l,r;
		opt=read(),l=read(),r=read();
		a[i]=Node(opt,l,r);
		if(opt==1)
			V.push_back(l),V.push_back(r);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	for(reg int i=1;i<=n;++i)
		if(a[i].opt==1){
			a[i].l=lower_bound(V.begin(),V.end(),a[i].l)-V.begin()+1;
			a[i].r=lower_bound(V.begin(),V.end(),a[i].r)-V.begin()+1;
		}
	reg int m=V.size();
	reg int tot=0;
	for(reg int i=1;i<=n;++i)
		if(a[i].opt==1){
			++tot;
			fa[tot]=tot;
			le[tot]=a[i].l,ri[tot]=a[i].r;
			SegmentTree::merge(1,1,m,a[i].l,tot);
			SegmentTree::merge(1,1,m,a[i].r,tot);
			reg int x=find(tot);
			if(le[x]+1<=ri[x]-1)
				SegmentTree::update(1,1,m,le[x]+1,ri[x]-1,tot);
		}
		else{
			reg int x=a[i].l,y=a[i].r;
			reg int rx=find(x),ry=find(y);
			if(rx==ry||(le[ry]<le[rx]&&le[rx]<ri[ry])||(le[ry]<ri[rx]&&ri[rx]<ri[ry]))
				puts("YES");
			else
				puts("NO");
		}
	return 0;
}

栈的维护 weed

时空限制:\(1\texttt{s},512\texttt{MiB}\)。

题目描述

从前有个栈,一开始是空的。

你写下了 \(m\) 个操作,每个操作形如 \(k\) \(v\),若 \(k=0\),代表往栈顶加入一个数 \(v\);若 \(k=1\),则代表从栈顶弹出 \(v\) 个数,如果栈中的元素少于 \(v\) 个,则全部弹出。

接着你又进行了 \(q\) 次修改,每次你会选择一个操作,并且修改它的两个参数。

在每次修改后,你都要求出如果依次执行这些操作,最后栈中剩下的元素之和。

数据范围

对于 \(100\%\) 的数据,\(m,q\leq 2\times 10^5\),\(v\leq 10^4\)。

题解

不难看出是线段树分治,即对时间建立线段树维护操作。

具体的,我们每个节点维护三个值:

  • \(\texttt{add}\),表示经过这个区间之后增加的元素个数。如果一个元素在这个区间加入后删除,则它对 \(\texttt{add}\) 没有影响。
  • \(\texttt{del}\),表示经过这个区间之后减少的元素个数。如果一个元素在这个区间加入后删除,则它对 \(\texttt{del}\) 没有影响。
  • \(\texttt{sum}\),表示经过这个区间之后栈中剩余元素的和。

那么我们可以得出合并式:

  • \(\texttt{add}_k=\max\{\texttt{add}_{\texttt{lson}}-\texttt{del}_{\texttt{rson}},0\}+\texttt{add}_{\texttt{rson}}\)
  • \(\texttt{del}_k=\texttt{del}_{\texttt{lson}}+\max\{\texttt{del}_{\texttt{rson}}-\texttt{add}_{\texttt{lson}},0\}\)
  • \(\texttt{sum}_k=\texttt{sum}_{\texttt{rson}}+\operatorname{query}(\texttt{lson},\texttt{del}_{\texttt{rson}})\)

时间复杂度为 \(\Theta(n\log_2n+m\log^2_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#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 MAXM=2e5+5;

struct Operation{
	int k,v;
	inline Operation(reg int k=0,reg int v=0):k(k),v(v){
		return;
	}
	inline void Read(void){
		k=read(),v=read();
		return;
	}
};

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		int add,del;
		int sum;
		#define add(x) unit[(x)].add
		#define del(x) unit[(x)].del
		#define sum(x) unit[(x)].sum
	};
	Node unit[MAXM<<2];
	inline int query(reg int k,reg int val){
		if(add(k)<=val)
			return 0;
		if(add(rson)>=val)
			return sum(k)-sum(rson)+query(rson,val);
		else
			return query(lson,val-add(rson)+del(rson));
	}
	inline void pushup(reg int k){
		del(k)=del(lson)+max(del(rson)-add(lson),0);
		add(k)=max(add(lson)-del(rson),0)+add(rson);
		sum(k)=sum(rson)+(del(rson)?query(lson,del(rson)):sum(lson));
		return;
	}
	inline void build(reg int k,reg int l,reg int r,reg Operation a[]){
		if(l==r){
			if(a[l].k==1)
				del(k)=a[l].v,add(k)=sum(k)=0;
			else
				del(k)=0,add(k)=1,sum(k)=a[l].v;
			return;
		}
		build(lson,l,mid,a),build(rson,mid+1,r,a);
		pushup(k);
		return;
	}
	inline void update(reg int k,reg int l,reg int r,reg int pos,reg int K,reg int V){
		if(l==r){
			if(K==1)
				del(k)=V,add(k)=sum(k)=0;
			else
				del(k)=0,add(k)=1,sum(k)=V;
			return;
		}
		if(pos<=mid)
			update(lson,l,mid,pos,K,V);
		else
			update(rson,mid+1,r,pos,K,V);
		pushup(k);
		return;
	}
	#undef lson
	#undef rson
	#undef mid
}

int m,q;
Operation O[MAXM];

int main(void){
	m=read(),q=read();
	for(reg int i=1;i<=m;++i)
		O[i].Read();
	SegmentTree::build(1,1,m,O);
	while(q--){
		static int c,k,v;
		c=read(),k=read(),v=read();
		SegmentTree::update(1,1,m,c,k,v);
		printf("%d\n",SegmentTree::unit[1].sum);
	}
	return 0;
}

星际探测 melancholy

时空限制:\(1\texttt{s},256\texttt{MiB}\)。

题目描述

DX3906 星系,Melancholy 星上,我在勘测这里的地质情况。

我把这些天来已探测到的区域分为 \(N\) 组,并用二元组 \((D,V)\) 对每一组进行标记:其中 \(D\) 为区域的相对距离,\(V\) 为内部地质元素的相对丰富程度。

在我的日程安排表上有 \(Q\) 项指派的计划。每项计划的形式是类似的,都是“对相对距离 \(D\) 在 \([L,R]\) 之间的区域进行进一步的勘测,并在其中有次序地挑出 \(K\) 块区域的样本进行研究。”采集这 \(K\) 块的样品后,在实验中它们的研究价值即为这 \(K\) 块区域地质相对丰富程度 \(V\) 的乘积。

我对这 \(Q\) 项计划都进行了评估:一项计划的评估值 \(P\) 为所有可能选取情况的研究价值之和。

但是由于仪器的原因,在一次勘测中,这其中 \(V\) 最小的区域永远不会被选取。

现在我只想知道这 \(Q\) 项计划的评估值对 \(2^{32}\) 取模后的值。特殊地,如果没有 \(K\) 块区域可供选择,评估值为 \(0\)。

数据范围

对于 \(100\%\) 的数据,\(1\leq K\leq 6\),\(1\leq N,Q\leq 10^5\),\(1\leq D,V\leq 10^9\),\(1\leq L\leq R\leq 10^9\)。

数据保证所有区域的 \(D\) 与 \(V\) 互不相等。

题解

显然可以合并答案。答案的合并式为
\[f_{k,i}=\sum^i_{j=0}f_{\texttt{lson},j}f_{\texttt{rson},i-j}\]

所以我们先用线段树维护区间,然后最后把查询区间根据最小值位置裂成两半,最后合并即可。值得注意的是,合并答案时的单位元为:
\[
f_i=
\begin{cases}
1,&i=0\\
0,&i\ne 0
\end{cases}
\]

对 \(2^{32}\) 取模直接自然溢出 unisigned int 即可。

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

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef unsigned int uint;
typedef long long ll;
#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 char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;
const int MAXK=6+1;
const uint inf=0x7fffffffu;

struct Data{
	uint d,v;
	inline Data(reg uint d=0,reg uint v=0):d(d),v(v){
		return;
	}
	inline bool operator<(const Data& a)const{
		return d<a.d;
	}
};

int n,q;
Data a[MAXN];

namespace SegmentTree{
	#define lson ( (k) << 1 )
	#define rson ( (k) << 1 | 1 )
	#define mid ( ( (l) + (r) ) >> 1 )
	struct Node{
		int pos;
		uint f[MAXK];
		inline Node(void){
			pos=0,memset(f,0,sizeof(f));
			f[0]=1;
			return;
		}
		inline Node operator+(const Node& x){
			Node res;
			res.f[0]=0;
			if(a[pos].v<a[x.pos].v)
				res.pos=pos;
			else
				res.pos=x.pos;
			for(reg int i=0;i<MAXK;++i)
				for(reg int j=0;j<=i;++j)
					res.f[i]+=f[j]*x.f[i-j];
			return res;
		}
		#define f(x) unit[(x)].f
		#define pos(x) unit[(x)].pos
	};
	Node unit[MAXN<<2];
	inline void pushup(reg int k){
		unit[k]=unit[lson]+unit[rson];
		return;
	}
	inline void build(reg int k,reg int l,reg int r,reg Data a[]){
		if(l==r){
			f(k)[1]=a[l].v;
			pos(k)=l;
			return;
		}
		build(lson,l,mid,a),build(rson,mid+1,r,a);
		pushup(k);
		return;
	}
	inline Node query(reg int k,reg int l,reg int r,reg int L,reg int R){
		if(L<=l&&r<=R)
			return unit[k];
		Node res;
		if(L<=mid)
			res=res+query(lson,l,mid,L,R);
		if(R>mid)
			res=res+query(rson,mid+1,r,L,R);
		return res;
	}
	#undef lson
	#undef rson
	#undef mid
}

uint fac[MAXN];

using namespace SegmentTree;

int main(void){
	n=read(),q=read();
	a[0].v=inf;
	for(reg int i=1;i<=n;++i)
		a[i].d=read();
	for(reg int i=1;i<=n;++i)
		a[i].v=read();
	fac[0]=1;
	for(reg int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i;
	sort(a+1,a+n+1);
	build(1,1,n,a);
	while(q--){
		static int L,R,k;
		L=read(),R=read(),k=read();
		reg int l=lower_bound(a+1,a+n+1,Data(L,0))-a;
		reg int r=upper_bound(a+1,a+n+1,Data(R,0))-(a+1);
		if(l>r||l>n)
			puts("0");
		else{
			reg int pos=query(1,1,n,l,r).pos;
			Node tmp;
			if(l<=pos-1)
				tmp=tmp+query(1,1,n,l,pos-1);
			if(r>=pos+1)
				tmp=tmp+query(1,1,n,pos+1,r);
			printf("%u\n",tmp.f[k]*fac[k]);
		}
	}
	return 0;
}