题面

题解

我们对于每一个与宫殿相连的点，分别计算它会作为多少个点的最短路的起点

若该点为\(u\)，对于某个点\(p\)来说，如果\(d=|p-u|\)，且在\([p-d,p+d]\)中不存在点到\(p\)的距离小于\(u\)到\(p\)的距离，那么\(u\)就可以作为\(p\)的最短路的起点

易知可行的\(p\)肯定是连续的一段区间，所以我们可以二分左右端点

设\(sum_i\)表示点\(i\)到点\(1\)的距离，我们维护关键点的区间中\((sum_i-l_i)_{\max}\)和\((sum_i+l_i)_{\min}\)。对于\(p\)来说，\([p-d,p]\)中可行的关键点肯定是最大的\(sum_i-l_i\)，而\([p,p+d]\)中肯定是最小的\(sum_i+l_i\)，用\(ST\)表可以做到\(O(1)\)查询。然后把这两个点和\(u\)比较，如果\(u\)比起它们仍然更优，那么\(u\)就可以占领\(p\)

注意判断一下如果两个关键点到\(p\)的距离相等只能算一个，所以特判一下就好了

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=2e5+5;struct node{    int u,d;    node(){}    node(R int x,R int y):u(x),d(y){}    inline bool operator <(const node &b)const{return u
      
       l1[y]?x:y;}inline int Min(R int x,R int y){return l2[x]==l2[y]?min(x,y):l2[x]
       
        mid&&better(g,get2(mid+1,r),p)!=g)return false;    return true;}void solve(){    ll res=0;    fp(i,1,k){        int l=1,r=e[i].u,mid,x,ans;        while(l<=r)ck(mid=(l+r)>>1,i)?(ans=mid,r=mid-1):(l=mid+1);        x=ans;        l=e[i].u,r=n;        while(l<=r)ck(mid=(l+r)>>1,i)?(ans=mid,l=mid+1):(r=mid-1);        res+=ans-x+1;    }    print(res);}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read();    fp(i,2,n)sum[i]=read()+sum[i-1],Log[i]=Log[i>>1]+1;    while(m--){        k=read();        fp(i,1,k)e[i].u=read(),e[i].d=read();        init(),solve();    }    return Ot(),0;}