题解 P1997 【faebdc的烦恼】
皎月半洒花
2019-03-22 21:58:26
这是一篇主席树的题解。
我们思考主席树的本质，其实就是可以刨出一个区间$l,r$让我们可以在树高复杂度$log$的基础上进行一波常规线段树不能进行的、权值查找操作。那么由于主席树本质上是一棵权值线段树，所以直接$return$的$val$一定是最小的（只要我们保证先查找左子树）。
以上是老生常谈，~~是我从自己以前整理过的笔记扒拉出来的~~。
而对于这道题，我们考虑二分。为什么满足二分的性质呢？比较显然的是，如果我们通过查找出现次数为$k$的数，发现访问的值为`NULL`，那么对于任何$k+x(x \in \mathbb{N})$，访问的$val$都将会是`NULL`。
那么我们就可以二分实现(这份代码有$81pts~with$ `TLE*2`)
```cpp
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) ;
}
}
```
但事实上，我们认知中的主席树上二分的复杂度应该是$\Theta(q \log ^2n)$，其中一个$\log$用来二分，一个$\log$用来查找。但事实上我们这么写，其复杂度并不是对的。因为我们为了防止漏掉可行解，每次需要查询两棵子树，而查询两棵子树的复杂度，最坏情况下却是单次$\Theta(2^n)$的。那么复杂度就会完全爆炸，以至于最后我不得不写两个$subtask$用暴力去$AC$（事实上，这种情况下的主席树是没有暴力快的）。
换句话说，这复杂度特么根本不对……
那么接下来是一个剪枝，由巨佬[乖≮闹√€](https://www.luogu.org/space/show?uid=70863)提出，并且时间效率十分的高。
大体思路就是，考虑对于主席树上的每一个点维护一个$max$一个$min$，记录区间内**单个数值出现的最大次数和最小次数**，那么我们在$check$的时候就可以直接用这种方式判——如果$r$版本的主席树内出现的最大次数减去$l-1$版本内出现的数的最小次数$k<q$（$q$是二分出的$val$），那么一定不满足。
事实上，这种剪枝并不是最优性剪枝，但是通过此题足矣：
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#define il inline
#define ADD 393216
#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) ;
}
}
```
最后是_rqy提的$hack$思路：
