题目概述

一条直线上有 $n$ 个点，只有相邻点之间有边。刚开始 $dis_i=10^{18}$ ，给出 $K$ 个关键点的 $dis$ ，用Bellman–Ford求最短路，令 $t$ 为每次最短路数组与上次不同的个数，求 $\sum t$。

解题报告

ZJOI近几年来（对我来说）唯一可做的题。然而ZhangZisu神仙表示：

ZJOI近三年来唯一一道noip题。 ——ZhangZisu

给考场上就会做的ZhangZisu神仙跪了Orz。

我考场上考虑的是对于每个点去找 $K$ 个关键点然后统计答案。事实证明我tm成功想反了。

因为 $\sum K$ 不大，所以我们肯定要用 $K$ 个关键点去统计贡献。看看样例就可以发现 $K$ 个关键点影响到的点是一段区间 $[L,R]$ ，而且显然 $[L,R]$ 可行意味着 $[l,r](L\le l\le r\le R)$ 可行，那么我们就可以二分 $L$ 和 $R$ 了，最终的答案就是 $\sum{R-L+1}$ 。

二分怎么验证？假设现在在求 $i$ 的区间，写一下式子就可以推出（以二分 $L$ 为例，$sum$ 表示和 $1$ 的距离）：

$$ \forall \ key\ x\to \begin{cases}dis_x+sum_x>dis_i+sum_i&L\le x<i\\dis_x-sum_x>dis_i+sum_i-2sum_L&x<L\end{cases} $$

然后我WA了……发现和答案总是差那么一点……为什么呢？我们看这种情况：

 1 2 2 1
1 X X X 1

上面是相邻点的距离，下面是关键点和还没求的点。你会发现第二个X不会被任何一个关键点修正！因为这个点和第一个关键点以及第二个关键点的间隔和距离都相同。特判掉这种情况就行了……

示例程序

我脑子有问题，不知道为什么写了个主席树……实际上线段树求区间极值就行了……

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=1e7;

int n,te,K,p[maxn+5],dis[maxn+5],ro[maxn+5][2];
LL tem[(maxn<<1)+5],pre[maxn+5],ans;
int len,sum[maxt+5],ls[maxt+5],rs[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void writei(int x){
    static int len=0,buf[30];do buf[len++]=x%10,x/=10; while (x);
    while (len) putchar(buf[--len]);puts("");
}
inline int Find(LL x){
    int L=1,R=tem[0];
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
            tem[mid]<=x?L=mid+1:R=mid-1;
    return R;
}
int Build(int L,int R){
    int p=len++;if (L==R) return p;int mid=L+(R-L>>1);
    ls[p]=Build(L,mid);rs[p]=Build(mid+1,R);return p;
}
int Insert(int p,int pos,int l=1,int r=tem[0]){
    int now=len++;sum[now]=sum[p];ls[now]=ls[p];rs[now]=rs[p];
    if (l==r) {sum[now]++;return now;}int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);
    sum[now]=sum[ls[now]]+sum[rs[now]];return now;
}
int Ask(int A,int B,int L,int R,int l=1,int r=tem[0]){
    if (R<l||r<L) return 0;if (L<=l&&r<=R) return sum[B]-sum[A];int mid=l+(r-l>>1);
    return Ask(ls[A],ls[B],L,R,l,mid)+Ask(rs[A],rs[B],L,R,mid+1,r);
}
inline int FindL(int pos){
    int L=1,R=p[pos];
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
        int l=1,r=pos,a,b;
        for (int m=l+(r-l>>1);l<=r;m=l+(r-l>>1))
            mid<=p[m]?r=m-1:l=m+1;b=l;
        l=1;r=pos;
        for (int m=l+(r-l>>1);l<=r;m=l+(r-l>>1))
            mid-p[m]<=p[pos]-mid?r=m-1:l=m+1;a=l;
        int A=Ask(ro[b-1][0],ro[pos-1][0],1,Find(dis[p[pos]]+pre[p[pos]]));
        int B=Ask(ro[a-1][1],ro[b-1][1],1,Find(dis[p[pos]]+pre[p[pos]]-(pre[mid]<<1)));
        !A&&!B?R=mid-1:L=mid+1;
    }
    return L;
}
inline int FindR(int pos){
    int L=p[pos],R=n;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
        int l=pos,r=K,a,b;
        for (int m=l+(r-l>>1);l<=r;m=l+(r-l>>1))
            p[m]<=mid?l=m+1:r=m-1;a=r;
        l=pos;r=K;
        for (int m=l+(r-l>>1);l<=r;m=l+(r-l>>1))
            p[m]-mid<=mid-p[pos]?l=m+1:r=m-1;b=r;
        int A=Ask(ro[pos][1],ro[a][1],1,Find(dis[p[pos]]-pre[p[pos]]));
        int B=Ask(ro[a][0],ro[b][0],1,Find(dis[p[pos]]-pre[p[pos]]+(pre[mid]<<1)));
        if (!A&&B==1&&p[b]-mid==mid-p[pos])
            if (dis[p[b]]+pre[p[b]]-pre[mid]==dis[p[pos]]+pre[mid]-pre[p[pos]])
                {L=mid+1;continue;} //间隔相同距离相同,特判为验证成功
        !A&&!B?L=mid+1:R=mid-1;
    }
    return R;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);readi(te);for (int i=2,x;i<=n;i++) readi(x),pre[i]=pre[i-1]+x;
    while (te--){
        readi(K);for (int i=1;i<=K;i++) readi(p[i]),readi(dis[p[i]]);
        for (int i=(sort(p+1,p+1+K),tem[0]=0,1);i<=K;i++)
            tem[++tem[0]]=dis[p[i]]+pre[p[i]],tem[++tem[0]]=dis[p[i]]-pre[p[i]];
        sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
        for (int i=(ro[0][0]=ro[0][1]=Build(1,tem[0]),1);i<=K;i++){
            ro[i][0]=Insert(ro[i-1][0],Find(dis[p[i]]+pre[p[i]]));
            ro[i][1]=Insert(ro[i-1][1],Find(dis[p[i]]-pre[p[i]]));
        }
            ans=0;for (int i=1;i<=K;i++) ans+=FindR(i)-FindL(i)+1;
        printf("%lld\n",ans);
    }
    return 0;
}