[COJ0985]WZJ的数据结构（负十五）
试题描述
CHX有一个问题想问问大家。给你一个长度为N的数列A,请你找到两个位置L,R,使得A[L]、A[L+1]、……、A[R]中没有重复的数，输出R-L+1的最大值。
以上是附中联赛加试的一道题。WZJ觉得这道题太水了，改了改题目：
WZJ有一个问题想问问大家。给你一个长度为N的数列A,你要回答M次问题。每次问题给你两个正整数ql,qr。请你找到两个位置L、R (ql<=L<=R<=qr)，使得A[L]、A[L+1]、……、A[R]中没有重复的数，输出R-L+1的最大值。
介于某些人的吐槽，本题不强制在线。注意范围，祝你好运！
输入
输入第一行为两个正整数N，M。
输入第二行为N个整数Ai。
接下来M行每行两个正整数ql,qr。
输出
对于每个问题，输出R-L+1的最大值。
输入示例
输出示例
数据规模及约定
1<=N<=200000
1<=M<=500000
1<=ql,qr<=N
-10^9<=Ai<=10^9
题解
找出所有数上一次出现在哪（即对于一个数 A[i]，找到一个最大的 pos 使得 A[pos] = A[i] 且 pos < i），然后计算出 f[i] 表示区间 [f[i], i] 没有重复元素，且使得 f[i] 尽量小。那么我们对于每个位置记录 i - f[i] + 1，即最长区间长度，那么对于询问 [ql, qr]，找到 [ql, k] 没有重复元素且 k ≤ qr 的这个 k，然后 k 右边部分求一个最大值，左边直接减。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 200010
#define maxlog 20
int n, q, A[maxn], num[maxn], lp[maxn], f[maxn]; int Log[maxn], mx[maxlog][maxn];
void init() {
Log[1] = 0;
for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1;
for(int i = 1; i <= n; i++) mx[0][i] = i - f[i] + 1;
for(int j = 1; j < maxlog; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
mx[j][i] = max(mx[j-1][i], mx[j-1][i+(1<<j-1)]);
return ;
}
int query(int l, int r) {
if(l > r) return -1;
int len = r - l + 1, t = Log[len];
return max(mx[t][l], mx[t][r-(1<<t)+1]);
} int main() {
n = read(); q = read();
for(int i = 1; i <= n; i++) num[i] = A[i] = read(); sort(num + 1, num + n + 1);
for(int i = 1; i <= n; i++) {
A[i] = lower_bound(num + 1, num + n + 1, A[i]) - num;
f[i] = max(f[i-1], lp[A[i]] + 1);
lp[A[i]] = i;
}
init(); while(q--) {
int ql = read(), qr = read();
int k = upper_bound(f + 1, f + n + 1, ql) - f - 1;
k = min(k, qr);
printf("%d\n", max(k - ql + 1, query(k+1, qr)));
} return 0;
}