题解P2249 【深基13.例1】查找

· · 个人记录

这里提供一种全新的线性做法，时间复杂度是 \Theta(n+m) 的。但是由于常数较大，被 \Theta(n+m\log n) 的二分做法吊起来打。

我们用一个结构体存储每一个询问的位置及其询问的值。我们按照这个值排序，从而将问题转化为只有正数，使得我们可以搞一个指针，每一次询问暴力向右爬找到不小于询问元素的第一个元素，每次询问就可以做到均摊 \Theta(1) 了。

这种技巧在 P5073 里又一次出现，让每一次查询时间复杂度降到均摊 \Theta(\log n)。

这种技巧在 P4118 里又一次出现，让每一次整块查询时间复杂度降到均摊 \Theta(1)。

代码：（使用基数排序，保证线性时间复杂度）

#include <bits/stdc++.h>
#define ptrdiff_t int
#define size_t int
char c;
const size_t READ_MAXN = 1 << 15;
const size_t READ_ARR_SIZE = READ_MAXN;
const size_t WRITE_MAXN = 1 << 20;
const size_t WRITE_ARR_SIZE = WRITE_MAXN;
char inbuf[READ_ARR_SIZE], outbuf[WRITE_ARR_SIZE];
char *curinpos = inbuf + READ_MAXN, *curoutpos = outbuf;
char *end_inbuf = inbuf + READ_MAXN, *end_outbuf = outbuf + WRITE_MAXN;
inline char gc() {
    if (curinpos == end_inbuf) {
        end_inbuf = inbuf + fread(inbuf, 1, READ_MAXN, stdin);
        curinpos = inbuf;
    }
    return *curinpos++;
}
inline void pc(char x) {
    if (curoutpos == end_outbuf) {
        fwrite(outbuf, 1, READ_MAXN, stdout);
        curoutpos = outbuf;
        end_outbuf = outbuf + READ_MAXN;
    }
    *curoutpos++ = x;
}
inline void pc_unchecked(char x) { *curoutpos++ = x; }
inline unsigned readuint() {
    unsigned eax(0);
    c = gc();
    while (c < 48) c = gc();
    while (c > 47) eax = (eax << 3) + (eax << 1) + (c & 15), c = gc();
    return eax;
}
inline void putint(int x) {
    static char buf[15];
    static int curpos;
    curpos = 0;
    do {
        buf[curpos++] = (x % 10) | 48;
        x /= 10;
    } while (x);
    while (curpos--) pc(buf[curpos]);
}
inline void putint_unchecked(int x) {
    static char buf[15];
    static int curpos;
    curpos = 0;
    if (x < 0) {
        pc_unchecked('-');
        x = -x;
    }
    do {
        buf[curpos++] = (x % 10) | 48;
        x /= 10;
    } while (x);
    while (curpos--) pc_unchecked(buf[curpos]);
}
struct question {
    int id;
    long long k;
};
question* q;
bool cmp(const question& a, const question& b) { return a.k < b.k; }
// sort [q+l, q+r)
inline void Sort(ptrdiff_t l, ptrdiff_t r) {
    if (r - l <= 1500) {
        std::sort(q + l, q + r, cmp);
        return;
    }
    long long *val = new long long[r - l + 5], *valt = new long long[r - l + 5];
    for (ptrdiff_t i = l; i < r; i++) val[i - l] = valt[i - l] = q[i].k | ((1ll * i) << 32);
    ptrdiff_t *cnt = new ptrdiff_t[32768];
    for (int i = 0; i < 30; i += 15) {
        memset(cnt, 0, 32768 * sizeof(ptrdiff_t));
        for (ptrdiff_t j = 0; j < r - l; j++) ++cnt[(val[j] >> i) & 32767];
        for (int j = 1; j < 32768; j++) cnt[j] += cnt[j - 1];
        for (ptrdiff_t j = r - l - 1; ~j; j--) valt[--cnt[(val[j] >> i) & 32767]] = val[j];
        memcpy(val, valt, (r - l + 5) * sizeof(long long));
    }
    question* tmp = new question[r - l + 5];
    for (ptrdiff_t i = l; i < r; i++) tmp[i - l] = q[i];
    for (ptrdiff_t i = l; i < r; i++) q[i] = tmp[(val[i - l] >> 32) - l];
    //delete[] val;
    //delete[] valt;
    //delete[] cnt;
    //delete[] tmp;
}
int *ans;
int main() {
    ptrdiff_t curpos = 1;
    unsigned n = readuint(), m = readuint();
    q = new question[m + 5];
    int* ia = new int[n + 5];
    ans = new int[m + 5];
    for (unsigned i = 1; i <= n; i++) ia[i] = readuint();
    long long minn = 0x3f3f3f3f;
    for (unsigned i = 0; i < m; i++) {
        q[i].id = i;
        q[i].k = readuint();
        (q[i].k < minn) && (minn = q[i].k);
    }
    for (unsigned i = 1; i <= n; i++) ia[i] -= minn;
    for (unsigned i = 0; i < m; i++) q[i].k -= minn;
    Sort(0, m);
    for (int i = 0; i < m; i++) {
        while (curpos <= n && ia[curpos] < q[i].k) ++curpos;
        ans[q[i].id] = (ia[curpos] != q[i].k ? -1 : curpos);
    }
    for (unsigned i = 0; i < m; i++) putint_unchecked(ans[i]), pc_unchecked(' ');
    fwrite(outbuf, 1, curoutpos - outbuf, stdout);
    return 0;
}

upd：已经卡到了最优解。