有数据就是好

以及

对于\(k\)个关键点中的每一个关键点\(a\),二分它能更新到的左端点和右端点

设\(d=|a−p|\)，则\(a\)可以更新\(p\)当且仅当区间\([p−d,p+d]\)中的关键点到\(p\)的距离没有比\(a\)更优的

用\(st\)表维护两个东西 : 区间中到右端点最短的距离 , 区间中到右端点最短的距离

具体细节见代码

#include
    
     #include
     
      #include
      
       #include
       
        #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="<
        
         <
         
           pii;const LL INF=1e18;inline LL read(){ register LL x=0,f=1;register char c=getchar(); while(c<48||c>57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}const int MAXN=2e5+5;const int logN=19;LL a[MAXN],p[MAXN],len[MAXN],st1[MAXN][logN+1],st2[MAXN][logN+1];int log2[MAXN];int n,m,k;pii pp[MAXN];inline LL dis(int x,int y){ if(x>y) return INF; return a[y-1]-a[x-1];}inline LL calc1(int l,int r){ if(l>r) return INF; int len=log2[r-l+1]; int pos1=l+(1<
          
           <
           
            = int pos2=upper_bound(p+1,p+k+1,r)-p-1;// > if(pos1>pos2) return INF; return calc1(pos1,pos2)+dis(p[pos2],r);}inline LL calc2(int l,int r){ if(l>r) return INF; int len=log2[r-l+1]; int pos=r-(1<
            
             pos2) return INF; return calc2(pos1,pos2)+dis(l,p[pos1]);}inline bool check1(int x,int t){ if(t<1||t>n) return false; int pos=p[x],d=pos-t,l=t-d,r=t+d; LL zuo=cal1(l,t),you=cal2(t,r-1); LL dist=min(zuo,you),now=dis(t,pos)+len[x]; if(now
             
              n) return false; int pos=p[x],d=t-pos,l=t-d,r=t+d; LL zuo=cal1(l+1,t),you1=cal2(t,r-1),you2=cal2(t,r); LL dist=min(zuo,you2),now=dis(pos,t)+len[x]; if(now
              
               >1]+1; while(m--){ k=read(); for(int i=1;i<=k;i++){ int x=read(),y=read(); pp[i]=pii(x,y); } sort(pp+1,pp+k+1); for(int i=1;i<=k;i++){ p[i]=pp[i].first,len[i]=pp[i].second; st1[i][0]=len[i],st2[i][0]=len[i]; } for(int j=1;j<=18;j++) for(int i=1;i<=k;i++){ int x=i+(1<<(j-1)),y=i+(1<
               
                k) break; st1[i][j]=min(st1[i][j-1]+dis(p[x-1],p[y]),st1[x][j-1]);//区间中到右端点最近的 st2[i][j]=min(st2[i][j-1],st2[x][j-1]+dis(p[i],p[x]));//区间中到左端点最近的 } LL ans=0; for(int i=1;i<=k;i++){ int L=1,R=p[i]; while(L+1
                
                 >1; if(check1(i,mid)) R=mid; else L=mid+1; } if(check1(i,R-1)) R--; int pos1=R; L=p[i],R=n; while(L+1
                 
                  >1; if(check2(i,mid)) L=mid; else R=mid-1; } if(check2(i,L+1)) L++; ans+=L-pos1+1; } printf("%lld\n",ans); }}