Description：

给出一个排列，多次询问包含某个区间的长度最小的连续段，多解输出最左边的。

$1\leqslant n\leqslant 10^5$

Solution1：

首先可以注意到最后的答案一定是唯一的，因为连续段的交也是连续段，不可能有两个最短的包含他的连续段。

一个段能否构成连续段的充要条件是 $mx-mn=r-l$ ，移项就是 $(mx-mn)-(r-l)=0$ ，并且无论是不是连续段都有 $mx-mn\geqslant r-l$ ，我们可以求出来一个 $l[i]$ 表示以 $i$ 为右端点最长的连续段的左端点， $r[i]$ 与他相反，设询问的区间为 $L,R$ ，这时由上面那个结论我们可以发现我们只要找一组 $l',r'$ 满足 $l[r']\leqslant L,r[l']\geqslant R$ 那么 $l',r'$ 一定是一组合法的答案，因为他们是两个连续段的交，如果求出来了 $l,r$ 我们就可以在 $ST$ 表上二分求解。

现在的问题变成了怎么求这两个数组，我们可以扫描线枚举 $r$ ，用线段树维护 $(mx_{i,r}-mn_{i,r})-(-i)$ 的值，然后在线段树上维护一个最小值，每次在线段树上二分出最靠左的值为 $r$ 的位置，现在的问题就变成了如何维护 $mx$ 和 $mn$ ，我们可以维护一个单调栈，那么每次弹栈的区间就是需要修改最大 $/$ 最小值的范围。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 400010

int p[MAXN];

struct node

{

	int lc,rc;

	int minv,tag;

	node(){tag = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	t[t[rt].lc].tag += t[rt].tag;t[t[rt].lc].minv += t[rt].tag;

	t[t[rt].rc].tag += t[rt].tag;t[t[rt].rc].minv += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].tag += k;t[rt].minv += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int query(int rt,int L,int R,int k,int l,int r)

{

	if(t[rt].minv > k)return -1;

	if(l == r)return l;

	pushdown(rt);

	if(L <= l && r <= R)

	{

		if(t[t[rt].lc].minv == k)return query(t[rt].lc,L,R,k,l,mid);

		else return query(t[rt].rc,L,R,k,mid + 1,r);

	}

	int res = -1;

	if(L <= mid)res = query(t[rt].lc,L,R,k,l,mid);

	if(res != -1)return res;

	else return query(t[rt].rc,L,R,k,mid + 1,r);

}

void reset(int rt,int l,int r)

{

	t[rt].minv = t[rt].tag = 0;

	if(l == r)return;

	reset(t[rt].lc,l,mid);

	reset(t[rt].rc,mid + 1,r);

	return;

}

struct state

{

	int l,r,h;

};

stack<state> s1,s2;

int lef[MAXN],rig[MAXN];

int f1[MAXN][17],f2[MAXN][17];

int lg[MAXN];

int query1(int l,int r)

{

	int len = lg[r - l + 1];

	return min(f1[l][len],f1[r - (1 << len) + 1][len]);

}

int query2(int l,int r)

{

	int len = lg[r - l + 1];

	return max(f2[l][len],f2[r - (1 << len) + 1][len]);

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	build(root,1,n);

	for(int i = 1;i <= n;++i)add(root,i,i,i,1,n);

	for(int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

	for(int i = 1;i <= n;++i)

	{

		while(!s1.empty() && s1.top().h <= p[i])

		{

			add(root,s1.top().l,s1.top().r,p[i] - s1.top().h,1,n);

			s1.pop();

		}

		if(!s1.empty())s1.push((state){s1.top().r + 1,i,p[i]});

		else s1.push((state){1,i,p[i]});

		while(!s2.empty() && s2.top().h >= p[i])

		{

			add(root,s2.top().l,s2.top().r,s2.top().h - p[i],1,n);

			s2.pop();

		}

		if(!s2.empty())s2.push((state){s2.top().r + 1,i,p[i]});

		else s2.push((state){1,i,p[i]});

		lef[i] = query(root,1,i,i,1,n);

	}

	reset(root,1,n);

	while(!s1.empty())s1.pop();

	while(!s2.empty())s2.pop();

	for(int i = 1,j = n;i < j;++i,--j)swap(p[i],p[j]);

	for(int i = 1;i <= n;++i)add(root,i,i,i,1,n);

	for(int i = 1;i <= n;++i)

	{

		while(!s1.empty() && s1.top().h <= p[i])

		{

			add(root,s1.top().l,s1.top().r,p[i] - s1.top().h,1,n);

			s1.pop();

		}

		if(!s1.empty())s1.push((state){s1.top().r + 1,i,p[i]});

		else s1.push((state){1,i,p[i]});

		while(!s2.empty() && s2.top().h >= p[i])

		{

			add(root,s2.top().l,s2.top().r,s2.top().h - p[i],1,n);

			s2.pop();

		}

		if(!s2.empty())s2.push((state){s2.top().r + 1,i,p[i]});

		else s2.push((state){1,i,p[i]});

		rig[i] = n - query(root,1,i,i,1,n) + 1;

	}

	for(int i = 1,j = n;i < j;++i,--j)swap(rig[i],rig[j]);

	for(int i = 1;i <= n;++i)f1[i][0] = lef[i];

	for(int i = 1;i <= n;++i)f2[i][0] = rig[i];

	for(int k = 1;k <= 16;++k)

	{

		for(int i = 1;i <= n - (1 << k) + 1;++i)

		{

			f1[i][k] = min(f1[i][k - 1],f1[i + (1 << (k - 1))][k - 1]);

			f2[i][k] = max(f2[i][k - 1],f2[i + (1 << (k - 1))][k - 1]);

		}

	}

	scanf("%d",&q);

	int L,R,ansl,ansr;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&L,&R);

		int l,r,m;

		l = R;r = n;

		while(l < r)

		{

			m = ((l + r) >> 1);

			if(query1(R,m) <= L)r = m;

			else l = m + 1;

		}

		ansr = l;

		l = 1;r = L;

		while(l < r)

		{

			m = ((l + r + 1) >> 1);

			if(query2(m,L) >= R)l = m;

			else r = m - 1;

		}

		ansl = l;

		printf("%d %d\n",ansl,ansr);

	}

