网站大部分都是jsp做的,网站推广常用的方法,求个网站或者app,计算机网站建设与管理是什么意思题目描述 A 是某公司的 CEO#xff0c;每个月都会有员工把公司的盈利数据送给 A#xff0c;A 是个与众不同的怪人#xff0c;A 不注重盈利还是亏本#xff0c;而是喜欢研究「完美序列」#xff1a;一段连续的序列满足序列中的数互不相同。 A 想知道区间 [L,R] 之间最长的完… 题目描述 A 是某公司的 CEO每个月都会有员工把公司的盈利数据送给 AA 是个与众不同的怪人A 不注重盈利还是亏本而是喜欢研究「完美序列」一段连续的序列满足序列中的数互不相同。 A 想知道区间 [L,R] 之间最长的完美序列长度。 输入格式 第一行两个整数 N,MN 表示连续 N 个月编号为 0 到 N−1M 表示询问的次数 第二行 N 个整数第 i 个数表示该公司第 i 个月的盈利值 ai 接下来 M 行每行两个整数 L,R表示 A 询问的区间。 输出格式 输出 M 行每行一个整数对应询问区间内的完美序列的最长长度。 样例 样例输入 9 2
2 5 4 1 2 3 6 2 4
0 8
2 6 样例输出 6
5 数据范围与提示 对于全部数据1≤N,M≤2×10^5,0≤L≤R≤N−1,∣ai∣≤10^6。 ___________________________________________________________________________________________ 很神奇的题目动态规划RMQ last[i]表示数列中第i个数上一次出现的位置因为可能出现负数所以要加上maxa。 st[i]表示数列中第i个数为结尾的完美数量的开始位置。 f[i]表示数列中第i个数为结尾的完美序列的长度。 所以st[i]max(st[i-1],last[i]1) 而f[i]i-st[i]1 那么,[l,r]区间内的最长完美序列的长度怎么求呢 l到r的区间可以分成两部分左边的部分他们的st[]不再区间内也就是小于l右边的部分可能在区间内也就是大于等于l。 左边的部分的最大长度当然就是左右部分的边界减去l二右边的部分则需要查找啊最大值就用动力RMQ. ___________________________________________________________________________________________ 1 #includebits/stdc.h2 using namespace std;3 const int maxn2e510;4 const int maxa1e610;5 int last[maxa1],st[maxn],f[maxn][20];6 int n,m;7 int _log[maxn];8 int query(int l,int r)9 {
10 if(lr)return -10000000;
11 int lg_log[r-l1];
12 return max(f[l][lg],f[r-(1lg)1][lg]);
13 }
14 int main()
15 {
16 scanf(%d%d,n,m);
17 _log[0]-1;
18 for(int x,i1;in;i)
19 {
20 _log[i]_log[i1]1;
21 scanf(%d,x);
22 st[i]max(st[i-1],last[xmaxa]1);
23 f[i][0]i-st[i]1;
24 last[xmaxa]i;
25 }
26 for(int j1;j20;j)
27 for(int i1;i(1j)-1n;i)
28 f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);
29 int l,r;
30 while(m--)
31 {
32 scanf(%d%d,l,r);
33 l,r;
34 int tplower_bound(stl,str1,l)-(stl);
35 int tppquery(tpl1,r);
36 printf(%d\n,max(tp,tpp));
37 }
38 return 0;
39 } View Code 转载于:https://www.cnblogs.com/gryzy/p/10302202.html
