题目描述
「完美序列」：一段连续的序列满足序列中的数互不相同。A 想知道区间L，R之间最长的完美序列长度。
样例输入
9 2
2 5 4 1 2 3 6 2 4
0 8
2 6
样例输出
6
5
思路:
先考虑一下怎么处理这个不重复的问题
我们用last[i]记录i这个数字上次出现的位置,st[i]表示以第i个数为结尾最长完美序列的起始位置。
那么很容易得到st[i]的转移方式: st[i]= max (st[i −1] ,last[i] + 1)
同时也可以得到这段序列的长度:f[i]=i-st[i]+1 (f[i]表示以第i个数为结尾的最长完美序列的长度)
我们再考虑如何求答案
我们有f[i][0]表示：结尾位置在i时，最长完美序列的长度；
我们有f[i][1]表示：结尾位置在i、i+1这2种情况中，最长完美序列的长度的最大值；
我们有f[i][2]表示：结尾位置在i、i+1，i+2，i+3 这4种情况中，最长完美序列的长度的最大值；
……
可求出以任意区间中的位置为结尾的最长完美序列的最大值。RMQ。
但是本题要求的是任意区间的完美序列的最大长度L1，并不是以任意区间中的位置为结尾的最长完美序列的最大长度L2。
观察区间【5，9】：
【5，9】中的数是{2，3，6，2，4} 最长完美序列是{3，6，2，4}，答案长度是4。
而{f[5],f[6],f[7],f[8],f[9]}的最大值f[7]=6。原因是以位置7结尾的完美序列的起始位置st[7]=2，2不在区间【5，9】内。
以5，6，7位置结尾的最长完美序列的起点都不在区间【5，9】内（st[5]=2,st[6]=2,st[7]=2）,这也说明5，6，7位置上的数是不同的。
以8，9 位置结尾的最长完美序列的起点都在区间 【5，9】内（st[8]=6,st[9]=6）,ans2=rmq(8,9)。
这样【5，9】区间被分成两段了，【5，7】和【8，9】
前一段【5，7】中有最长完美序列的长度是ans1=7-5+1=3
后一段【8，9】以8，9位置结尾的最长完美序列的长度是ans2=rmq(8,9)=4
最终ans=max(ans1,ans2)=4
那么现在的关键就是找到前后两段的分界点now。
ans1=now-L+1
ans2=rmq(now+1,R)
最终ans=max(ans1,ans2)
如何求分界点now，st[]是个不下降的序列，所以可以二分解决。
#include <bits/stdc++.h> using namespace std; #define re register #define LL long long inline int read() { int f = 1, lzx = 0; char c = getchar(); while ((c > '9') || (c < '0')) { if (c == '-') f = -f; c = getchar(); } while (c <= '9' && c >= '0') { lzx = lzx * 10 + c - '0'; c = getchar(); } return lzx * f; } //快读 const int MaxN = 2e5 + 10; const int MaxM = 1e6 + 10; int last[2 * MaxM], a[MaxN], f[MaxN][55]; int pre[2 * MaxM], Log[MaxN]; int n, m; int find(int l, int r) { int x = l; int ans = l - 1; while (l <= r) { int mid = (l + r) / 2; if (pre[mid] < x) l = mid + 1, ans = mid; else r = mid - 1; } return ans; } //二分寻找分界点 int ask(int l, int r) { int k = Log[r - l + 1]; return max(f[l][k], f[r - (1 << k) + 1][k]); } //求最大的f int main() { scanf("%d%d", &n, &m); Log[0] = -1; for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1; //预处理log for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); pre[i] = max(pre[i - 1], last[a[i] + MaxM] + 1);//a[i]可能为负数，所以偏移MaxM f[i][0] = i - pre[i] + 1; last[a[i] + MaxM] = i; } //求出f和pre for (int j = 1; j <= Log[n]; ++j) for (int i = 1; i <= n; ++i) { if (i + (1 << (j - 1)) > n) f[i][j] = f[i][j - 1]; else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); // ST表 } for (int i = 1; i <= m; ++i) { int l, r; scanf("%d%d", &l, &r); l++, r++; int now = find(l, r), anss = now - l + 1; if (now < r) printf("%d\n", max(now - l + 1, ask(now + 1, r))); else printf("%d\n", anss); } return 0; }