Given array A[] of 30000 elements and 30000 queries [l, r]. Answer for each query, any indices l <= i, j <= r; i != j such that absolute value of A[i] + A[j] is minimal
At first glance, it seems to be a segment tree question, but there is an easy way to solve this.
We divide the array to blocks of size `B`. Then we precompute array F[][] and G[][] where F[b][x] stores optimal indices i, j where i lies in b-th block, and j is to the right of i but not exceeding x. Similarly, G[b][x] stores optimal indices i, j where i lies in b-th block and j is to the left of i but not less than x
precomputing these arrays is trivial by binary searching on sorted copy of the block.
Now, when given a query [l, r] we can iterate over all blocks b which lies in the range, and consider F[b][r] and G[b][l] as candidates for our answer.
But we are overlooking cases where both indices lies in the left/right border (which is not a full block) of our query, or when one lies in the left border and the other lies in the right border.
So we can just iterate over all pairs in the border, which will cost us O(B ^ 2).
Total time complexity : O((N/B)N logB) for precomputing and O(Q (N/B + B^2).
By letting B be cube root of N, we obtain complexity of O(N^(5/3) log B) + O(N^(2/3) * Q).
Which is obviously fast enough for the task. It also has very low constant.
#pragma GCC optimize("O3,unroll-loops")
#include <stdio.h>
#include <stdlib.h>
#define N 30005
#define B 780
#define K 40
int n, q, k1;
int a[N], k[K], c[B][N], d[B][N];
short c1[B][N], c2[B][N], d1[B][N], d2[B][N];
int cmpr(const void *i, const void *j)
{
return a[*(int*) i] - a[*(int*) j];
}
int L1(int a, int b)
{
return b > a ? b - a : a - b;
}
int close(int x)
{
int lower, upper;
lower = -1;
upper = k1;
while (upper - lower > 1)
{
int mid;
mid = lower + (upper - lower) / 2;
if (a[k[mid]] <= x)
lower = mid;
else
upper = mid;
}
if (-1 == lower)
return k[0];
if (k1 - 1 == lower)
return k[k1 - 1];
return x - a[k[lower]] < a[k[lower + 1]] - x ? k[lower] : k[lower + 1];
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (int i = 0; i * K < n; ++i)
{
int run, run1, run2;
run1 = run2 = -1;
run = 2e9 + 1;
k1 = 0;
int rb = i * K + K - 1 < n - 1 ? i * K + K - 1 : n - 1;
for (int j = i * K; j <= rb; ++j)
{
k[k1++] = j;
for (int j2 = i * K; j2 < j; ++j2)
if (L1(-a[j], a[j2]) < run)
{
run = L1(-a[j], a[j2]);
run1 = j2;
run2 = j;
}
}
qsort(k, k1, sizeof *k, cmpr);
for (int j = i * K + K; j < n; ++j)
{
int y;
y = close(-a[j]);
if (L1(a[y], -a[j]) < run)
{
run = L1(a[y], -a[j]);
run1 = y;
run2 = j;
}
c[i][j] = run;
c1[i][j] = run1;
c2[i][j] = run2;
}
}
for (int i = (n - 1) / K; i >= 0; --i)
{
int run, run1, run2;
run1 = run2 = -1;
run = 2e9 + 1;
k1 = 0;
int rb = i * K + K - 1 < n - 1 ? i * K + K - 1 : n - 1;
for (int j = i * K; j <= rb; ++j)
{
k[k1++] = j;
for (int j2 = i * K; j2 < j; ++j2)
if (L1(-a[j], a[j2]) < run)
{
run = L1(-a[j], a[j2]);
run1 = j2;
run2 = j;
}
}
qsort(k, k1, sizeof *k, cmpr);
for (int j = i * K - 1; j >= 0; --j)
{
int y;
y = close(-a[j]);
if (L1(a[y], -a[j]) < run)
{
run = L1(a[y], -a[j]);
run1 = y;
run2 = j;
}
d[i][j] = run;
d1[i][j] = run2;
d2[i][j] = run1;
}
}
for (int l, r; q--; )
{
int ans, ans1, ans2;
scanf("%d%d", &l, &r);
--l, --r;
ans1 = ans2 = -1;
ans = 2e9 + 1;
for (int i = l / K + 1; i * K + K - 1 < r; ++i)
{
if (c[i][r] < ans)
{
ans = c[i][r];
ans1 = c1[i][r];
ans2 = c2[i][r];
}
if (d[i][l] < ans)
{
ans = d[i][l];
ans1 = d1[i][l];
ans2 = d2[i][l];
}
}
for (int j = l; j < l / K * K + K && j <= r; ++j)
{
for (int j2 = l; j2 < j; ++j2)
if (L1(-a[j2], a[j]) < ans)
{
ans = L1(-a[j2], a[j]);
ans1 = j2;
ans2 = j;
}
}
if (l < r / K * K)
{
for (int j = r / K * K; j <= r; ++j)
{
for (int j2 = r / K * K; j2 < j; ++j2)
if (L1(-a[j2], a[j]) < ans)
{
ans = L1(-a[j2], a[j]);
ans1 = j2;
ans2 = j;
}
}
for (int j = l; j < l / K * K + K && j <= r; ++j)
for (int j2 = r / K * K; j2 <= r; ++j2)
{
if (j >= j2)
continue;
if (L1(-a[j2], a[j]) < ans)
{
ans = L1(-a[j2], a[j]);
ans1 = j;
ans2 = j2;
}
}
}
if (ans1 > ans2)
{
int temp = ans1;
ans1 = ans2;
ans2 = temp;
}
printf("%d %d\n", 1 + ans1, 1 + ans2);
}
return 0;
}