ARC082D Sandglass

题意：有一个沙漏由A,B两个杯子组成。一共有X克沙子。 每秒会有一克沙子从上杯子流到下杯子，直到流完为止。

一共会有k次翻转杯子，第i次翻转杯子会在第 \(r_i\) 秒。

有q组询问，每组形如 \(t,a\) ，表示一开始A杯子在上，里面有a克沙子（B杯子里有 \(X-a\) 克沙子），求第t秒的时候A杯子里有多少沙子。 \(q,k\le 10^5\)

\(q,k\le 10^5\) ，暴力是一定会超时的。所以我们要想想办法。

计算当一开始里A杯子有s克沙子杯子里有\(l\)克沙子的时候第\(r_i\)秒时A里面的沙子量。

可以发现：1的时候为\(\max\{s-r_1,0\}\)，等等。

然后会发现每一次A里面的沙子量可以表示为\(\max\{\min\{s+a,b\},c\}\)，其中\(a,b,c\)都是常数，

所以我们可以找一波递推公式。

用\((a,b,c)\)表示\(\max\{\min\{s+a,b\},c\}\)。 设每次流沙子的时间为d。 发现当第奇数次翻转的时候，沙子量会从\((a,b,c)\)变为\(\max\{\max\{\min\{s+a,b\},c\}-d,0\}\)，第偶数次的时候会变成\(\min\{\max\{\min\{s+a,b\},c\}+d,l\}\)，暴力拆一波式子得到第奇数次翻转的时候变为\((a-d,b-d,\max\{c-d,0\})\)，第偶数次翻转的时候变为\((a+d,min\{\max\{b,c\}+d,l\},\min\{c+d,l\})\)。

求出每一次的a,b,c以后，对每组询问二分查找一下在第t秒之前最后一次翻转，这次翻转之前A杯子里有多少沙子，然后再一波\(O(1)\)计算一下就可以了（毕竟没有翻转直接流当然\(O(1)\)）

/*
Author: CNYALI_LK
LANG: C++
PROG: F.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
int r[102424];
int t[102424],y[102424];
int a[102424],b[102424],c[102424];
#define min mmin
#define max mmax
#define abs aabs
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int l,k,q,d;
    a[0]=0;
    b[0]=0x3f3f3f3f;
    c[0]=-0x3f3f3f3f;
    scanf("%d%d",&l,&k);
    for(int i=1;i<=k;++i)scanf("%d",r+i);
    a[1]=(-r[1]);
    b[1]=0x3f3f3f3f;
    c[1]=0;
    for(int i=2;i<=k;++i){
        d=r[i]-r[i-1];
        if(i&1){
            a[i]=a[i-1]-d;
            b[i]=b[i-1]-d;
            c[i]=mmax(c[i-1]-d,0);
        }
        else{
            a[i]=a[i-1]+d;
            b[i]=mmin(mmax(b[i-1],c[i-1])+d,l);
            c[i]=min(c[i-1]+d,l);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d",t+i);
        int lx,rx,mid;
        scanf("%d",y+i);
        lx=0;rx=k;
        while(lx<=rx){
            mid=(lx+rx)>>1;
            if(t[i]>=r[mid])lx=mid+1;
            else rx=mid-1;
        }
        --lx;
        t[i]-=r[lx];
        y[i]=max(min(y[i]+a[lx],b[lx]),c[lx]);
        if(lx&1){
            y[i]=min(y[i]+t[i],l);
        }
        else{
            y[i]=max(y[i]-t[i],0);
        }
        printf("%d\n",y[i]);
    }
    return 0;
}