我们观察到只有查询操作。
这个查询可以通过线段树来实现，因为可以通过维护最大最小值来维护差值最大值，因为是一个星期，所以容易相当答案是关于周期循环的，因此建立七棵线段树。
恶心的是有两个方向，因此我们要建十四棵线段树维护
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; const int inf=1e9; const int mod=1e9+7; struct node{ int l,r; int lans,rans,mx,mi; }tr[15][N<<2]; struct seg{ int lans,rans,mx,mi; }; int a[15][N]; int n; void pushup(node t[],int u){ t[u].lans=max(t[u<<1].lans,t[u<<1|1].lans); t[u].lans=max(t[u].lans,t[u<<1|1].mx-t[u<<1].mi); t[u].rans=max(t[u<<1].rans,t[u<<1|1].rans); t[u].rans=max(t[u].rans,t[u<<1].mx-t[u<<1|1].mi); t[u].mx=max(t[u<<1].mx,t[u<<1|1].mx); t[u].mi=min(t[u<<1].mi,t[u<<1|1].mi); } void build(node t[],int st,int u,int l,int r){ if(l==r){ int k=(l+st)%7; if(k==0) k=7; if(st>=7){ k=8-k; } t[u]={l,r,0,0,a[k][l],a[k][l]}; } else{ t[u]={l,r}; int mid=l+r>>1; build(t,st,u<<1,l,mid); build(t,st,u<<1|1,mid+1,r); pushup(t,u); } } seg query(node t[],int u,int l,int r){ if(t[u].l>=l&&t[u].r<=r){ return seg{t[u].lans,t[u].rans,t[u].mx,t[u].mi}; } int mid=t[u].l+t[u].r>>1; seg ans={0,0,0,inf}; seg tmp,tmp1; if(l<=mid){ tmp=query(t,u<<1,l,r); ans.lans=max(ans.lans,tmp.lans); ans.rans=max(ans.rans,tmp.rans); ans.mx=max(ans.mx,tmp.mx); ans.mi=min(ans.mi,tmp.mi); } if(r>mid){ tmp1=query(t,u<<1|1,l,r); ans.lans=max(ans.lans,tmp1.lans); ans.rans=max(ans.rans,tmp1.rans); ans.mx=max(ans.mx,tmp1.mx); ans.mi=min(ans.mi,tmp1.mi); if(l<=mid){ ans.lans=max(ans.lans,tmp1.mx-tmp.mi); ans.rans=max(ans.rans,tmp.mx-tmp1.mi); } } return ans; } int main(){ ios::sync_with_stdio(false); cin>>n; int i,j; for(i=1;i<=n;i++){ int x,d; cin>>x>>d; for(j=1;j<=4;j++){ a[j][i]=a[7-j+1][i]=x+d*(j-1); } } for(i=1;i<=14;i++){ build(tr[i],i-1,1,1,n); } int m; cin>>m; while(m--){ int l,r; cin>>l>>r; if(l<r){ int k=(9-l%7)%7; if(k==0) k=7; int ans=query(tr[k],1,l,r).lans; ans=max(ans,0); cout<<ans<<endl; } else{ int k=(l%7); if(k==0)k=7; k=15-k; swap(l,r); int ans=query(tr[k],1,l,r).rans; ans=max(ans,0); cout<<ans<<endl; } } return 0; }