[ 2018 Multi-University Training Contest 1 ] [ HDU6299 ] B Balanced Sequence
[ 2018 Multi-University Training Contest 1 ] [ HDU6304 ] G Chiaki Sequence Revisited

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

Zarxdy34 posted @ 2018年7月24日 17:14 in HDU with tags 线段树 rmq , 509 阅读

        题意:定义一个数列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,不过建树没看懂,晚些再补。

Avatar_small
NCERT Geography Ques 说:
2022年9月29日 14:20

Geography helps the students on understanding the basic physical systems that affect everyday life. NCERT Geography Question Paper Class 9 Geography is the study of the Internal and external characteristics of the Earth and its atmosphere, and of human activity as it affects and is affected by these, including the distribution of populations and resources, land use, and industries.Geography helps the students on understanding the basic physical systems that affect everyday life.Geography helps the students on understanding the basic physical systems that affect everyday life.Geography helps the students on understanding the basic physical systems that affect everyday life.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter