CF1039E Summer Oenothera Exhibition

题面传送门
既然题面告诉我们不强制在线那就离线。按照极差的顺序从小到大排序。
考虑维护st表之后其实可以暴力跳，时间复杂度\(O(n\log n+q n\log n)\)。
这种每个点向后跳的操作想到弹飞绵羊，就想到LCT。如果对于每个点都维护这个点当前往后跳能跳到第几个点，那么查询的时候直接从\(1\)点开始查LCT深度即可。这样的复杂度是\(O(n^2\log n+q\log n)\)
两边对询问和序列长度的复杂度不大一样，考虑根号分治。设阈值\(B\)，往后跳的长度小于\(B\)的时候LCT连边，大于\(B\)的时候暴力跳，时间复杂度为\(O(nB\log n+q\frac{n}{B}\log n)\)，取\(B=\sqrt q\)时有最优\(O(n\sqrt q\log n)\)
实测的情况下LCT常数很大，所以把\(B\)的值放小一点会优很多。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (100000+5)
#define M (1000000+5)
#define K (20+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,m,x,k,B,A[N],lg[N],Mx[N][20],R[N],Mi[N][20],Ans[N],ToT,H[N];
I int Qry(int P,int w){int x=-1e9,y=1e9;for(int i=18;~i;i--) P+(1<B.w;}}Pus;priority_queue Q;
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	int i,j;scanf("%d%d%d",&n,&m,&k);B=sqrt(n/64);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for(i=n;i;i--){
		for(Mx[i][0]=Mi[i][0]=A[i],j=1;i+(1<