【gzoj3646】Frequent values【RMQ】

分析

一开始我居然没看到“不下降”三个大字，导致一直卡住不知道怎么做。

如果不下降，那么相等的都是挤在一起的，所以我们把所有相等段的长度都预处理出来，具体地，就是把当前数字是相等段的第几个给求出来，成为一个数组。例如样例，我们处理出一个数组：

1 2 1 2 3 4 1 1 2 3
1

这样子我们就可以用区间最值来做了！

但是如果是这样：6 1 2 3 1 2。最值是6，答案是3，怎么处理呢？

发现如果在区间中出现了一个1，那么后面的就都是完整的段（只可能被去尾），直接可以用最值统计的，但是前面的一小段不行。所以预处理出一个数组last，存这个数字所在连续段的结尾，样例处理：

2 2 6 6 6 6 7 10 10 10
1

这样子就可以快速找到查询区间 [l,r] 中离 $l$ 最近的一个1，所以只需要对 $[last[l]+1,r]$ 这段区间做RMQ（这个实现很简单），然后与前面被“掐头”的一段长度 $last[l]+1-l+1$ 比较，求出最值即可。

特判：如果整个区间就是一个被“掐头”的区间：比如：2 3 4 5 6。那就直接输出 $r-l+1$。

上代码

cin什么东西啊又TLE
吐槽输入

#include
#include
#include
#include
using namespace std;

int n,q,b[100010],a[100010];
int lg[100010],f[100010][23],last[100010];

int main()
{
	while(1)
	{
		scanf("%d",&n); if(n==0) break;
		scanf("%d",&q);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			if(b[i]==b[i-1]) a[i]=a[i-1]+1;
			else a[i]=1;
			f[i][0]=a[i];
		}
		last[n]=n;
		for(int i=n-1;i>=1;i--)
		{
			if(a[i+1]==1) last[i]=i;
			else last[i]=last[i+1];
		}
		lg[1]=0;
		for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
		for(int j=1;j<=lg[n];j++)
		{
			for(int i=1;i+(1<<j)-1<=n;i++)
			{
				f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			}
		}
		while(q--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			if(last[l]>=r)//判断是不是连续一整段的 
			{
				cout<<r-l+1<<endl;
				continue;
			}
			int k=lg[r-(last[l]+1)+1];
			cout<<max(last[l]-l+1,max(f[last[l]+1][k],f[r-(1<<k)+1][k]))<<endl;
		}
		memset(f,0,sizeof(f));
		memset(last,0,sizeof(last));
		memset(a,0,sizeof(a));
	} 
	
	return 0;
} 
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