题解：P11255 [GDKOI2023 普及组] 淋雨

· · 题解

首先将所有雨点转化为 a_i, b_i，表示其将要在 a_i 时落在 b_i。因为起点在变，我们考虑倒着做，即使时间倒流，这样我们就可以将起点当作一个雨点转移。设 f_i 表示强制淋到 i 雨时的最大答案，就有

f_i = \max_{a_j > a_i, v_c \times (a_j - a_i) \geq |b_i - b_j|}\{f_j + 1\}

我们将绝对值拆开，即要求

\begin{cases} a_j > a_i & A\\ b_i + v_ca_i \leq b_j + v_ca_j & B\\ b_i - v_ca_i \geq b_j - v_ca_j & C\\ \end{cases}

这是一个经典的三维偏序问题，直接使用 CDQ 分治即可做到 \mathcal{O}(n\log^2n + q\log n) 复杂度。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

namespace IO{
    #define SIZ (1 << 18)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
    #define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    template <typename tp>
    void rd(tp &x){
        x = 0;
        int f = 1;
        char c = gc();
        for (;!isdigit(c); c == '-' && (f = -1), c = gc());
        for (;isdigit(c); x = x * 10 + (c ^ 48), c = gc());
        x *= f;
    }
    template <typename tp, typename... Arg>
    inline void rd(tp &x, Arg &...args){
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush(){
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c){
        p3 - obuf == SIZ && (flush(), 1538), *p3++ = c;
    }
    template <typename tp>
    void prt(tp x, char ed = '\n'){
        x < 0 && (pc('-'), x = -x);
        static char stk[40];
        int stkp = 0;
        do{
            stk[stkp] = char(x % 10), x /= 10, ++stkp;
        } while (x);
        while (stkp){
            pc(char(stk[--stkp] + '0'));
        }
        pc(ed);
    }
    #undef gc
    #undef SIZ
}

using namespace IO;

const int maxn = 5e5 + 10, maxq = 5e5 + 10;

struct Val{
    long long x, y;
    int f;
    constexpr Val(long long x = 0, long long y = 0, int f = 0): x(x), y(y), f(f){}
} a[maxn];

int n, q, s, v, k;
int res[maxq];
vector<long long> tmp;
vector<pair<int, long long> > qry[maxn];

namespace segtree{
    int tree[maxn];
    inline int lbw(int x){
        return x & -x;
    }
    inline void add(int x, int k, int len){
        for (;x <= len; tree[x] = max(tree[x], k), x += lbw(x));
    }
    inline int query(int x){
        int res = 0;
        for (;x; res = max(res, tree[x]), x -= lbw(x));
        return res;
    }
}

using namespace segtree;

inline int pos(int x){
    return lower_bound(tmp.begin(), tmp.end(), a[x].y - k * a[x].x) - tmp.begin() + 1;
}

inline void solve(int l, int r){
    if (l == r){
        return a[l].f = max(a[l].f, 1), void();
    }
    const int mid = l + r >> 1;
    const auto cmp = [&](Val x, Val y){return x.y + k * x.x > y.y + k * y.x;};
    solve(l, mid), sort(a + l, a + mid + 1, cmp), sort(a + mid + 1, a + r + 1, cmp);
    tmp.clear();
    for (int i = l; i <= r; i++){
        tmp.push_back(a[i].y - k * a[i].x);
    }
    sort(tmp.begin(), tmp.end()), unique(tmp.begin(), tmp.end());
    for (int i = 0; i <= tmp.size(); tree[i++] = 0);
    for (int i = mid + 1, p = l; i <= r; i++){
        for (;p <= mid && a[p].y + k * a[p].x >= a[i].y + k * a[i].x; add(pos(p), a[p].f, tmp.size()), p++);
        a[i].f = max(a[i].f, query(pos(i)) + 1);
    }
    sort(a + mid + 1, a + r + 1, [](Val x, Val y){return x.x > y.x || x.x == y.x && x.y < y.y;}), solve(mid + 1, r);
}

int main(){
    rd(n, q, s, v, k);
    for (int i = 1; i <= n; i++){
        long long x, y;
        rd(x, y), a[i] = Val(y, x * s + y * v, 0);
    }
    sort(a + 1, a + n + 1, [](Val x, Val y){return x.x > y.x || x.x == y.x && x.y < y.y;}), solve(1, n);
    sort(a + 1, a + n + 1, [](Val x, Val y){return x.y + k * x.x > y.y + k * y.x;});
    for (int i = 1; i <= q; i++){
        long long x;
        rd(x), x *= s;
        int l = 1, r = n;
        while (l < r){
            const int mid = l + r + 1 >> 1;
            if (x <= a[mid].y + k * a[mid].x){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        x <= a[l].y + k * a[l].x && (qry[l].push_back(make_pair(i, x)), 1538);
    }
    for (int i = 1; i <= n; i++){
        tmp.push_back(a[i].y - k * a[i].x);
    }
    sort(tmp.begin(), tmp.end()), unique(tmp.begin(), tmp.end());
    for (int i = 1; i <= tmp.size(); tree[i++] = 0);
    for (int i = 1; i <= n; i++){
        add(pos(i), a[i].f, tmp.size());
        for (auto x: qry[i]){
            const int p = upper_bound(tmp.begin(), tmp.end(), x.second) - tmp.begin();
            p && (res[x.first] = query(p));
        }
    }
    for (int i = 1; i <= q; i++){
        prt(res[i]);
    }
    flush();

return 0;
}

但是我们有 n, q \leq 5 \times 10^5 的加强版，这时 CDQ 分治无法通过。我们注意到如果 B 和 C 满足，即 v_c \times (a_j - a_i) \geq |b_i - b_j|，那么显然 a_j \geq a_i，而不难发现 a_j = a_i 并无意义，即 A 并无作用，于是我们对 B 和 C 做二维偏序即可，时间复杂度 \mathcal{O}((n + q)\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 5e5 + 10, maxq = 5e5 + 10;

struct Val{
    long long x, y;
    int f;
    constexpr Val(long long x = 0, long long y = 0, int f = 0): x(x), y(y), f(f){}
} a[maxn];

int n, q, s, v, k;
int res[maxq];
vector<long long> tmp;
vector<pair<int, long long> > qry[maxn];

namespace BIT{
    int tree[maxn];
    inline int lbw(int x){
        return x & -x;
    }
    inline void add(int x, int k){
        for (;x <= tmp.size(); tree[x] = max(tree[x], k), x += lbw(x));
    }
    inline int query(int x){
        int res = 0;
        for (;x; res = max(res, tree[x]), x -= lbw(x));
        return res;
    }
}

using namespace BIT;

inline int pos(int x){
    return lower_bound(tmp.begin(), tmp.end(), a[x].y - k * a[x].x) - tmp.begin() + 1;
}

int main(){
    scanf("%d %d %d %d %d", &n, &q, &s, &v, &k);
    for (int i = 1; i <= n; i++){
        long long x, y;
        scanf("%lld %lld", &x, &y), a[i] = Val(y, x * s + y * v, 0), tmp.push_back(a[i].y - k * a[i].x);
    }
    sort(tmp.begin(), tmp.end()), unique(tmp.begin(), tmp.end()), sort(a + 1, a + n + 1, [](Val x, Val y){return x.y + k * x.x > y.y + k * y.x;});
    for (int i = 1; i <= q; i++){
        long long x;
        scanf("%lld", &x), x *= s;
        int l = 1, r = n;
        while (l < r){
            const int mid = l + r + 1 >> 1;
            if (x <= a[mid].y + k * a[mid].x){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        x <= a[l].y + k * a[l].x && (qry[l].push_back(make_pair(i, x)), 1538);
    }
    for (int i = 1; i <= n; i++){
        a[i].f = query(pos(i)) + 1, add(pos(i), a[i].f);
        for (auto x: qry[i]){
            const int p = upper_bound(tmp.begin(), tmp.end(), x.second) - tmp.begin();
            p && (res[x.first] = query(p));
        }
    }
    for (int i = 1; i <= q; i++){
        printf("%d\n", res[i]);
    }

return 0;
}