贝尔福特曼(?)的方式相当于每次将所有与源点直接相连的点的影响区域向两边各扩展一格。显然每个点在过程中最多更新其他点一次且这些点构成一段连续区间。这个东西二分st表查一下就可以了。注意某一轮中两点都更新某节点的情况。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<cassert> using namespace std; #define ll long long #define N 200010 #define inf 100000000000000000ll char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int T,n,m,a[N],L[N],R[N],lg2[N]; ll s[N],f[N][19],g[N][19]; struct data { int x,y; bool operator <(const data&a) const { return x<a.x; } }edge[N]; ll query(int x,int y,ll f[N][19]) { if (x>y) return inf; return min(f[x][lg2[y-x+1]],f[y-(1<<lg2[y-x+1])+1][lg2[y-x+1]]); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5308.in","r",stdin); freopen("bzoj5308.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),T=read(); for (int i=1;i<n;i++) a[i]=read(); for (int i=2;i<=n;i++) s[i]=s[i-1]+a[i-1]; for (int i=2;i<=n;i++) { lg2[i]=lg2[i-1]; if ((2<<lg2[i])<=i) lg2[i]++; } while (T--) { int m=read(); for (int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(); sort(edge+1,edge+m+1); for (int i=1;i<=m;i++) f[i][0]=edge[i].y-s[edge[i].x]; for (int j=1;j<=lg2[m];j++) for (int i=1;i<=m;i++) f[i][j]=min(f[i][j-1],f[min(i+(1<<j-1),n)][j-1]); for (int i=1;i<=m;i++) g[i][0]=edge[i].y+s[edge[i].x]; for (int j=1;j<=lg2[m];j++) for (int i=1;i<=m;i++) g[i][j]=min(g[i][j-1],g[min(i+(1<<j-1),n)][j-1]); ll ans=0; for (int i=1;i<=m;i++) { int l=1,r=edge[i].x-1;L[i]=r+1; while (l<=r) { int mid=l+r>>1,p=max(1,mid-(edge[i].x-mid)); int x=lower_bound(edge+1,edge+i+1,(data){mid,0})-edge,y=lower_bound(edge+1,edge+i+1,(data){p,0})-edge; if (query(y,x-1,f)+s[mid]>g[i][0]-s[mid]&&query(x,i-1,g)>g[i][0]) L[i]=mid,r=mid-1; else l=mid+1; } l=edge[i].x+1,r=n;R[i]=l-1; while (l<=r) { int mid=l+r>>1,p=min(n,mid+(mid-edge[i].x)-1); int x=lower_bound(edge+i,edge+m+1,(data){mid+1,0})-edge-1,y=lower_bound(edge+i,edge+m+1,(data){p+1,0})-edge-1; if (query(i+1,x,f)>f[i][0]&&query(x+1,y,g)-s[mid]>f[i][0]+s[mid] &&(y==m||edge[y+1].x!=p+1||g[y+1][0]-s[mid]>=f[i][0]+s[mid])) R[i]=mid,l=mid+1; else r=mid-1; } } for (int i=1;i<=m;i++) ans+=R[i]-L[i]+1; printf(LL,ans); } return 0; }