题意简述
直线上有 (n) 个点，第 (i) 个点与第 (i+1) 个点之间连双向边，边权为 (w[i])
另有一点 (S)
(m) 次询问：给定 (k) 条连接 (S) 与直线上一点的双向边（有边权），在新图上以 (S) 为源点跑 (Bellman-Ford) ，求跑完后所有点被更新次数的总和。
(n,m,k leq 2 imes 10^5)
想法
更新次数看上去难搞，仔细想后发现，对直线上每一个点，将 (S) 分别通过 (k) 条路走到该点的路径的边权和 (s) 及 路径上经过的边数 (t) 做一个单调队列（随 (t) 增大，(s) 减小），则该点被更新的次数就是单调队列中的元素数目。
发现仍不太好做。转而考虑每条从 (S) 到直线的边可以更新多少点，发现是一个区间。
于是二分+st表判断求区间的两端。注意计数时不要记重了……
复杂度 (O(nlog^2n))
总结
思想
可以换对象考虑问题。
要有影响区间的意识，二分意识。
码力
(set) 中似乎不一定 --s.begin()==s.end() ，所以用 (upper\_ bound) 时如果想 (--) 的话最好先判断再减。
注意操作对象……
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#define INF 1e18
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 200005;
typedef long long ll;
int n,m,k;
int w[N];
ll s[N];
struct data{
int a,l;
bool operator < (const data &b) const{ return a<b.a; }
}d[N];
ll st1[N][18],st2[N][18];
set<int> Set;
set<int>::iterator it;
int mp[N],Log[N];
ll Min1(int l,int r) {
if(l>r || l<0 || r>k) return INF;
int len=r-l+1,j=Log[len];
return min(st1[l][j],st1[r-(1<<j)+1][j]);
}
ll Min2(int l,int r) {
if(l>r || l<0 || r>k) return INF;
int len=r-l+1,j=Log[len];
return min(st2[l][j],st2[r-(1<<j)+1][j]);
}
int main()
{
n=read(); m=read();
for(int i=1;i<n;i++) w[i]=read();
for(int i=1;i<n;i++) s[i]=s[i-1]+w[i];
int t=0,cur=1;
for(int i=1;i<=n;i++){
if(i==cur) Log[i]=t++,cur*=2;
else Log[i]=t-1;
}
while(m--){
k=read();
for(int i=1;i<=k;i++) d[i].a=read(),d[i].l=read(),Set.insert(d[i].a);
sort(d+1,d+1+k);
for(int i=1;i<=k;i++) mp[d[i].a]=i;
for(int i=1;i<=k;i++) st1[i][0]=d[i].l+s[n-1]-s[d[i].a-1];
for(int i=1;i<=k;i++) st2[i][0]=d[i].l+s[d[i].a-1];
for(int j=1;j<18;j++){
int len=(1<<j);
for(int i=1;i+len-1<=k;i++){
st1[i][j]=min(st1[i][j-1],st1[i+len/2][j-1]);
st2[i][j]=min(st2[i][j-1],st2[i+len/2][j-1]);
}
}
ll ans=0;
for(int i=1;i<=k;i++){
int l=d[i].a,r=n,mid,bon,lm,rm;
while(l<r){
mid=(l+r+1)>>1;
it=Set.upper_bound(2*mid-d[i].a);
if(it!=Set.begin()) bon=mp[*(--it)]; else bon=0;
it=Set.upper_bound(mid);
if(it!=Set.begin()) lm=mp[*(--it)]; else lm=i;
it=Set.lower_bound(mid);
if(it!=Set.end()) rm=mp[*it]; else rm=k+1;
if(bon>0 && d[bon].a+d[i].a==mid*2 && st1[i][0]-(s[n-1]-s[mid-1])==st2[bon][0]-s[mid-1]){
if(Min1(i+1,lm)>st1[i][0] && Min2(rm,bon-1)-s[mid-1]>st1[i][0]-(s[n-1]-s[mid-1])) l=mid;
else r=mid-1;
}
else if(Min1(i+1,lm)>st1[i][0] && Min2(rm,bon)-s[mid-1]>st1[i][0]-(s[n-1]-s[mid-1])) l=mid;
else r=mid-1;
}
ans+=l-d[i].a+1;
l=1;r=d[i].a;
while(l<r){
mid=(l+r)>>1;
it=Set.lower_bound(2*mid-d[i].a);
if(it!=Set.end()) bon=mp[*it]; else bon=k+1;
it=Set.upper_bound(mid);
if(it!=Set.begin()) lm=mp[*(--it)]; else lm=0;
it=Set.lower_bound(mid);
if(it!=Set.end()) rm=mp[*it]; else rm=i;
if(bon<=k && d[bon].a+d[i].a==mid*2 && st1[bon][0]-(s[n-1]-s[mid-1])==st2[i][0]-s[mid-1]) l=mid+1;
else if(Min2(rm,i-1)>st2[i][0] && Min1(bon,lm)-(s[n-1]-s[mid-1])>st2[i][0]-s[mid-1]) r=mid;
else l=mid+1;
}
ans+=d[i].a-l;
}
printf("%lld
",ans);
//clear
for(int i=1;i<=k;i++){
Set.erase(d[i].a);
mp[d[i].a]=0;
}
}
return 0;
}