自动搬运

查看原文

来自洛谷，原作者为

	a326820068122c RP++

搬运于2025-08-24 22:03:46，当前版本为作者最后更新于2022-07-26 10:32:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

题目大意是给定 $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;
}