Problem. 完全参差序列
题目背景
2022年，南京师范大学迎来了 120周年校庆 ，值此120周年校庆筹备工作全面启动之际，学校诚邀海内外校友、社会贤达、各界人士壬寅中秋相聚金陵，共赴节日盛典，共商教育大计，共襄发展盛举。但是，小周学长觉得新生也是学校的重要组成，因此决定邀请大家参加校庆聚会；
然而，请来了新生，如何站位却难住了小周学长——新生的能力参差不齐，纯粹按照身高来排列又显得古板，因此小周学长想到了一种特殊的排列方式——【 分段式参差排法-完全参差序列（S-F）】：即一段连续的学生排列满足排列中的学生 综合水平值 （一个根据多方面评判的的数值） 互不相同。
小周学长想知道区间 [L, R] 之间最长 S-F 序列的长度。
输入格式
第一行两个整数 N，M。N 表示连续 N 个学生，编号为 0 到 N−1，M 表示询问的次数；
第二行 N 个整数，第 i 个数表示该学生队列第 i 个学生的 综合水平值 ai；
接下来 M 行每行两个整数 L，R，表示 小周学长 询问的区间。
输出格式
输出 M 行，每行一个整数对应询问区间内的 S-F 序列的最长长度。
数据范围
对于 50% 的数据:
-
1 ≤ N, M ≤ 1000,
-
0 ≤ L ≤ R ≤ N − 1,
-
0 ≤ ai ≤ 10^5.
对于 100% 的数据:
-
1 ≤ N, M ≤ 2 × 10^5,
-
0 ≤ L ≤ R ≤ N − 1,
-
0 ≤ ai ≤ 10^6.
时间和空间限制
2s / 64MB
题解
Tips：
本题原型为《信息学奥赛一本通》题目“与众不同”，数据规模和空间限制与原题相同，不过原题时间限制为1s，考虑到vijos评测机对python等语言的不友好，经测试：算法相同的情况下python竟然比c++慢了近10倍。因此将时间放宽到2s后依然会卡到python等语言。这我在出题前确实没考虑到，向大家陪个罪。以下是对于本题的几种解法。
解法一：
<预处理 + 二分 + ST表>
分析题目，首先我们发现可以 O(n) 预处理出 以 i 为结尾的最长完全参差序列，记 pos[val]: 上一个值为 val 的位置。
起始位置递推公式 last_i=max(last_i−1, pos(A_i)+1)
然后我们可以研究 last[ ] 的性质, 对于一个完全参差序列 i∈序列 j 来说，序列 j不一定是完全参差序列；但对于一个非完全参差序列 i∈序列 j 来说，序列 j 一定不是完全参差序列。所以最长序列对应的开始位置一定是随 i 单调不减的。
于是在查询区间[QL, QR]中 二分查找 位置 p 使得 last[p-1]<QL, last[p]>=QL。对于[QL, L)： L − QLA，对于[L, QR]： ST表 查询最大值。
时间复杂度 O(NlogN+MlogN)
解法二：
<双指针 + RMQ(ST) + 二分>
首先我们用v[i]为以下标i的元素为结尾的最长完全参差序列长度，la[i]是该序列的起始下标；然后我们可以巧妙地利用双指针把v[i]和la[i]求出来，代码如下：
for(int i=1,j=1;i<=n;i++)
{
mp[a[i]]++;
while(j<=i&&mp[a[i]]>1)
mp[a[j++]]--;
v[i]=i-j+1,la[i]=j;
}
求出v和a以后，我们对于每一次询问二分，把从左到右第一个起始位置没有超出a的完全参差序列找出来，最后用RMQ查询[l,r]之间的最大值即可。
解法三：
<dp + RMQ(线段树) + 二分>
读到这里，我们不难发现其实本题也就两个步骤：第一步预处理，第二步RMQ查询。第一步预处理有两种方法，一种是双指针（滑动窗口），一种是dp的思想；至于第二步RMQ可以用线段树和ST表来做，不过重点是预处理的部分，因为预处理的处理方式有点难想。
对于预处理，我们可以用dp来计算以a[i]为结尾的最长“完全参差序列”的长度len[i]，以及“完全参差序列”的开头的下标indx[i]，实现方式附上代码：
for (int i = 1; i <= n; ++i)
{
int x = a[i] + dif; // dif = 1e6, 用来处理负数
indx[i] = max(indx[i - 1], last[x] + 1); // last数组记录的是x最近出现的下标
len[i] = i - indx[i] + 1; // 计算len
last[x] = i; // 更新x最近出现的下标
}
然后完成代码就没什么问题了，对于区间最值我们可以用线段树来维护，当然用ST也可，最后二分即可完成。
ps - -
最后，为大家附上AC代码 - -
#include<bits/stdc++.h>标签：last,Log,题解,ll,预处理,序列,Problem,参差 From： https://www.cnblogs.com/zms396/p/16809405.html
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
//预处理部分
ll n, Q;
map<ll, ll> mp;
ll a[N], b[N], c[N];
//RMQ算法（ST表）
ll Log[N];
ll mx[22][N];
ll ask(ll l, ll r)
{
ll k = Log[r - l + 1];
return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> Q;
Log[1] = 0;
for (ll i = 2; i <= n; i++)
Log[i] = Log[i >> 1] + 1;//预处理Log
for (ll i = 1; i <= n; i++)
cin >> a[i];
//双指针
for (ll i = 1, j = 1; i <= n; i++)
{
mp[a[i]]++;
while (j <= i && mp[a[i]] > 1)
mp[a[j++]]--;
b[i] = i - j + 1;
c[i] = j;
}
//ST表
for (ll i = 1; i <= n; i++)
mx[0][i] = b[i];
ll cur = Log[n];
for (ll k = 1; k <= cur; k++)
{
for (ll i = 1; i <= n - (1 << k) + 1; i++)
{
mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
}
}
//处理询问
while (Q--)
{
ll x, y;
cin >> x >> y;
x++; y++;//偏移区间方便操作
//二分出第一个开始位置大于等于x的（假如有的话）
ll l = x, r = y;
while (l < r)
{
ll mid = (l + r) >> 1;
if (c[mid] >= x)r = mid;
else l = mid + 1;
}
//对应分类讨论
if (c[l] < x)
cout << y - x + 1 << endl;
else
cout << max((l - 1) - x + 1, ask(l, y)) << endl;
}
return 0;
}