[Arc082F] Sandglass
Description
有一个沙漏由两个上下相通玻璃球A和B构成，这两个玻璃球都含有一定量的沙子，我们暂且假定AB中位于上方的玻璃球的为U，下方的玻璃球为L，则除非U中没有沙子，否则每秒钟都会有1克沙子从U掉入L。在第0个时刻，A中有a克沙子，B中有X?a克沙子(总共有X克沙子)，且U为A，L为B(即A上B下)。在r1,r2,...,rK这些时刻，我们将倒转整个沙漏，使得原来的U变成L，原来的L变成U。对于翻转操作，t时刻是指从第0个时刻起经过t秒后的时刻，我们可以将翻转沙漏的操作看做瞬间完成的。现在有Q次询问，每一次询问会给定一对非负整数（ti，ai），求a=ai，第ti时刻，A中所含沙子的克数。
Input
第一行一个正整数X
第二行一个正整数K
第三行K个整数，表示r1,r2,...,rK
接下来一行一个正整数Q
接下来Q行，每行两个非负整数，分别表示每次次询问的(ti,ai)
Output
一共Q行对于每次询问，输出一行一个非负整数表示答案。
Sample Input
Sample 1
180
3
60 120 180
3
30 90
61 1
180 180
Sample 2
100
1
100000
4
0 100
90 100
100 100
101 100
Sample 3
100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10
Sample Output
Sample 1
60
1
120
Sample 2
100
10
0
0
Sample 3
19
52
91
10
58
42
100
HINT
(1leq x leq 10^9,1leq kleq 10^5)
所有输入数据均为非负整数
试题分析
数形结合：考虑每一个翻转时刻的以a为x轴，剩余沙子数量为y轴的图像。
那么可以发现当沙子在流失的时候图像逐渐下移，碰到0的部分就变成了0。
当沙子在流入的时候图像上移，碰到X的部分就变成了X。
然而图像在0时刻一开始是一段斜率为1的直线，原先被“压缩”成为一条直线的部分不会随着变化展开，所以整个过程图像都在压缩。
于是发现这是一个三段函数，直接记录上面的和下面的转折点然后计算即可。
代码写的丑了点
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline LL read(){
LL x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const LL INF = 2147483600;
const LL MAXN = 100010;
LL flip[MAXN+1][2],up[MAXN+1][2];
LL X,N,t[MAXN+1],Q;
int main(){
X=read(),N=read(); bool lossing=1;
LL l=0,r=X; up[0][0]=l,up[0][1]=r;
flip[0][0]=0; flip[0][1]=X;
for(LL i=1;i<=N;i++) {
t[i]=read();
if(lossing) {
flip[i][0]=flip[i-1][0]; flip[i][1]=flip[i-1][1];
flip[i][0]=max(flip[i][0],flip[i][0]-(l-(t[i]-t[i-1])));
l=max(0LL,l-(t[i]-t[i-1])),r=max(0LL,r-(t[i]-t[i-1]));
}
else {
flip[i][0]=flip[i-1][0]; flip[i][1]=flip[i-1][1];
flip[i][1]=min(flip[i][1],flip[i][1]-(r+(t[i]-t[i-1])-X));
l=min(X,l+(t[i]-t[i-1])),r=min(X,r+(t[i]-t[i-1]));
} if(flip[i][1]<flip[i][0]) flip[i][0]=flip[i][1];
up[i][0]=l; up[i][1]=r;
lossing^=1;
} Q=read();
while(Q--){
LL tim=read(),A=read(),x=upper_bound(t,t+N+1,tim)-t-1;
LL Add=tim-t[x];
if(!(x&1)) Add=-Add;
if(flip[x][0]==flip[x][1]){ printf("%lld
",min(X,max(Add+up[x][0],0LL))); continue;}
else {
if(A<=flip[x][0]) printf("%lld
",min(X,max(Add+up[x][0],0LL)));
else if(A>flip[x][0]&&A<flip[x][1]) printf("%lld
",min(X,max(Add+up[x][0]+A-flip[x][0],0LL)));
else printf("%lld
",min(X,max(Add+up[x][1],0LL)));
}
}
return 0;
}