题解 P4803

· · 题解

巧了我也是随机跳到这题的。

这题大体做法和上一篇题解差不多。

题目大意是给定 n 条互不重合的线，问一段固定长度的线长度上方的线的权值和是多少，交点视为两个点都不在彼此上方。

这里可以发现交点显然不优，因为通过交点的其他飞机挡不了它。

由于对于一架飞机 x 而言，它的被影响的值只有在经过一个交点后才会改变（因为飞机的相对位置就改变了），所以可以使用前缀和来解决问题（当有一架飞机 i 升到 x 上面时，这个位置的改变值为 C_i，当有一架飞机 i 降到 x 下面时，这个位置的改变值为 -C_i）。

提供一个小优化。

就是由于 k 是定值，所以取最大值是个滑动窗口的问题，可以用单调队列求解（即使 k 不是定值也可以用st表解决）。

这样时间复杂度从 O(n^2\log n+qn) 优化到了 O((n^2+q)\log n)。（这里二分还是需要的）

所以这题根本用不着个 15s，给 3s 就够了。

另外这题建议用long double以保证精度。

有一个小细节，就是为了不把交点算进来，需要略微减少一下查询两端的距离。

发一下代码：

#include <bits/stdc++.h>
#define for1(i,n) for(i=1;i<=(n);i++)
#define for0(i,n) for(i=0;i<=(n);i++)
#define mems(a) memset(a,0,sizeof(a))
using namespace std;
typedef long double ld;
typedef long long ll;
const int N=2005,M=800005;
const ld eps=1e-10;
int m,d,n,cq,b[N],c[N],q[N],lq,rq;
ll ans[M],dp[N];
ld k[N],t[N],l[M];
vector<int> v[N],u[N];
bool dy(const ld &x,const ld &y){return abs(x-y)<eps;}
struct node{
    ld x;
    ll f;
    bool operator<(const node &nd)const{return x<nd.x;}
}p[N],s[N];
bool cmp(const int &x,const int &y){return l[x]<l[y];}
int main(){
    scanf("%d%d%d%d",&m,&d,&n,&cq);
    int i,j,x,cs,cp;
    ld z;
    for1(i,n) scanf("%d%d%d",&b[i],&x,&c[i]),k[i]=(ld)(x-b[i])/m;
    for1(i,cq) scanf("%d%Lf",&x,&l[i]),l[i]+=d-5e-11,v[x].push_back(i);
    for1(i,n){
        cs=cp=lq=rq=q[0]=dp[0]=0;
        for1(j,n){
            if(b[j]>b[i]) dp[0]+=c[j];
            if(!dy(k[i],k[j])){
                z=(b[i]-b[j])/(k[j]-k[i]);
                if(z>=0&&z<=m) p[++cp]={z,k[j]>k[i]?c[j]:-c[j]};
            }
        }
        sort(p+1,p+cp+1);
        for1(j,cp){
            if(dy(p[j].x,p[j-1].x)) s[cs].f+=p[j].f;
            else s[++cs]=p[j];
        }
        t[cs+1]=m;
        for0(j,cs) u[j].clear(),t[j]=s[j].x;
        for(int y:v[i]) u[upper_bound(t+1,t+cs+1,l[y])-t-1].push_back(y);
        for1(j,cs+1){
            sort(u[j-1].begin(),u[j-1].end(),cmp);
            for(int y:u[j-1]){
                while(l[y]-t[q[lq]+1]>d-eps) lq++;
                ans[y]=dp[q[lq]];
            }
            if(j>cs) break;
            dp[j]=dp[j-1]+s[j].f;
            while(t[j]-t[q[lq]+1]>d-eps) lq++;
            while(lq<=rq&&dp[j]>=dp[q[rq]]) rq--;
            q[++rq]=j;
        }
    }
    for1(i,cq) printf("%lld\n",ans[i]);
    return 0;
}