题解 P1081 【开车旅行】
这里提供另外一种预处理（最小、次小）的方法
用的是之前自己YY出来的树状数组+二分查找，有时候挺好用的，何况我不会数据结构qwq
值域树状数组肯定是单调的，所以可以二分
用这种方法可以实现一个容器
支持插入、删除一个数，以及查询第K大乃至某个给定范围内的数中的第K大
插入、删除正常做
查询时找出容器中满足在查询区间内的数值的范围，就能推出要查的数在数组里的位置了
位置是由单点的sum值体现的，二分查找就行了
只不过这种方法查询是 不过这题够用了
这题的预处理实现方式就是倒过来插值，同时查询，总共
然而这题是在考倍增关于倍增各位讲得很清楚了qwq
代码贴这，写了好久啊orz
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const double eps = 0.0000001;
const double feps = -0.0000001;
const double inf = 100000000000000000.0;
const int MAXN = 100005;
struct node {
int g, h; // g: position, h: rank
} P[MAXN];
int N, H[MAXN], poi[MAXN];
int A[MAXN], B[MAXN], C[MAXN];
int D[MAXN][23];
ll dis[MAXN][23][2]; // 0: A, 1: B
int abs(int x) { return x>0 ? x : -x; }
ll read()
{
ll o = 0, oo = 0; char c = getchar();
while (c < '0' || c > '9') oo |= (c=='-'), c = getchar();
while (c >='0' && c <='9') o = (o<<3)+(o<<1)+(c&15), c = getchar();
return oo ? -o : o;
}
int cmp1(node x, node y) { return x.h < y.h; }
int cmp2(node x, node y) { return x.g < y.g; }
void add(int x) { for (; x<=N; x+=x&(-x)) C[x] += 1; return; }
int sum(int x) { int res=0; for (; x; x-=x&(-x)) res += C[x]; return res; }
void init()
{
N = read();
for (int i=1; i<=N; i++) H[i] = read(), P[i] = (node){i, H[i]};
sort(P+1, P+N+1, cmp1);
for (int i=1; i<=N; i++) H[i] = P[i].h, poi[i] = P[i].g, P[i].h = i;
sort(P+1, P+N+1, cmp2);
A[N] = B[N] = 0, add(P[N].h);
A[N-1] = 0, B[N-1] = N, add(P[N-1].h);
for (int i=N-2; i>=1; i--)
{
int l, r, m, t=sum(P[i].h), a, b, c;
if (t > 0) {
l = 0, r = P[i].h; // (l, r]
while (r - l > 1) {
m = (l + r) >> 1;
if (sum(m) < t) l = m; else r = m;
}
a = r;
} else { a = 0; }
if (t < N-i) {
l = P[i].h, r = N; // (l, r]
while (r - l > 1) {
m = (l + r) >> 1;
if (sum(m) > t) r = m; else l = m;
}
b = r;
} else { b = 0; }
if (!a) { B[i] = poi[b], c = 0; }
if (!b) { B[i] = poi[a], c = 0; }
if (a&&b) {
int da = abs(H[P[i].h] - H[a]);
int db = abs(H[P[i].h] - H[b]);
B[i] = (da > db) ? poi[b] : poi[a];
c = (da > db) ? a : b;
}
if (t > 1) {
l = 0, r = P[i].h; // (l, r]
while (r - l > 1) {
m = (l + r) >> 1;
if (sum(m) < t-1) l = m; else r = m;
}
a = r;
} else { a = 0; }
if (t < N-i-1) {
l = P[i].h, r = N; // (l, r]
while (r - l > 1) {
m = (l + r) >> 1;
if (sum(m) < t+2) l = m; else r = m;
}
b = r;
} else { b = 0; }
int da = abs(H[P[i].h] - H[a]);
int db = abs(H[P[i].h] - H[b]);
int dc = abs(H[P[i].h] - H[c]);
if (c) {
if (a) c = (da > dc) ? c : a;
if (b) c = (dc > db) ? b : c;
} else {
if (a) c = a;
if (b) c = b;
}
A[i] = poi[c];
add(P[i].h);
}
for (int i=1; i<=N; i++) {
D[i][0] = B[A[i]];
dis[i][0][0] = abs(H[P[A[i]].h] - H[P[i].h]);
dis[i][0][1] = abs(H[P[B[A[i]]].h] - H[P[A[i]].h]);
}
for (int j=1; j<=21; j++) {
for (int i=1; i<=N; i++) {
D[i][j] = D[D[i][j-1]][j-1];
dis[i][j][0] = dis[i][j-1][0] + dis[D[i][j-1]][j-1][0];
dis[i][j][1] = dis[i][j-1][1] + dis[D[i][j-1]][j-1][1];
}
}
return;
}
void work()
{
double T = inf, t;
int S = 1;
ll M = read(), m, LA, LB;
for (int i=1; i<=N; i++) {
LA = 0, LB = 0, m = M;
int o = i;
for (int j=21; j>=0; j--) if (D[o][j]) {
if (dis[o][j][0] + dis[o][j][1] <= m) {
m -= dis[o][j][0] + dis[o][j][1];
LA += dis[o][j][0], LB += dis[o][j][1];
o = D[o][j];
}
}
if (A[o] && abs(H[P[o].h] - H[P[A[o]].h]) <= m)
LA += abs(H[P[o].h] - H[P[A[o]].h]);
if (LB > 0) {
t = (double) LA / LB;
if (t < T) T = t, S = i;
else if (t-T<eps&&t-T>feps) S = H[P[i].h] > H[P[S].h] ? i : S;
} else if (T + 1.0 > inf) S = H[P[i].h] > H[P[S].h] ? i : S;
}
printf("%d\n", S);
M = read();
for (; M; M--)
{
S = read(), m = read(), LA = 0, LB = 0;
int o = S;
for (int j=21; j>=0; j--) if (D[o][j]) {
if (dis[o][j][0] + dis[o][j][1] <= m) {
m -= dis[o][j][0] + dis[o][j][1];
LA += dis[o][j][0], LB += dis[o][j][1];
o = D[o][j];
}
}
if (A[o] && abs(H[P[o].h] - H[P[A[o]].h]) <= m)
LA += abs(H[P[o].h] - H[P[A[o]].h]);
printf("%lld %lld\n", LA, LB);
}
return;
}
int main()
{
// freopen("", "r", stdin);
// freopen("", "w", stdout);
init();
work();
// fclose(stdin);
// fclose(stdout);
return 0;
}