	return 0;

}

Solution2：

上面那个做法不好推广，我们知道解决连续段问题有一个非常有效的手段，就是利用本原连续段树。

具体建树的方法是先对于每两个相邻的位置，求出包含他们的最短的连续段，这个的求法就是从这个位置向在这两个数之间的最靠前的和最靠后的这个区间连边，这个可以用线段树优化建图，然后 $tarjan$ 之后拓扑排序 $dp$ 出每个强连通分量的左端点和右端点，然后就可以按照这个区间长度从小往大建树了，因为每个节点不可能有 $1$ 个儿子，总共 $n$ 个叶子，所以节点至多只有 $O(n)$ 个。

不过这题不用真的建树，我们求出了包含每个相邻位置的最短的连续段之后只要区间查询左端点最大值和右端点最小值就行了。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

struct edge

{

	int to,nxt;

}e[MAXN * 2 + MAXN * 30];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int p[MAXN];

struct node

{

	int lc,rc;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	if(l == r){rt = l;return;}

	rt = newnode();

	build(t[rt].lc,l,mid);add(rt,t[rt].lc);

	build(t[rt].rc,mid + 1,r);add(rt,t[rt].rc);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R){add(k,rt);return;}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int pos[MAXN];

int lef[MAXN][17],rig[MAXN][17];

int lg[MAXN];

int query_max(int f[MAXN][17],int l,int r)

{

	int len = lg[r - l + 1];

	return max(f[l][len],f[r - (1 << len) + 1][len]);

}

int query_min(int f[MAXN][17],int l,int r)

{

	int len = lg[r - l + 1];

	return min(f[l][len],f[r - (1 << len) + 1][len]);

}

int dfn[MAXN],low[MAXN],tot = 0;

int stack[MAXN],top = 0;

bool v[MAXN];

int ins[MAXN],scc = 0;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	v[k] = true;stack[++top] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] >= dfn[k])

	{

		int t;

		++scc;

		do

		{

			t = stack[top--];

			v[t] = false;

			ins[t] = scc;

		}while(t != k);

	}

	return;

}

int lbound[MAXN],rbound[MAXN];

vector<int> g[MAXN];

int ind[MAXN];

int f1[MAXN][17],f2[MAXN][17];

int main()

{

	scanf("%d",&n);

	ptr = n;

	build(root,1,n);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	for(int i = 1;i <= n;++i)pos[p[i]] = i;

	for(int i = 1;i <= n;++i)lef[i][0] = rig[i][0] = pos[i];

	for(int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

	for(int k = 1;k <= 16;++k)

	{

		for(int i = 1;i <= n - (1 << k) + 1;++i)

		{

			lef[i][k] = min(lef[i][k - 1],lef[i + (1 << (k - 1))][k - 1]);

			rig[i][k] = max(rig[i][k - 1],rig[i + (1 << (k - 1))][k - 1]);

		}

	}

	for(int i = 1;i < n;++i)

	{

		int l = query_min(lef,min(p[i],p[i + 1]),max(p[i],p[i + 1]));

		int r = query_max(rig,min(p[i],p[i + 1]),max(p[i],p[i + 1]));

		add(root,l,r - 1,i,1,n);

	}

	for(int i = 1;i <= ptr;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	memset(lbound,0x3f,sizeof(lbound));

	for(int i = 1;i <= n;++i)

	{

		lbound[ins[i]] = min(lbound[ins[i]],i);

		rbound[ins[i]] = max(rbound[ins[i]],i);

	}

	for(int k = 1;k <= ptr;++k)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(ins[k] != ins[e[i].to])

			{

				g[ins[e[i].to]].push_back(ins[k]);

				++ind[ins[k]];

			}

		}

	}

	queue<int> q;

	for(int i = 1;i <= scc;++i)

	{

		if(ind[i] == 0)q.push(i);

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

		{

			lbound[*it] = min(lbound[*it],lbound[k]);

			rbound[*it] = max(rbound[*it],rbound[k]);

			if((--ind[*it]) == 0)q.push(*it);

		}

	}

	for(int i = 1;i < n;++i)

	{

		f1[i][0] = lbound[ins[i]];

		f2[i][0] = rbound[ins[i]];

	}

	for(int k = 1;k <= 16;++k)

	{

		for(int i = 1;i <= n - (1 << k);++i)

		{

			f1[i][k] = min(f1[i][k - 1],f1[i + (1 << (k - 1))][k - 1]);

			f2[i][k] = max(f2[i][k - 1],f2[i + (1 << (k - 1))][k - 1]);

		}

	}

	int m;

	scanf("%d",&m);

	int l,r;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&l,&r);

		printf("%d %d\n",query_min(f1,l,r - 1),query_max(f2,l,r - 1) + 1);

	}

	return 0;

}