PKU 3263 Tallest Cow

PKU

http://poj.org/problem?id=3263

N匹の牛が並んでいて、I番目の牛が最大の高さHであることが分かっている。
このとき、R個の情報Ai,Biが与えられて、AiとBiの間の牛はAi,Biの牛より真に小さいということも分かっている。

この条件を満たされるような牛の高さの割り当ては必ず存在し、そのうち出来るだけ全ての牛の高さが高いものを出力しろというような問題

セグメント木を使って、Ai,Biの間の牛の高さがAi,Biの牛より真に小さくなるように更新していけばよい。
やたらとバグりました

int seg[100000];
int maxv[100000];
int query(int al,int ar,int cl,int cr,int k){
  //cout << al << ' ' << ar << ' ' << cl << ' ' << cr << ' ' << k << endl;
  if(ar<=cl || cr<=al) return -(1<<30);
  if(al<=cl && cr<=ar)
    return maxv[k];
  return
    seg[k]+
    max(query(al,ar,cl,cl+cr>>1,k*2+1),
        query(al,ar,cl+cr>>1,cr,k*2+2));
}

void update(int al,int ar,int cl,int cr,int k,int x){
  if(ar<=cl || cr<=al) return;
  //cout << al << ' ' << ar << ' ' << cl << ' ' << cr << ' ' << k << ' ' << x << endl;
  if(al<=cl && cr<=ar){
    maxv[k] += x;
    seg[k] += x;
    return;
  }

  update(al,ar,cl,cl+cr>>1,k*2+1,x);
  update(al,ar,cl+cr>>1,cr,k*2+2,x);
  maxv[k]=max(maxv[k*2+1],maxv[k*2+2]) + seg[k];
}

main(){
  int N,I,H,R;
  cin >> N >> I >> H >> R;

  rep(i,R){
    int a,b;
    cin >> a >> b;
    if(a>b) swap(a,b);
    if(a+1==b) continue;
    --a,--b;
    int av=query(a,a+1,0,N,0);
    int bv=query(b,b+1,0,N,0);
    int mv=query(a+1,b,0,N,0);
    //cout << av << ' ' << bv << ' ' << mv << endl;
    if(mv>=max(av,bv))
      update(a+1,b,0,N,0,mv-max(av,bv)-1);
    /*
    rep(j,N) cout << query(j,j+1,0,N,0) << ' ';
    cout << endl;
    */
  }

  int di=query(I-1,I,0,N,0)-H;
  rep(i,N) cout << query(i,i+1,0,N,0)-di << endl;
}