【日常小测】小Y

  • 题目来源：湖南省队集训Day2T1
  • 本文为博主原创，未经许可不得转载

分析：

首先考虑如何计算答案：把左区间视为左括号，右区间视为右括号，设$x_i$表示第$i$个右括号左边左括号的数量

那么答案就是$\sum_{i=1}^{S}(x_i-i+1)$ （仔细考虑为什么

然后我们发现如果有一段连续的右括号，那么这些右括号的x值是相同的，可以一起计算

所以我们对这样一段连续的右括号一起计算贡献，复杂度为$O(n \sqrt n)$ （仔细思考为何是$\sqrt n$

接下来考虑如何找到连续右括号的最右端（不再详述了，看代码就能理解

代码中的find()函数是找第k小，calc()函数是找比v小的数的个数

总的复杂度$O(n \sqrt n \log n)$，虽然n到了1e5，但是跑得飞快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 200100
using namespace std;
const int mod=1e9+7;
int n,m,cnt,fac[MAXN],inv[MAXN],root[MAXN<<4],sum[MAXN<<4],son[MAXN<<4][2];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int pow(int a,int b){
	int ret=1;
	while(b){
		if(b&1) ret=mul(ret,a);
		a=mul(a,a); b>>=1;
	}
	return ret;
}
void pre(){
	int N=100000;  fac[0]=1;
	for(int i=1;i<=N;++i) fac[i]=mul(fac[i-1],i);
	inv[N]=pow(fac[N],mod-2);
	for(int i=N-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1);
}
int newnode(int last){
	++cnt;
	son[cnt][0]=son[last][0];
	son[cnt][1]=son[last][1];
	sum[cnt]=sum[last]+1;
	return cnt;
}
void build(int &root,int last,int l,int r,int v){
	root=newnode(last);
	if(l==r)  return;
	int mid=(l+r)>>1;
	if(v<=mid) build(son[root][0],son[last][0],l,mid,v);
	else build(son[root][1],son[last][1],mid+1,r,v);
}
int find(int rootL,int rootR,int l,int r,int k){
	if(l==r)  return l;
	int mid=(l+r)>>1,temp=sum[son[rootR][0]]-sum[son[rootL][0]];
	if(k<=temp) return find(son[rootL][0],son[rootR][0],l,mid,k);
	else return find(son[rootL][1],son[rootR][1],mid+1,r,k-temp);
}
int calc(int rootL,int rootR,int l,int r,int v){
	if(l==r) return sum[rootR]-sum[rootL];
	int mid=(l+r)>>1;
	if(v<=mid) return calc(son[rootL][0],son[rootR][0],l,mid,v);
	else return sum[son[rootR][0]]-sum[son[rootL][0]]+calc(son[rootL][1],son[rootR][1],mid+1,r,v);
}
void clear(){
	cnt=0;
	memset(sum,0,sizeof(sum));
	memset(son,0,sizeof(son));
	memset(root,0,sizeof(root));
}
void solve(){
	n=read();  m=read();  clear();
	for(int i=1;i<=n;++i) build(root[i],root[i-1],1,n,read());
	for(int i=1;i<=m;++i){
		int l1=read(),r1=read(),l2=read(),r2=read(),S=r1-l1+1,ans=1;
		for(int k=1,last=0;k<=S;k=last+1){
			int I=find(root[l2-1],root[r2],1,n,k);
			int x=calc(root[l1-1],root[r1],1,n,I);
			int J=find(root[l1-1],root[r1],1,n,x+1);
			last =calc(root[l2-1],root[r2],1,n,J);
			ans=mul(ans,mul(fac[x-k+1],inv[x-last]));
		}
		printf("%d\n",ans);
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	pre(); for(int T=read();T;--T) solve();
	return 0;
}

本文标题:【日常小测】小Y

文章作者:chty

发布时间:2017年07月08日 - 20时55分

最后更新:2018年07月25日 - 21时30分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,