http://www.spoj.com/problems/LPERMUT/
Brief description:
給出一個序列，求最大的 mx，使得存在一個長度為 mx 的連續子序列，使其恰好為 1..mx 的一個排列。
Analysis:
好題。。。Vijos1381 數據太弱，正解應是 O(n) 。
盡量避免使用數據結構。。。我們需要充分利用排列的性質。。。
區間 [l, r] 恰好是 1..len （len = r-l+1）的排列的充分必要條件是：
- [l, r] 區間的數兩兩不同。
- s[r]-s[l+1] = 1+2+…+len。。。
為了確保區間中的數字兩兩不同。。。我們設 l[i] 為 i 向左最長可以延伸的距離。。（邊界設 l[0] = 0, l[n+1] = n+1。。）
。。那麼有 l[i] = max(l[i], p[a[i]]+1)。。。（p[a[i]] 是上一個 a[i] 的位置。。。（也可以用 two point 得到這個東西。。。。
void upd(int l, int r, int len){
if (len < ans) return;
if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}
。序列被 1 分割成了一些小的區間。。（不能包含兩個相同的 1。。。）。。
____ 1 ____ 1 _________ 1 _____
我們枚舉每個 1.。。討論區間中最大的數字 mx 出現在 1 的左邊還是右邊。。對稱處理。。
。。考慮左邊。。
for (int j=i-1,mx=1;l[i]<=j;--j){
checkMax(mx, a[j]);
upd(j,j+mx-1,mx);
}
由於 upd() 過程是 O(1) 的。。所以整個演算法是 O(n) 的。。。
//}/* .................................................................................................................................. */
const int N = int(1e5) + 9;
int a[N], s[N], l[N], p[N], n, ans;
void upd(int l, int r, int len){
if (len < ans) return;
if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
REP_1_C(i, RD(n)) s[i] = s[i-1] + RD(a[i]);
RST(p); l[0] = 0; REP_1(i, n){
l[i] = max(l[i-1], p[a[i]]+1); p[a[i]] = i;
//cout << l[i] << " ";
}
l[n+1] = n+1;
//puts("");
REP_1(i, n) if (a[i] == 1){
upd(i, i, 1);
for (int j=i-1,mx=1;l[i]<=j;--j){
checkMax(mx, a[j]);
upd(j,j+mx-1,mx);
}
for (int j=i+1,mx=1;l[j]<=i;++j){
checkMax(mx, a[j]);
upd(j-mx+1,j,mx);
}
}
OT(ans);
}
