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

· · 题解

思路

发现两滴雨能互相转移到需要满足两滴雨落地的位置的距离差不超过两滴雨落地的时间差乘上人行走的速度。当我们把人看作一个坐标为 (s_i,0) 的雨滴之后其实就是求每一滴雨最多能转移到多少个雨滴。考虑第一个限制，发现我们直接去计算两个节点的时间差时间是受不了的。

我们考虑直接使每个雨滴从落地的位置往左右分别走落地的时间乘上人的速度作为他的区间。此时我们的限制变成一个雨滴包含另一个雨滴时就可以转移。考虑这为什么是对的，由于两个雨滴都会同时往左右走，因此他们时间的重复部分等于被抵消了。所以这个就等同于计算了在这段时间差能否从一个雨滴走到另一个雨滴。考虑最后的答案怎么计算，此时我们的问题变成了一个二维偏序的问题。我们考虑先给区间按 l 排一个序然后用树状数组转移 dp。每次将 dp_i+1 的值转移到所有 r_j \le r_i 的 dp_j，当前区间为查询区间则不转移，回答询问即可。

代码

#include<bits/stdc++.h>
#define int long long
#define N 500001
using namespace std;
int n, q, ans[N], idx, c[N << 1];
int v1, v2, v3, s[N << 1];//v1 为雨滴落下的速度，v2 为风速，v3 为人行走的速度
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
__inline__ int read(){
    int x=0,f=1;
    char ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    while(!(ch>='0'&&ch<='9')){
        if(ch=='-'){
            f=-f;
        }
        ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    }
    while(ch>='0'&&ch<='9') 
        x=x*10+(ch^48),ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    return x*f;
}
__inline__ void write(int x){
    if(x>9) 
        write(x/10);
    ((O==obuf+(1<<21))&&(fwrite(obuf,1,O-obuf,stdout),O=obuf)),*O++=(x%10)^48;
}
struct Flush{
    ~Flush(){fwrite(obuf,1,O-obuf,stdout);}
}_;
unordered_map<int, int>mp;
struct Node{
    int l, r, id;
}a[N << 1];
__inline__ bool cmp(Node x1, Node x2){
    if(x1.l == x2.l){
        if(x1.r == x2.r){
            return x1.id > x2.id;
        }
        return x1.r > x2.r;
    }
    return x1.l < x2.l;
}
#define lowbit(x) (x & -x)
#define Max(x, y) (x > y ? x : y)
__inline__ void Push_Date(int x, int k){//树状数组维护前缀max
    while(x){
        c[x] = Max(c[x], k);
        x -= lowbit(x);
    }
}
__inline__ int Get_w(int x){
    int ans = 0;
    while(x <= idx){
        ans = Max(ans, c[x]);
        x += lowbit(x);
    }
    return ans;
}
signed main(){
    n = read(), q = read(), v1 = read(), v2 = read(), v3 = read();
    for(int i = 1; i <= n; i ++){
        int x = read(), y = read(), xx = x * v1 + y * v2;//为了避免爆精度，考虑全部乘上一个v1
        a[i].r = xx + y * v3;
        a[i].l = xx - y * v3;
        s[i] = a[i].r;
    }
    for(int i = 1; i <= q; i ++){
        int x = read();
        a[n + i].l = a[n + i].r = x * v1;
        a[n + i].id = i; 
        s[n + i] = x * v1;
    }
    sort(s + 1, s + n + q + 1);
    for(int i = 1; i <= n + q; i ++){
        if(i == 1 || s[i] != s[i - 1]){
            mp[s[i]] = ++ idx;
        }
    }
    sort(a + 1, a + n + q + 1, cmp);
    for(int i = 1; i <= n + q; i ++){
        if(a[i].id){
            ans[a[i].id] = Get_w(mp[a[i].r]);//询问
        }
        else{
            Push_Date(mp[a[i].r], Get_w(mp[a[i].r]) + 1);
        }//转移
    }
    for(int i = 1; i <= q; i ++){
        write(ans[i]);
        ((O==obuf+(1<<21))&&(fwrite(obuf,1,O-obuf,stdout),O=obuf)),*O++='\n';
    }
    return 0;
}

AC 记录。