原文链接https://www.cnblogs.com/zhouzhendong/p/ZJOI2018Day2T2.html
题目传送门 - BZOJ5308
题目传送门 - LOJ2529
题目传送门 - 洛谷P4501
题意
略。
题解
首先这个题目名称用来形容 cly 太好了。
考虑每一对 $(a_i,l_i)$ 对于答案的贡献。
我们可以发现每一条这种路径能够更新的节点是连续的一段。于是我们考虑二分边界。
设 x 为当前节点，我们当前二分到的节点为 y ，如果 x 不能更新节点 y ，那么，在区间 $[x,2y-x]$ 中必然存在一个点到 y 的最短路小于等于 x 到 y 的最短路。
于是，我们可以利用差分思想维护两个 ST 表来分别得到两边的最短路。
但是有一个特殊情况：
一个点同时被左右更新。
只需要特判就好了。
这题细节好多啊。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=200005;
const LL INF=1LL<<57;
int n,m,w[N],Log[N];
LL x[N],s1[N][18],s2[N][18];
struct Node{
int a,L;
}v[N];
bool cmp(Node A,Node B){
return A.a<B.a;
}
LL query1(int L,int R){
if (L>R)
return INF;
int d=Log[R-L+1];
return min(s1[L+(1<<d)-1][d],s1[R][d]);
}
LL query2(int L,int R){
if (L>R)
return INF;
int d=Log[R-L+1];
return min(s2[L+(1<<d)-1][d],s2[R][d]);
}
int p[N];
LL l[N];
int main(){
Log[1]=0;
for (int i=2;i<N;i++)
Log[i]=Log[i>>1]+1;
n=read(),m=read();
for (int i=1;i<n;i++)
w[i]=read(),x[i+1]=x[i]+w[i];
while (m--){
int k=read();
for (int i=1;i<=k;i++)
v[i].a=read(),v[i].L=read();
sort(v+1,v+k+1,cmp);
for (int i=1;i<=k;i++)
p[i]=v[i].a,l[i]=v[i].L;
for (int i=1;i<=k;i++){
s1[i][0]=l[i]-x[p[i]];
s2[i][0]=l[i]+x[p[i]];
for (int j=1;j<18;j++){
s1[i][j]=s1[i][j-1];
s2[i][j]=s2[i][j-1];
if (i-(1<<(j-1))>0){
s1[i][j]=min(s1[i][j],s1[i-(1<<(j-1))][j-1]);
s2[i][j]=min(s2[i][j],s2[i-(1<<(j-1))][j-1]);
}
}
}
LL ans=0;
for (int i=1;i<=k;i++){
int now=p[i],R=now,L=now;
for (int j=17;j>=0;j--){
int t=R+(1<<j);
if (t>n)
continue;
int pL=i+1;
int pM1=upper_bound(p+1,p+k+1,t)-p-1;
int pM2=lower_bound(p+1,p+k+1,t)-p;
int pR=upper_bound(p+1,p+k+1,t*2-now)-p-1;
if (query1(pL,pM1)<=l[i]-x[now])
continue;
if (query2(pM2,pR)-x[t]<=l[i]+x[t]-x[now])
continue;
R=t;
}
for (int j=17;j>=0;j--){
int t=L-(1<<j);
if (t<=0)
continue;
int pR=i-1;
int pM1=lower_bound(p+1,p+k+1,t)-p;
int pM2=upper_bound(p+1,p+k+1,t)-p-1;
int pL=lower_bound(p+1,p+k+1,t*2-now)-p;
if (query2(pM1,pR)<=l[i]+x[now])
continue;
if (query1(pL,pM2)+x[t]<=l[i]+x[now]-x[t])
continue;
L=t;
}
ans+=R-L+1;
if (R<n){
R++;
int pR=lower_bound(p+1,p+k+1,R*2-now)-p;
if (p[pR]==R*2-now){
int pM1=upper_bound(p+1,p+k+1,R)-p-1;
int pM2=lower_bound(p+1,p+k+1,R)-p;
if (query1(i+1,pM1)>l[i]-x[now]
&&query2(pM2,pR-1)-x[R]>l[i]+x[R]-x[now]
&&l[i]+x[R]-x[now]==l[pR]+x[p[pR]]-x[R])
ans++;
}
}
}
printf("%lld\n",ans);
}
return 0;
}