Description

有一个沙漏由两个上下相通玻璃球$A$和$B$构成，这两个玻璃球都含有一定量的沙子，我们暂且假定$A,B$中位于上方的玻璃球的为$U$，下方的玻璃球为$L$，则除非$U$中没有沙子，否则每秒钟都会有$1$克沙子从$U$掉入$L$。

在第$0$个时刻，$A$中有$a$克沙子，$B$中有$X-a$克沙子(总共有$X$克沙子)，且$U$为$A$，$L$为$B$(即$A$上$B$下)。

在$r_1,r_2,...,r_K$这些时刻，我们将倒转整个沙漏，使得原来的$U$变成$L$，原来的$L$变成$U$。对于翻转操作，$t$时刻是指从第$0$个时刻起经过$t$秒后的时刻，我们可以将翻转沙漏的操作看做瞬间完成的。

现在有Q次询问，每一次询问会给定一对非负整数$(t_i，a_i)$，求$a=a_i$的第$t_i$时刻，$A$中所含沙子的克数。

 

Input

第一行一个正整数$X$

第二行一个正整数$K$

第三行$K$个整数，表示$r_1,r_2,...,r_K$

接下来一行一个正整数$Q$

接下来$Q$行，每行两个非负整数，分别表示每次次询问的$(t_i,a_i)$

Output

一共$Q$行

对于每次询问，输出一行一个非负整数表示答案。

数据范围

$1\leq X \leq 10^9$

$1\leq K \leq 10^5$

$1\leq r_1<r_2<...<r_K \leq 10^9$

$1\leq Q \leq 10^5$

$0\leq t_1 < t_2 <...<t_Q\ leq 10^9$

$0\leq a_i \leq X$

 

题解

不难发现，反转的本质不过是从$A$向$B$流动还是从$B$向$A$流动。

进一步把问题简化，每次$A$中$+1$还是$A$中$-1$，难点在于当数量达到边界时会停止。

 

再换一个角度考虑，有个数组$a[ \space ]$，每次将它每个数都$+1$或$-1$，到$0$就不减，到$X$时不加，那么考虑从小到大排序，于是它就很显然满足一个性质：

·在任意时刻，所有曾经被下界$0$卡住的$a$一定是个前缀

·在任意时刻，所有曾经被上界$X$卡住(过)的$a$一定是个后缀

于是在任意时刻，这个数组$a$是一个三段的函数。

我在模拟赛上懒得思考了，于是就写了个线段树糊弄过去了。

维护区间最左边(最小)值和最右边(最大)值，分为这三种情况处理，

由于一定是恰好由这三段组成的，所以复杂度大概是$O(n\space 3log(n))$。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define mid (l+r>>1)#define M 200020using namespace std;int read(){	int nm=0,fh=1;char cw=getchar();	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');	return nm*fh;}int num[M],p[M<<2][2],tg[M<<2],mk[M<<2];int n,m,X,R[M],PS[M],tk[M],G[M],tim[M];bool cmpnum(int i,int j){return G[i]
          
           -1){ mk[x<<1]=mk[x<<1|1]=mk[x],tg[x<<1]=tg[x<<1|1]=0; p[x<<1][0]=p[x<<1|1][0]=mk[x]; p[x<<1][1]=p[x<<1|1][1]=mk[x]; } if(tg[x]){ tg[x<<1]+=tg[x],tg[x<<1|1]+=tg[x]; p[x<<1][0]+=tg[x],p[x<<1|1][0]+=tg[x]; p[x<<1][1]+=tg[x],p[x<<1|1][1]+=tg[x]; } mk[x]=-1,tg[x]=0;}inline void pushup(int x){p[x][0]=p[x<<1][0],p[x][1]=p[x<<1|1][1];}void build(int x,int l,int r){ tg[x]=0,mk[x]=-1; if(l==r){p[x][0]=p[x][1]=num[l];return;} build(x<<1,l,mid),build(x<<1|1,mid+1,r); pushup(x);}int getnum(int x,int l,int r,int pos){ if(l==r) return p[x][0]; int NUM; pushdown(x); if(pos<=mid) NUM=getnum(x<<1,l,mid,pos); else NUM=getnum(x<<1|1,mid+1,r,pos); pushup(x); return NUM;}void add(int x,int l,int r,int dt){ if(p[x][0]+dt>=X) p[x][0]=p[x][1]=mk[x]=X,tg[x]=0; else if(p[x][1]+dt<=0) p[x][0]=p[x][1]=mk[x]=0,tg[x]=0; else if(0<=p[x][0]+dt&&p[x][1]+dt<=X){p[x][0]+=dt,p[x][1]+=dt,tg[x]+=dt;} else pushdown(x),add(x<<1,l,mid,dt),add(x<<1|1,mid+1,r,dt),pushup(x);}int main(){ X=read(),m=read(); for(int i=1;i<=m;i++) R[i]=read(); n=read(); for(int i=1;i<=n;i++) tim[i]=read(),G[i]=read(),PS[i]=i; sort(PS+1,PS+n+1,cmpnum),R[++m]=tim[n]+1; for(int i=1;i<=n;i++) num[i]=G[PS[i]],tk[PS[i]]=i; build(1,1,n); for(int i=1,kd=-1,now=0;i<=m;i++,kd=-kd){ while(now
           
            <=R[i]){ now++; int x=getnum(1,1,n,tk[now]); x+=kd*(tim[now]-R[i-1]),printf("%d\n",max(min(x,X),0)); } add(1,1,n,(R[i]-R[i-1])*kd); } return 0;}