主席树上的不靠谱解法

$\rm{0x00~}Preface$

某天机房里,公认的ezi lwy跟wxl随口说了一道luogu上的题,wxl来了兴趣,被pks听见了,于是pks就瞅了一眼这题,然后说了一句”这不就是sb主席树上二分吗?随便一个$\Theta(n \log^2n)$就可以过啊”

然后pks那一整个晚上都在搞这个假算法,$\rm{QAQ}$

于是就有了本文,整理了两道主席树的正确(?)应用。

$\rm{0x01~}$faebdc的烦恼

传送门:https://www.luogu.org/problemnew/show/P1997

呃,其实这不是一道很难的题。因为本来就保证了数列不降,所以我们直接记录一下每个数出现区间的左右端点,瞎搞就好。但是既然我说了要主席树上二分,就一定要写写看吧qaq

我们考虑在我的这篇博客里面曾经介绍过的$T3$中的算法,我们直接去查询左右儿子值域区间内中数的个数,看看哪个可行,然后暴力找就好。

但是…他TLE了两个点,因为我是这么写的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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) ;
}
}

好像很正常?但是,这个复杂度是完全错误的。最大的时候甚至可以到达单次$m \log n$的复杂度——注意是单次。因为我们每次询问的时候,如果查询了左区间不合法,那么不代表右区间合法——毕竟是二分里的check环节。而上一个类似方法的题,可以保证我们如果左区间的数的出现次数不超过$\frac{1}{2}$,那么右区间一定满足——但显然的是,本题不具有这个性质。

所以,总结一下,主席树上不可以二分。

但是如果我们加一点剪枝呢?

我们考虑,对于主席树上的每一个点维护一个$maxx$一个$minx$,记录区间内单个数值出现的最大次数和最小次数,那么我们在$check$的时候就可以直接用这种方式判——如果$r$版本的主席树内出现的最大次数减去$l-1$版本内出现的数的最小次数$k<q$($q$是二分出的$val$),那么一定不满足。

比较显然的是,这不是一种最优性剪枝,而是一种可行性剪枝。但是对付这道题却有着不错的效果,跑的奇快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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) ;
}
}

$\rm{0x02~}CF840D~Destiny$

传送门:http://codeforces.com/problemset/problem/840/D

简化版题意:每次给出三个参数$l,r,k$,询问区间$[l,r]$内是否存在出现次数严格大于$\frac{r-l+1}{k}$的数。如果存在就输出最小的那个$ans$,否则输出$-1$.

这个东西……就直接查询就好了啊……由于不用二分,所以复杂度相对来说稳定了一些。于是我就没有加上文中提到过的那个诡异的优化。我们每次先查左半边,就可以保证在值域上最小,也就是说每次我们都可以求出最小的合法$ans$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
il int build(int l, int r){
int rt = ++ cnt ;
sum[rt] = 0 ;
if(l < r){
L[rt] = build(l, mid) ;
R[rt] = build(mid + 1, r) ;
}
return rt;
}
il int update(int last, int l, int r, int x){
int rt = ++ cnt ;
sum[rt] = sum[last] + 1 ;
R[rt] = R[last] ;
L[rt] = L[last] ;
if (l < r){
if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
else R[rt] = update(R[last], mid + 1, r, x) ;
}
return rt ;
}
il int query(int Left, int Right, int l, int r, int k){
if (l == r) return aft[l] ; int 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(), 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%d", &a, &b, &c) ; int k = (b - a + 1) / c ;
cout << query(T[a - 1], T[b], 1, Len, k) << endl ;
}
return 0 ;
}

事实上,加上那优化之后,总用时大约$27000ms$,而我这个不加优化的版本足足跑了$56677ms$……真丢人啊