# 题解 P1997 【faebdc的烦恼】

int build(const int &l, const int &r){
register int rt = ++ cnt ;
sum[rt] = 0 ;
if(l < r){
register int mid = (l + r) >> 1 ;
L[rt] = build(l, mid), R[rt] = build(mid + 1, r) ;
}
return rt;
}
int update(const int &last, const int &l, const int &r, const int &x){
register int rt = ++ cnt ;
sum[rt] = sum[last] + 1, R[rt] = R[last], L[rt] = L[last] ;
if (l < r){
register int mid = (l + r) >> 1 ;
if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
else  R[rt] = update(R[last], mid + 1, r, x) ;
}
return rt ;
}
int query(const int &Left,const int &Right,const int &l, const int &r, const int &k){
if (l == r) return aft[l] ;
register int mid = (l + r) >> 1, qwq ;
if (sum[Right] - sum[Left] < k) return -1 ;
int x = sum[L[Right]] - sum[L[Left]], y = sum[R[Right]] - sum[R[Left]] ;
if (x >= k)
if ((qwq = query(L[Left], L[Right], l, mid, k)) > 0) return qwq ;
if (y >= k)
if ((qwq = query(R[Left], R[Right], mid + 1, r, k)) > 0) return qwq ;
return -1 ;
}
int main(){
cin >> N >> M; for (i = 1; i <= N; i ++)  base[i] = qr() + ADD, aft[i] = base[i] ;
sort (aft + 1, aft + N + 1), Len = unique(aft + 1, aft + N + 1) - (aft + 1), T[0] = build(1, Len) ;
for (i = 1; i <= N; i ++) pos = lower_bound(aft + 1, aft + Len + 1, base[i]) - aft, T[i] = update(T[i - 1], 1, Len, pos) ;
for (i = 1; i <= M; i ++){
scanf("%d%d", &a, &b) ;
register int l = 1, r = b - a + 1, ans = 1 ;
while (l <= r){
register int mid = (l + r) >> 1 ;
if (query(T[a - 1], T[b], 1, Len, mid) > 0) ans = mid, l = mid + 1 ;
else r = mid - 1 ;
}
printf("%d\n", ans) ;
}
}

#include <cstdio>
#include <iostream>
#include <algorithm>

#define il inline
#define rr register
#define MAXN 100073

using namespace std ;
int a, b, c, pos, N, base[MAXN], mx[(MAXN << 5) + 1], mn[(MAXN << 5) + 1], aft[MAXN], M, i ;
int cnt, Len, T[(MAXN << 5) + 1], L[(MAXN << 5) + 1], R[(MAXN << 5) + 1], sum[(MAXN << 5) + 1] ;

il int qr(){
register int k = 0, f = 1 ; char c = getchar() ;
while(!isdigit(c)){ if (c == '-') f = -1 ; c = getchar() ; }
while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k * f ;
}
int update(const int &last, const int &l, const int &r, const int &x){
register int rt = ++ cnt, mid ;
sum[rt] = sum[last] + 1, R[rt] = R[last], L[rt] = L[last] ;
if (l == r){
mx[rt] = mn[rt] = sum[rt] ;
return rt ;
}
mid = (l + r) >> 1 ;
if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
else  R[rt] = update(R[last], mid + 1, r, x) ;
mn[rt] = min(mn[L[rt]], mn[R[rt]]), mx[rt] = max(mx[L[rt]], mx[R[rt]]) ;
return rt ;
}
bool query(const int &Left,const int &Right,const int &l, const int &r, const int &k){
if (l == r) return 1 ; rr int mid = (l + r) >> 1, qwq ;
if (mx[L[Right]] - mn[L[Left]] >= k && query(L[Left], L[Right], l, mid, k)) return 1 ;
if (mx[R[Right]] - mn[R[Left]] >= k && query(R[Left], R[Right], mid + 1, r, k)) return 1 ;
return 0 ;
}
int main(){
cin >> N >> M; for (i = 1; i <= N ; ++ i)  base[i] = qr() + ADD, aft[i] = base[i] ;
sort (aft + 1, aft + N + 1), Len = unique(aft + 1, aft + N + 1) - (aft + 1) ;
for (i = 1; i <= N ; ++ i) pos = lower_bound(aft + 1, aft + Len + 1, base[i]) - aft, T[i] = update(T[i - 1], 1, Len, pos) ;
for (i = 1; i <= M ; ++ i){
a = qr(), b = qr() ;
register int l = 1, mid, r = b - a + 1, ans = 1 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (query(T[a - 1], T[b], 1, Len, mid)) ans = mid, l = mid + 1 ;
else r = mid - 1 ;
}
printf("%d\n", ans) ;
}
}

2019-03-22 21:58:26 in 题解