66 E Petya and Post

問題

環状の道路にn個のガソリンスタンドが並んでいる。1番のガソリンスタンドはn番と2番のガソリンスタンドと隣接している。
それぞれのガソリンスタンド間の距離はa[i]、それぞれのガソリンスタンドで供給できるガソリンの量b[i]が与えられる。

あるガソリンスタンドを出発して、環状の道路を一周できるかどうかを知りたい。
一周するためには、途中でガソリンの量がマイナスになってはならない。
一周できるガソリンスタンドの番号を答えよ。（回り方は時計回り、反時計回りのどちらでもよい）

制約条件

n≦10^5
a[i],b[i]≦10^9
a[i]の和はb[i]の和に等しい。

方針

1番のスタンドから出発して、i番目のスタンドに辿り着く直前でのガソリンの量はΣa[i]-b[i]とかける。
これが全てのiについて非負であるようなスタンドを求めたい。
これを愚直にやるとO(n^2)かかってしまうのでTLE.

双方向キューを使い、数列S[i]=Σa[i]-b[i]について、蟻本に載っている、スライド最小値の技法を使って計算することでO(n)時間で計算できる。
n個のスタンドからはみ出た部分は後で引いて調整する。

ソースコード

int n,a[200000],b[200000],sum[200000],deq[200000];
int sz,ans[200000];
bool ok[200000];
void run(){
  scanf("%d",&n);
  rep(i,n)scanf("%d",a+i),a[i+n]=a[i];
  rep(i,n)scanf("%d",b+i),b[i+n]=b[i];
  
  rep(it,2){
    rep(i,2*n)sum[i]=a[i]-b[i];
    rep(i,2*n-1)sum[i+1]+=sum[i];
    
    int s=0,t=0,minus=0;
    rep(i,2*n-1){
      while(s<t&&sum[deq[t-1]]>=sum[i])t--;
      deq[t++]=i;
      if(i-n+1>=0){
        if(sum[deq[s]]-minus>=0)ok[it?n-1-(i-n+1):i-n+1]=1;
        minus+=a[i-n+1]-b[i-n+1];
        if(deq[s]==i-n+1)s++;
      }
    }
    if(!it)reverse(a,a+2*n),reverse(b,b+2*n),rotate(b,b+1,b+2*n);
  }
  rep(i,n)if(ok[i])ans[sz++]=i+1;
  printf("%d\n",sz);
  rep(i,sz)printf("%d%c",ans[i],i==sz-1?'\n':' ');
}