传送门

其实就是一个数不断加加减减,并且不能超出$[0,X]$的范围。我们可以二分出在什么时刻第一次超出边界,那这之后就跟初始的$a_i$无关了。同样,对于每个时刻的$a=0$和$a=X$,我们也要预处理出这之后第一次超出边界的时刻,然后建成树之后在上面倍增跳就行了。

#include <cstdio>
#include <cstring>
#include <set>
#define LL long long
#define MAXN 200010
using namespace std;

int n,m;
LL ti[MAXN],L,d[MAXN],sd[MAXN];
int p[MAXN][2],nump;
int pre[MAXN][21];
set< pair<LL,int> > S1,S2;

int getp(LL v,LL delta){
    int t1=n+1,t2=n+1;
    set< pair<LL,int> >::iterator it=S1.lower_bound(make_pair(delta-v,0));
    if(it!=S1.begin()) t1=(--it)->second;
    it=S2.lower_bound(make_pair(L+delta-v+1,0));
    if(it!=S2.end()) t2=it->second;
    if(t1==n+1 && t2==n+1) return nump+1;
    if(t1<t2) return p[t1][0];
    else return p[t2][1];
}

void pre_gao(int x){
    while(!S1.empty() && (--S1.end())->first>=sd[x]) S1.erase(--S1.end());
    S1.insert(make_pair(sd[x],x));
    while(!S2.empty() && S2.begin()->first<=sd[x]) S2.erase(S2.begin());
    S2.insert(make_pair(sd[x],x));
    pre[p[x][0]][0]=getp(0,sd[x]);
    pre[p[x][1]][0]=getp(L,sd[x]);
}

LL calc(LL delta,LL v,LL t){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(ti[mid]<=t) l=mid;
        else r=mid-1;
    }
    LL res=v+sd[l]-delta;
    if(l&1) res+=t-ti[l];
    else res-=t-ti[l];
    if(res<0) res=0;
    if(res>L) res=L;
    return res;
}

LL query(LL t,LL v){
    int temp=getp(v,0);
    if(!temp || ti[temp]>t) return calc(0,v,t);
    for(int i=20;i>=0;i--)
        if(ti[pre[temp][i]]<=t)
            temp=pre[temp][i];
    return calc(sd[(temp-1)%n+1],(temp>n)?L:0,t);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%lld%d",&L,&n);
    n++;
    for(int i=1;i<=n;i++){
        if(i<n) scanf("%lld",ti+i);
        else ti[i]=ti[i-1]+L;
        d[i]=ti[i]-ti[i-1];
        if(i&1) d[i]=-d[i];
        sd[i]=sd[i-1]+d[i];
    }
    for(int i=1;i<=n;i++) p[i][0]=++nump;
    for(int i=1;i<=n;i++) ti[p[i][1]=++nump]=ti[i];
    ti[nump+1]=1LL<<60;
    for(int i=n;i>=1;i--) pre_gao(i);
    for(int j=0;j<=20;j++) pre[nump+1][j]=nump+1;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=20;j++) pre[p[i][0]][j]=pre[pre[p[i][0]][j-1]][j-1];
        for(int j=1;j<=20;j++) pre[p[i][1]][j]=pre[pre[p[i][1]][j-1]][j-1];
    }
    scanf("%d",&m);
    while(m--){
        LL t,v;
        scanf("%lld%lld",&t,&v);
        if(t>ti[n]) t=ti[n];
        printf("%lld\n",query(t,v));
    }
    return 0;
}