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行

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

---

Solution

问题可简化为A->B和B->A流(即翻转) 然后可以进一步简化为A的+1、-1操作。

首先要知道对于0-x的初始状态，不管我如何操作，任意时刻的剩余沙子必然是一个不下降序列。

那么每次增加或减少r[i+1]-r[i]，就可以通过线段树维护0-x所有开始状态的修改，一次修改会将0-x分为两个区间，一个区间直接赋值为0或x(超过了上下界)，另一个直接打标记区间加减。 这两个操作是logx的。 所以虽然代码很奇怪，但是它的确$O(nlogx)$。 然后根据t递增处理询问，到i个操作时处理当前所有t<r[i+1]的询问。这一部分直接用1-i的前缀和可以直接算出来并与0取max,x取min。

由于t递增，还可以直接$O(n)$实现。 可以看到第i次操作后操作剩余沙子数后只有三种情况：

sum+r[i]-r[i-1]x0

其中sum是r[i]-r[i-1]的总和 那么维护一个sum,一个开局为0的down,一个开局为x的up 所以最后的答案是max(down,min(up,sum))

这个东西看起来令人迷惑。 但其实仔细想一想，若对于$a_i$没有触碰过0或x的情况，答案就是sum。 但如果触碰到上下界： 以触碰上界为例，若某一时刻$su{m}_i=x$，则必然有$up=x$（区间不下降） 触碰下界同理。

那么只要$a_i$任意时刻触碰上下界都会变成跟up或down相同的状态，即跟up取min,down取max。

还有一种奇怪的方法，不懂。 似乎是通过加入时刻在树上新建点，然后线段树维护吗，倍增和二分辅助查询任意时间的修改和，时间复杂度$O(nlogn)$

---

Code

一.

#include<bits/stdc++.h> using namespace std; struct qry{ int t,a,id; bool operator <(const qry&v)const{ return t<v.t; } }q[100010]; int k,m,X,cnt,rt; int r[100010]; int lc[3000010]; int rc[3000010]; int tree[3000010][2]; int tag[3000010]; int add[3000010]; int ans[100010]; int init(int x,int y){ ++cnt; tree[cnt][0]=x; tree[cnt][1]=y; tag[cnt]=-1; return cnt; } void up(int id){ tree[id][0]=min(tree[lc[id]][0],tree[rc[id]][0]); tree[id][1]=max(tree[lc[id]][1],tree[rc[id]][1]); } void pushdown(int id,int l,int r){ int mid=l+r>>1; int &ls=lc[id],&rs=rc[id]; if(!ls) ls=init(l,mid); if(!rs) rs=init(mid+1,r); if(tag[id]!=-1){ tree[ls][0]=tree[ls][1]=tag[ls]=tag[id]; tree[rs][0]=tree[rs][1]=tag[rs]=tag[id]; add[ls]=add[rs]=0; tag[id]=-1; } if(add[id]){ tree[ls][0]+=add[id]; tree[ls][1]+=add[id]; tree[rs][0]+=add[id]; tree[rs][1]+=add[id]; add[ls]+=add[id]; add[rs]+=add[id]; add[id]=0; } } int upt1(int id,int l,int r,int x){ if(!id) id=init(l,r); pushdown(id,l,r); if(tree[id][0]>=X-x){ tree[id][1]=tree[id][0]=tag[id]=X; add[id]=0; } else if(tree[id][1]<=X-x){ tree[id][1]+=x; tree[id][0]+=x; add[id]+=x; } else{ int mid=l+r>>1; lc[id]=upt1(lc[id],l,mid,x); rc[id]=upt1(rc[id],mid+1,r,x); //cout<<id<<" "<<lc[id]<<" "<<rc[id]<<endl; up(id); } return id; } int upt2(int id,int l,int r,int x){ if(!id) id=init(l,r); pushdown(id,l,r); if(tree[id][1]<=x) tree[id][1]=tree[id][0]=add[id]=tag[id]=0; else if(tree[id][0]>=x){ tree[id][1]-=x; tree[id][0]-=x; add[id]-=x; } else{ int mid=l+r>>1; lc[id]=upt2(lc[id],l,mid,x); rc[id]=upt2(rc[id],mid+1,r,x); //cout<<id<<" "<<lc[id]<<" "<<rc[id]<<endl; up(id); } return id; } int query(int id,int l,int r,int x){ if(id==0) return x; pushdown(id,l,r); if(l==r) return tree[id][0]; int mid=l+r>>1; if(x<=mid) return query(lc[id],l,mid,x); else return query(rc[id],mid+1,r,x); } int main(){ int rev=0; scanf("%d%d",&X,&k); for(int i=1;i<=k;i++) scanf("%d",&r[i]); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].t,&q[i].a); q[i].id=i; } sort(q+1,q+m+1); r[k+1]=1e9; for(int i=0,j=1;i<=k;i++,rev^=1){ while(j<=m&&q[j].t<=r[i+1]){ int s=query(rt,1,X,q[j].a); if(rev) s=min(X,s+q[j].t-r[i]); else s=max(0,s-q[j].t+r[i]); ans[q[j++].id]=s; } if(j>m||i==k) break; if(rev) rt=upt1(rt,1,X,r[i+1]-r[i]); else rt=upt2(rt,1,X,r[i+1]-r[i]); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); }

