(⊙o⊙)…
SOL： 我们显然可以二分，我们考虑二分每一个由城堡出来的路径的贡献，必然是一条线段。
用ST表check就好了。
#include<bits/stdc++.h> #define sight(x) ('0'<=x&&x<='9') #define N 400017 #define LL long long #define int LL using namespace std; inline void read(int &x) { static int b; static char c; for (b=1,c=getchar();!sight(c);c=getchar()) if(c=='-') b=-1; for (x=0;sight(c);c=getchar()) x=x*10+c-48; x=x*b; } void write(LL x) { if (x<10) {putchar(48+x); return;} write(x/10); putchar(48+x%10); } inline void writeln(LL x) { if (x<0) {putchar('-'); x=-x;} write(x); putchar(' '); } struct Node{ int a,b; Node() {} Node(int x,int y):a(x),b(y){} inline bool operator <(const Node& XX)const&{ return a<XX.a; } }p[N]; #define SIZ 19 #define orz1(x) (1ll*p[x].b+sum[p[x].a]) #define orz2(x) (1ll*p[x].b+sum[n]-sum[p[x].a]) int k,ch1[N][SIZ],ch2[N][SIZ],n,len,b[N],idl,idr; LL sum[N],key1[N],key2[N]; void build() { for (int i=1;i<=k;i++) ch1[i][0]=ch2[i][0]=i, key1[i]=1ll*p[i].b+sum[p[i].a],key2[i]=1ll*p[i].b+sum[n]-sum[p[i].a]; for (int j=1;j<SIZ;j++) for (int i=1;i<=k;i++) { if (key1[ch1[i][j-1]]>key1[ch1[i+(1<<j-1)][j-1]]) ch1[i][j]=ch1[i+(1<<j-1)][j-1]; else ch1[i][j]=ch1[i][j-1]; if (key2[ch2[i][j-1]]<key2[ch2[i+(1<<j-1)][j-1]]) ch2[i][j]=ch2[i][j-1]; else ch2[i][j]=ch2[i+(1<<j-1)][j-1]; } } inline int que2(int l,int r) { len=b[r-l+1]; return key2[ch2[l][len]]<key2[ch2[r-(1<<len)+1][len]]?ch2[l][len]:ch2[r-(1<<len)+1][len]; } inline int que1(int l,int r) { len=b[r-l+1]; return key1[ch1[l][len]]>key1[ch1[r-(1<<len)+1][len]]?ch1[r-(1<<len)+1][len]:ch1[l][len]; } int p1,p2,anw; inline bool check1(int x,int id) { if (x<=0) return 0; idl=lower_bound(p+1,p+k+1,Node(x,0))-p; idr=lower_bound(p+1,p+k+1,Node(x*2-p[id].a,0))-p; if (idr<idl) p1=que2(idr,idl-1); else p1=0; p2=que1(idl,id); if (!p1) anw=p2; else if (!p2) anw=p1; else if (p[p1].b+sum[x]-sum[p[p1].a]!=p[p2].b+sum[p[p2].a]-sum[x]) anw=(p[p1].b+sum[x]-sum[p[p1].a]>p[p2].b+sum[p[p2].a]-sum[x])?p2:p1; else anw=p[p2].a-x>x-p[p1].a?p1:p2; return anw==id; } inline bool check2(int x,int id) { if (x>n) return 0; idl=lower_bound(p+1,p+k+1,Node(x,0))-p; idr=upper_bound(p+1,p+k+1,Node(x*2-p[id].a,0))-p; p1=que2(id,idl-1); if (idl<idr) p2=que1(idl,idr-1); else p2=0; if (!p1) anw=p2; else if (!p2) anw=p1; else if (p[p1].b+sum[x]-sum[p[p1].a]!=p[p2].b+sum[p[p2].a]-sum[x]) anw=(p[p1].b+sum[x]-sum[p[p1].a]>p[p2].b+sum[p[p2].a]-sum[x])?p2:p1; else anw=p[p2].a-x>x-p[p1].a?p1:p2; return anw==id; } int m,x,l,r,siz; LL ans; signed main () { for (int i=2;i<N;i++) b[i]=b[i>>1]+1; read(n); read(m); for (int i=2;i<=n;i++) read(x),sum[i]=sum[i-1]+x; while (m--) { read(k); ans=0; for (int i=1;i<=k;i++) read(p[i].a),read(p[i].b); sort(p+1,p+k+1); build(); for (int i=1;i<=k;i++) { // if (i==50) { // l=0; // } siz=1<<18; l=r=p[i].a; // 1+1=fhbhandsome while (siz) { if (check1(l-siz,i)) l-=siz; if (check2(r+siz,i)) r+=siz; siz>>=1; } ans+=r-l+1; // if (m==98) // cerr<<i<<' '<<l<<' '<<r<<endl; } writeln(ans); } return 0; }