题意：N个数，M个询问，每个询问为一个区间，求区间最长连续子序列，要求每个数都不同（perfect sequence，简称PS）。
题解：很容易求出以每个数为结尾的ps，也就是求区间的最大值。有一个不同就是长度可能会超出询问范围，所以先对PS的首位置二分，然后RMQ。注意一点，序列有可能出现负数，所以先加最大值变为正数。其实也不算变形，挺裸的……
这题卡线段树，然而我只会线段树，心塞……
代码（树状数组）：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = ; int a[N], pos[N], len[N], nt[N]; #define lowbit(x) ((x)&(-x))
int idx[N]; void init(int n)
{
for(int i=;i<=n;i++) {
idx[i] = len[i];
for(int j=;j<lowbit(i);j<<=){
idx[i]=max(idx[i],idx[i-j]);
}
}
} int query(int l, int r)
{
int ans=len[r];
while(true) {
ans=max(ans,len[r]);
if(r==l) break;
for(r-=;r-l>=lowbit(r);r-=lowbit(r)){
ans=max(ans,idx[r]);
}
}
return ans;
} int main()
{
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] += ;
}
memset(pos, , sizeof pos);
nt[] = ;
for (int i = ; i <= n; ++i) {
nt[i] = max(nt[i-], pos[a[i]]+);//nt[i]以i为结尾的最长子序列的首端
len[i] = i-nt[i]+;
pos[a[i]] = i;
}
init(n); while (m--) {
int l, r;
scanf("%d%d", &l, &r); l++, r++;
int p = upper_bound(nt+, nt++n, l) - nt;
int ans = ;
if (p > r) {
printf("%d\n", r-l+);
continue;
}
if (p > l) ans = p-l;
ans = max(ans, query(p, r));
printf("%d\n", ans);
}
}
return ;
}
代码（ST算法）：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = ; int a[N], pos[N], len[N], nt[N];
int f[N][]; void init(int n)
{
// f[i,j]表示[i,i+2^j-1]区间最大值
// f[i,j]=max(d[i,j-1], d[i+2^(j-1),j-1])
for (int i = ; i <= n; ++i) f[i][] = len[i];
for (int j = ; (<<j) <= n; ++j)
for (int i = ; i+j- <= n; ++i)
f[i][j] = max(f[i][j-], f[i+(<<j-)][j-]);
} int query(int l, int r)
{
int k = ;
while ((<<k+ <= r-l+)) ++k;
return max(f[l][k], f[r-(<<k)+][k]);
} int main()
{
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] += ;
}
memset(pos, , sizeof pos);
nt[] = ;
for (int i = ; i <= n; ++i) {
nt[i] = max(nt[i-], pos[a[i]]+);//nt[i]以i为结尾的最长子序列的首端
len[i] = i-nt[i]+;
pos[a[i]] = i;
}
init(n); while (m--) {
int l, r;
scanf("%d%d", &l, &r); l++, r++;
int p = upper_bound(nt+, nt++n, l) - nt;
int ans = ;
if (p > r) {
printf("%d\n", r-l+);
continue;
}
if (p > l) ans = p-l;
ans = max(ans, query(p, r));
printf("%d\n", ans);
}
}
return ;
}
还有一种网上流传的算法，类似kmp。想法很巧妙，但是最坏复杂度貌似是O(n^2)，不过也能A这道题。而且速度不必上面慢。数据水吧~
nt[i]记录想要字串中含有a[(i+1)-pos[i+1]]的最大位置。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = ; int a[N], pos[N], len[N], nt[N]; int main()
{
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = ; i <= n; ++i) {
scanf("%d", a+i);
a[i] += ;
}
memset(pos, , sizeof pos);
len[] = ; nt[] = ;
for (int i = ; i <= n; ++i) {
if (len[i-]+ <= i-pos[a[i]]) {
len[i] = len[i-]+;
nt[i] = nt[i-];
} else {
len[i] = i-pos[a[i]];
nt[i] = i-;
}
pos[ a[i] ] = i;
//printf("%d %d %d\n", len[i], nt[i], pos[a[i]]);
}
while (m--) {
int l, r;
scanf("%d%d", &l, &r); l++, r++;
int res = len[r];
if (res >= r-l+) {
printf("%d\n", r-l+);
continue;
}
while (nt[r] > ) {
r = nt[r];
res = max(res, min(len[r], r-l+));
if (res >= r-l+) {
break;
}
}
printf("%d\n", res);
}
}
return ;
}