很巧的 trick。

首先離線。從大到小掃 \(l\)，維護數(shù)組 \(p_i\) 表示當前出現(xiàn) \(i\) 的最小的位置。

顯然當確定了左端點，從左到右的 \(\operatorname{mex}\) 是單調(diào)不降的。因此我們要求的就是一段區(qū)間 \([l',r']\)，滿足 \(\operatorname{mex}[l,l']\ge x\) 且 \(l'\) 最小，\(\operatorname{mex}[l,r']\le y\) 且 \(r'\) 最大。（其中 \(\operatorname{mex}[l,r]\) 表示區(qū)間 \([l,r]\) 的 \(\operatorname{mex}\)。）顯然 \(l'=\max_{0\le i<x}p_i\)，\(r'+1=\max_{0\le i\le y}p_i\)。用線段樹維護 \(p\) 即可。時間復雜度 \(O(n\log n)\)。代碼實現(xiàn)時要注意一些細節(jié)。

#include<cstdio>
#include<iostream>
#include<vector>
#define ll long long
#define il inline
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e5+5;
int n,m,a[maxn],ans[maxn];
struct wen{
	int x,y,id;
};
vector<wen> wt[maxn];
int tr[maxn<<2];
il void pushup(int id){
	tr[id]=max(tr[lid],tr[rid]);
}
il void build(int id,int l,int r){
	tr[id]=n+1;
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
}
il void upd(int id,int l,int r,int p,int v){
	if(l==r){
		tr[id]=v;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid){
		upd(lid,l,mid,p,v);
	}
	else{
		upd(rid,mid+1,r,p,v);
	}
	pushup(id);
}
il int query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return tr[id];
	}
	int mid=(L+R)>>1,res=0;
	if(l<=mid){
		res=max(res,query(lid,L,mid,l,r));
	}
	if(r>mid){
		res=max(res,query(rid,mid+1,R,l,r));
	}
	return res;
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1,l,x,y;i<=m;i++){
		cin>>l>>x>>y;
		wt[l].pb((wen){x,y,i});
	}
	build(1,0,n);
	for(int i=n;i;i--){
		upd(1,0,n,a[i],i);
		for(wen j:wt[i]){
			int id=j.id,x=j.x,y=j.y;
			ans[id]=query(1,0,n,0,y)-(x?query(1,0,n,0,x-1):i);
		}
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}
}
int main(){return asbt::main();}