时间限制:10000ms
单点时限:5000ms
内存限制:256MB
描述
你正在和小冰玩一个猜数字的游戏。小冰首先生成一个长为N的整数序列 $A_1, A_2, \dots , A_N$。在每一轮游戏中，小冰会给出一个区间范围 $[L, R]$，然后你要猜一个数 $K$。如果 $K$ 在 $A_L, A_{L+1}, \dots , A_R$ 中，那么你获胜。
在尝试了几轮之后，你发现这个游戏太难（无聊）了。小冰决定给你一些提示，你每猜一次，小冰会告诉你 $K$ 与 $A_L, A_{L+1}, \dots, A_R$ 中最接近的数的绝对差值，即 $\min(|A_i - K|), L \le i \le R$。
现在，请你实现这个新功能。
输入
第一行为一个整数 $T$，表示数据组数。
每组数据的第一行为两个整数 $N$ 和 $Q$。
第二行为 $N$ 个由空格分开的整数，分别代表 $A_1, A_2, \dots, A_N$。
接下来 $Q$ 行，每行三个由空格隔开的整数 $L、R、K$。
输出
每组数据的先输出一行"Case #X:"，X为测试数据编号。
接下来对每个询问输出一行，每行为一个整数，即为所求的值。
数据范围
1 ≤ T ≤ 20
0 ≤ Ai, K ≤ 109
1 ≤ L ≤ R ≤ N
小数据
1 ≤ N, Q ≤ 1000
大数据
1 ≤ N, Q ≤ 200000
输入数据量较大，推荐使用scanf / BufferedReader等IO方法。
- 样例输入
-
1
9 3
1 8 3 4 9 2 7 6 5
1 9 10
3 7 9
5 6 5 - 样例输出
- Case #1:
- 1
- 0
- 3
Solution
- 先定义一个概念
- 给定数组 $a_{1},\dots,a_{n}$，数 $k$ 在区间 $[l,r]$ 上的Rank——记作Rank(k, l, r)——定义为：
- a[l..r]上小于k的数字的个数
- 对于每组询问 $L, R, K$，先求出Rank(K, L, R)，剩下的问题就是求（静态）区间第 $k$ 小。
- 为了方便表述，将 $a[l \dots r]$ 上第 $k$ 小的数记作 least(k, l, r)，ans表示每个查询的答案，分三种情况：
- (1) Rank(K, L, R) = 0, ans = least(Rank(K, L, R)+1, L, R) - K
- (2) Rank(K, L, R) = R-L+1, ans = K - least(Rank(K, L, R), L, R)
- (3) otherwise, ans = min(least(Rank(K, L, R)+1, L, R) - K, K - least(Rank(K, L, R), L, R))
- Rank(K, L, R)与least(K, L, R)都可用划分树实现，单次查询的时间复杂度都是O(log n)，而且二者代码非常相似。
- 划分树的空间复杂度是 $O(n \log n)$。
- 划分树 (partition tree)
- 划分树是线段树的一种，用于维护数组 $A[1 \dots n]$。它的每个节点u代表数组 $A$ 的一些元素。
- 假设内部（即非叶子)节点 $u$ 表示元素是 $u[L..R] \subset A$，定义节点 $u$ 的长度 $u.length=R-L+1$，记 $u$ 的左右儿子分别为 $v, w$，令
- \[mid\equiv \frac{L+R}{2}\]
- 则
- \[v.length=mid-L+1, w.length=R-mid\]
- 或者表示成
- \[ v = v[L, mid], w=w(mid,R] \]
Implmentation
#include <bits/stdc++.h>
using namespace std; const int N(2e5+); int a[][N], toleft[][N], sa[N]; void build(int lev, int l, int r){
if(l==r) return;
int mid=(l+r)>>, &tar=sa[mid], nl=mid-l+;
for(int i=l; i<=r; i++) if(a[lev][i]<tar) nl--;
for(int i=l, lp=l, rp=mid+; i<=r; i++){
if(a[lev][i]<tar) a[lev+][lp++]=a[lev][i];
else if(a[lev][i]>tar) a[lev+][rp++]=a[lev][i];
else nl?a[lev+][lp++]=a[lev][i],nl--:a[lev+][rp++]=a[lev][i];
toleft[lev][i]=toleft[lev][l-]+lp-l;
}
build(lev+, l, mid); build(lev+, mid+, r);
}
//Rank(l, r, k):区间[l, r]内比k小的数的个数
//满足区间加法
int Rank(int lev, int L, int R, int l, int r, int val){
if(L==R) return a[lev][L]<val; int nl=toleft[lev][r]-toleft[lev][l-], nr=r-l+-nl, mid=(L+R)>>; if(sa[mid]>=val){
if(nl){
l=L+toleft[lev][l-]-toleft[lev][L-];
r=l+nl-;
return Rank(lev+, L, mid, l, r, val);
}
return ; //error-prone
}
else{
if(nr){
r+=toleft[lev][R]-toleft[lev][r];
l=r-nr+;
return nl+Rank(lev+, mid+, R, l, r, val);
}
return nl;
}
} int Query(int lev, int L, int R, int l, int r, int k){
if(L==R) return a[lev][L]; int nl=toleft[lev][r]-toleft[lev][l-], nr=r-l+-nl, mid=(L+R)>>; if(nl>=k){
l=L+toleft[lev][l-]-toleft[lev][L-];
r=l+nl-;
return Query(lev+, L, mid, l, r, k);
}
r+=toleft[lev][R]-toleft[lev][r];
l=r-nr+;
return Query(lev+, mid+, R, l, r, k-nl);
} int main(){
int T; scanf("%d", &T);
for(int n, q, cs=; T--;){
scanf("%d%d", &n, &q);
printf("Case #%d:\n", ++cs); for(int i=; i<=n; i++) scanf("%d", sa+i), a[][i]=sa[i];
sort(sa+, sa+n+); build(, , n); for(int l, r, k, rk, res; q--;){
scanf("%d%d%d", &l, &r, &k);
rk=Rank(, , n, l, r, k);
//printf("%d\n", rk);
if(rk==) res=Query(, , n, l, r, rk+)-k;
else if(rk==r-l+) res=k-Query(, , n, l, r, rk);
else res=min(Query(, , n, l, r, rk+)-k, k-Query(, , n, l, r, rk));
printf("%d\n", res);
}
}
}
问题解决了，但代码不是可以写得再短一些？
Rank和Query可否合并到一起呢？