传送门：http://oj.cnuschool.org.cn/oj/home/addSolution.htm?problemID=955
试题描述：
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的最大值。
输入示例：
5 3
1 2 1 3 4
1 3
2 4
2 5
输出示例：
2
3
4
其他说明：
1<=N<=200000
1<=M<=500000
1<=ql,qr<=N
-10^9<=Ai<=10^9
题解（幸好没有强制在线呀(⊙ ▽ ⊙)）分治分成DP+RMQ。
我们先搞定最长不同数区间，每次来限制了就会把它砍断，对于右边的“此区间”我们预处理循环节计数再用RMQ搞定最大值，对于左区间我们二分找到编号，然后直接用L-ql出区间（这个区间一定没有重复数辣o(*￣3￣)o）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define REP(i, s, n) for(int i = s; i <= n; i ++)
#define RAP(i, n, s) for(int i = n; i >= s; i --)
using namespace std;
const int maxn = + ;
const int maxhash = ;
int n, Q, d[maxn][], Log[maxn], dp[maxn], A[maxn], last[maxn];
namespace HASH{
int fch[maxhash], next[maxn], val[maxn], ms = ;
void hash_init() { memset(fch, -, sizeof(fch)); }
int find_insert(int v){
int id = v % maxhash;
if(id < ) id += maxhash;
for(int i = fch[id]; i != -; i = next[i]) if(val[i] == v) return i;
next[ms] = fch[id]; val[ms] = v; return fch[id] = ms ++;
}
}using namespace HASH;
void RMQ(){
Log[] = -; REP(i, , n) d[i][] = i - dp[i] + , Log[i] = Log[i >> ] + ;//此循环节开始计数了
for(int j = ; ( << j) <= n; j ++)
for(int i = ; i + ( << j) - <= n; i ++)
d[i][j] = max(d[i][j - ], d[i + ( << (j - ))][j - ]);
return ;
}
inline void read(int &x){
x = ; int sig = ; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') sig = -; ch = getchar(); }
while(isdigit(ch)) x = * x + ch - '', ch = getchar();
x *= sig; return ;
}
inline void write(int x){
int len = , buf[];
while(x) buf[++ len] = x % , x /= ;
for(int i = len; i; i --) putchar(buf[i] + '');
putchar('\n'); return ;
}
void init(){
hash_init();
read(n); read(Q);
REP(i, , n) read(A[i]), A[i] = find_insert(A[i]), dp[i] = max(dp[i - ], last[A[i]] + ), last[A[i]] = i;
//更新循环节的尾巴，转移十分的机智啊我都想骂人了。最后别忘了更新自己的位置 (⊙ ▽ ⊙)
RMQ();
return ;
}
int query(int L, int R) {
int k = Log[R - L + ];
return max(d[L][k], d[R - ( << k) + ][k]);
}
void work(){
int ql, qr;
while(Q --){
read(ql); read(qr);
int L = ql, R = qr + , M;
while(L + < R){ //这二分什么鬼？ε=ε=ε=┏(゜ロ゜;)┛
M = L + R >> ;
if(dp[M] < ql) L = M;//二分找循环节
else R = M ;//二分写错了？TAT
}
print(max(L - ql + , query(L + , qr)));//拆成两段，此循环节的前段和上一个循环节的后一段（ˉ﹃ˉ）
}
return ;
}
void print(){ return ;
}
int main(){
init();
work();
print();
return ;
}