传送门：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）
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #define REP(i, s, n) for(int i = s; i <= n; i ++) 7 #define RAP(i, n, s) for(int i = n; i >= s; i --) 8 using namespace std; 9 const int maxn = 200000 + 10; 10 const int maxhash = 871199; 11 int n, Q, d[maxn][20], Log[maxn], dp[maxn], A[maxn], last[maxn]; 12 namespace HASH{ 13 int fch[maxhash], next[maxn], val[maxn], ms = 0; 14 void hash_init() { memset(fch, -1, sizeof(fch)); } 15 int find_insert(int v){ 16 int id = v % maxhash; 17 if(id < 0) id += maxhash; 18 for(int i = fch[id]; i != -1; i = next[i]) if(val[i] == v) return i; 19 next[ms] = fch[id]; val[ms] = v; return fch[id] = ms ++; 20 } 21 }using namespace HASH; 22 void RMQ(){ 23 Log[0] = -1; REP(i, 1, n) d[i][0] = i - dp[i] + 1, Log[i] = Log[i >> 1] + 1;//此循环节开始计数了 24 for(int j = 1; (1 << j) <= n; j ++) 25 for(int i = 1; i + (1 << j) - 1 <= n; i ++) 26 d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]); 27 return ; 28 } 29 inline void read(int &x){ 30 x = 0; int sig = 1; char ch = getchar(); 31 while(!isdigit(ch)) { if(ch == '-') sig = -1; ch = getchar(); } 32 while(isdigit(ch)) x = 10 * x + ch - '0', ch = getchar(); 33 x *= sig; return ; 34 } 35 inline void write(int x){ 36 int len = 0, buf[10]; 37 while(x) buf[++ len] = x % 10, x /= 10; 38 for(int i = len; i; i --) putchar(buf[i] + '0'); 39 putchar(' '); return ; 40 } 41 void init(){ 42 hash_init(); 43 read(n); read(Q); 44 REP(i, 1, n) read(A[i]), A[i] = find_insert(A[i]), dp[i] = max(dp[i - 1], last[A[i]] + 1), last[A[i]] = i; 45 //更新循环节的尾巴，转移十分的机智啊我都想骂人了。最后别忘了更新自己的位置 (⊙ ▽ ⊙) 46 RMQ(); 47 return ; 48 } 49 int query(int L, int R) { 50 int k = Log[R - L + 1]; 51 return max(d[L][k], d[R - (1 << k) + 1][k]); 52 } 53 void work(){ 54 int ql, qr; 55 while(Q --){ 56 read(ql); read(qr); 57 int L = ql, R = qr + 1, M; 58 while(L + 1 < R){ //这二分什么鬼？ε=ε=ε=┏(゜ロ゜;)┛ 59 M = L + R >> 1; 60 if(dp[M] < ql) L = M;//二分找循环节 61 else R = M ;//二分写错了？TAT 62 } 63 print(max(L - ql + 1, query(L + 1, qr)));//拆成两段，此循环节的前段和上一个循环节的后一段（ˉ﹃ˉ） 64 } 65 return ; 66 } 67 void print(){ 68 69 return ; 70 } 71 int main(){ 72 init(); 73 work(); 74 print(); 75 return 0; 76 }