二.

#include<bits/stdc++.h> using namespace std; int a[100010],x,n,m; int judge(int tt,int low=0,int up=x){ if(tt<low) return low; if(tt>up) return up; return tt; } int main(){ scanf("%d%d",&x,&n); a[0]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); int low=0,up=x,k=1,sum=0,flag=-1,t,b,num; while(m--){ scanf("%d%d",&t,&b); while(t>=a[k]&&k<=n){ num=flag*(a[k]-a[k-1]); sum+=num; low=judge(low+num); up=judge(up+num); k++; flag=-flag; } int ans=judge(flag*(t-a[k-1])+judge(sum+b,low,up)); printf("%d\n",ans); } return 0;

三.

#include<iostream> #include<cstdio> #include<vector> using namespace std; struct node{ int s,ls,rs; }t[800001]; int sum,n,m,x,y,f[200001],fa[200001][21],d,ans; node operator + (node a,node b){ node c; c.s=a.s+b.s; c.ls=min(a.ls,b.ls+a.s); c.rs=max(a.rs,b.rs+a.s); return c; } void add(int a,int l,int r,int u,int val){ if(l>u||r<u)return; if(l==r){ t[a].s=val; t[a].ls=val; t[a].rs=val; return; } int mid=(l+r)/2; add(a*2,l,mid,u,val); add(a*2+1,mid+1,r,u,val); t[a]=t[a*2]+t[a*2+1]; } int getans(int a,int l,int r,int &s){ if(l==r)return l; int mid=(l+r)/2; if(s+t[a*2].rs>=sum||s+t[a*2].ls<=0)return getans(a*2,l,mid,s); s=s+t[a*2].s; return getans(a*2+1,mid+1,r,s); } int find(int a,int l,int r,int ql,int qr,int &s){ if(l>qr||r<ql)return 0; if(ql<=l&&r<=qr){ if(s+t[a].rs>=sum||s+t[a].ls<=0)return getans(a,l,r,s); s=s+t[a].s; return 0; } int mid=(l+r)/2; int p=find(a*2,l,mid,ql,qr,s); if(p)return p; return find(a*2+1,mid+1,r,ql,qr,s); } void solve(int a,int l,int r,int ql,int qr){ if(l>qr||r<ql)return; if(ql<=l&&r<=qr){ ans=ans+t[a].s; return; } int mid=(l+r)/2; solve(a*2,l,mid,ql,qr); solve(a*2+1,mid+1,r,ql,qr); } void midfind(){ for(int i=20;i>=0;i--){ if(fa[d][i]!=0&&f[fa[d][i]]<=y){ d=fa[d][i]; if(fa[d][i]&1)x=0; else x=sum; } } if(f[d]>y)d=0; else{ if(d&1)x=0; else x=sum; } ans=x; int l=d,r=n; while(l<r){ int mid=(l+r+1)/2; if(f[mid]>y)r=mid-1; else l=mid; } y=y-f[l]; if(l&1)ans=ans+y; else ans=ans-y; solve(1,1,n,d+1,l); if(ans>sum)ans=sum; if(ans<0)ans=0; } int main(){ scanf("%d%d",&sum,&n); n++; f[n]=2000000000; for(int i=1;i<=n;i++){ if(i<n)scanf("%d",&f[i]); if(i&1)add(1,1,n,i,f[i-1]-f[i]); else add(1,1,n,i,f[i]-f[i-1]); } for(int i=n;i>=1;i--){ if(i&1)d=0; else d=sum; fa[i][0]=find(1,1,n,i+1,n,d); for(int j=1;j<=20;j++)fa[i][j]=fa[fa[i][j-1]][j-1]; } scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&y,&x); d=x; d=find(1,1,n,1,n,d); midfind(); printf("%d\n",ans); } }