[ 2018 Multi-University Training Contest 1 ] [ HDU6305 ] H RMQ Similar Sequence

        题意：定义一个数列A的\(RMQ(A,l,r)\)为使得\(a_i\)为\(a_l,a_{l+1},a_{l+2}, \cdots ,a_r\)中最大数的最小的i。

        对于两个数列A与B，定义它们RMQ相似当且仅当两数列元素个数相等且对于所有的\(1 \leq l \leq r \leq n\)，有\( RMQ(A,l,r)=RMQ(b,l,r)\)。

        现在给你一个正整数数列\(\{a_i\}\)，其中\(1 \leq a_i \leq n\)，对于实数数列\(\{b_i\}\)，其中\(b_i\)为\([0...1]\)中随机的一个实数，当数列A与B  RMQ相似时，B的权值为\(\sum{b_i}\)，否则为0,求B权值的期望。（答案对\(10^9 + 7\)取模）（\(1 \leq n \leq 10^6\)）

        题解：首先要观察两个序列RMQ相似的条件。当数列A是一个1..n的全排列时，两个序列RMQ相似当且仅当B中元素的大小顺序和A相同。此时答案为\(\frac{n}{2} \cdot \frac{1}{n!}\)（其中\(\frac{n}{2}\)表示的是B中元素之和的期望，\(\frac{1}{n!}\)表示的是B中元素大小顺序满足条件的概率）。

        问题主要是在于当A中含有相同元素的时候的答案。由于不同的A的全排列所对应的满足条件的B是互不相交的（元素间大小关系不同），所以我们要求出与A  RMQ相似的n排列的个数，答案就是这个乘上上面所说的一个排列所对应的答案。接下来找符合条件的全排列（记为C）的个数。

        考虑A的一个区间\([l..r]\)，设\(m=RMQ(A,l,r)\)，那么我构造的\(c_m\)一定是C中该区间中的最大值，\(c_m\)的值可以确定下来。可以发现，当取任意的\(l \leq l_0 \leq m\)与\(m \leq r_0 \leq r\)的时候，\(RMQ(C,l_0,r_0)=RMQ(A,l_0,r_0)\)肯定是等于m的，也就是说此时m左右两边的数无论大小关系如何都互不影响，那么我们可以任意分配\(m-l\)个数给左边的区间，\(r-m\)个数给右边的区间，方案数为\(C_{r-l}^{m-l}\)，然后递归处理左右两个区间，最后再乘上两个区间的答案就好了。

        由于n有\(10^6\)，直接DFS会爆栈。不过BFS写也不麻烦。求区间RMQ我直接用线段树来写了（ST表被卡内存），1200ms勉强还是跑过去了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,mo=1e9+7;

struct Segment_Tree
{
	int v[maxn];
	int maxpos[maxn<<2];
	int n;

	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)

	int GetMaxpos(int a,int b)
	{
		if (v[a]==v[b]) return a;
		else if (v[a]>v[b]) return a;
		else return b;
	}

	void BuildTree(int o,int l,int r,int *a)
	{
		if (l==r)
		{
			maxpos[o]=l;
			v[l]=a[l];
			return;
		}
		BuildTree(ls,l,mid,a);
		BuildTree(rs,mid+1,r,a);
		maxpos[o]=GetMaxpos(maxpos[ls],maxpos[rs]);
	}

	int Query(int o,int l,int r,int a,int b)
	{
		if (a<=l && r<=b) return maxpos[o];
		int res=a;
		if (a<=mid) res=GetMaxpos(res,Query(ls,l,mid,a,b));
		if (b> mid) res=GetMaxpos(res,Query(rs,mid+1,r,a,b));
		return res;
	}

	int Query(int l,int r) {return Query(1,1,n,l,r);}
	void Build_Tree(int _n,int *a) {n=_n;BuildTree(1,1,_n,a);}

#undef ls
#undef rs
#undef mid
}T;

long long p[maxn];
long long inv[maxn],invp[maxn];
int a[maxn];
int n;

long long C(int a,int b)
{
	return (p[a]*invp[b]%mo)*invp[a-b]%mo;
}

void Init()
{
	p[0]=1;
	inv[1]=inv[0]=invp[0]=invp[1]=1;
	for (int i=1;i<=1000000;i++) p[i]=p[i-1]*i%mo;
	for (int i=2;i<=1000000;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo,invp[i]=invp[i-1]*inv[i]%mo;
}

int L[maxn],R[maxn];

long long Solve()
{
	long long res=1;
	int tot=1;
	L[1]=1,R[1]=n;
	for (int i=1;i<=n;i++)
	{
		int l=L[i],r=R[i];
		if (l==r) continue;
		int x=T.Query(l,r);
		res=(res*C(r-l,x-l))%mo;
		if (l<=x-1) L[++tot]=l,R[tot]=x-1;
		if (x+1<=r) L[++tot]=x+1,R[tot]=r;
	}
	return res;
}

int main()
{
	Init();
	int Case;
	scanf("%d",&Case);
	while (Case--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		T.Build_Tree(n,a);
		printf("%lld\n",(Solve()*invp[n-1]%mo)*inv[2]%mo);
	}
	return 0;
}

        有笛卡尔树做的\(O(n)\)的RMQ，不过建树没看懂，晚些再补。