左右与右左是两个独立的问题
设f[i]表示i时刻左右车道减少一条的答案
g[i]表示i时刻右左车道增加一条的答案
ans=min(f[i]+g[i+r])
计算f[i]:
首先暴力计算出f[m+1],同时记录下每个时刻刚开走的车的数量now[i]
从m到1计算f[i],如果该时刻开走的车数不足n1+1,则无影响
否则多了一辆车,选取后面最早的有空位的时刻j开走
用一个栈维护空位,复杂度为$O(m)$
计算g[i]:
首先暴力计算出g[0],同时记录下每个时刻刚开走的车的数量now[i]
从1到m+r计算g[i],如果该时刻开走的车数不足n2+1,则无影响
否则多了一辆车,选取后面最早的有空位的时刻j开走
因为j是单调变化的,所以复杂度为$O(m)$
#include<cstdio>
#define N 200010
typedef long long ll;
struct P{int t,k;P(){}P(int _t,int _k){t=_t,k=_k;}}q[N];
int n1,n2,m,r,i,a[N],b[N],now[N],rem,t,mx,fin;ll ans,f[N],g[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int min(int a,int b){return a<b?a:b;}
int main(){
for(read(n1),read(n2),read(m),read(r),i=1;i<=m;i++)read(a[i]),read(b[i]);
for(rem=ans=0,i=1;i<=m;i++)rem+=a[i],t=min(rem,n1+1),now[i]=t,rem-=t,ans+=rem;
mx=m+rem/n1+1,fin=rem%n1;
if(fin)ans+=(ll)(fin+rem-n1)*(rem/n1)/2;else ans+=(ll)rem*(rem/n1-1)/2;
for(q[t=1]=P(mx,fin),i=m;i;i--){
if(now[i]>n1){
while(t&&q[t].k==n1)t--;
if(!t)q[t=1]=P(++mx,0);
q[t].k++,ans+=q[t].t-i;
}else q[++t]=P(i,now[i]);
f[i]=ans;
}
for(rem=ans=0,i=1;i<=m+r;i++)rem+=b[i],t=min(rem,n2+1),now[i]=t,rem-=t,ans+=rem;
mx=m+r+rem/(n2+1)+1,fin=rem%(n2+1);
if(fin)ans+=(ll)(fin+rem-n2-1)*(rem/(n2+1))/2;else ans+=(ll)rem*(rem/(n2+1)-1)/2;
for(i=t=1;i<=m+r;i++){
g[i]=ans;
if(now[i]>n2){
while(t<=m+r&&(t<i||now[t]>n2))t++;
if(t<=m+r)now[t]++,ans+=t-i;else{
if(fin>n2)mx++,fin=0;
fin++,ans+=mx-i;
}
}
}
for(ans=1LL<<62,i=1;i<=m;i++)if(f[i]+g[i+r]<ans)t=i,ans=f[i]+g[i+r];
return printf("%d",t),0;
}