PKU 2892 Tunnel Warfare

http://poj.org/problem?id=2892
列を破壊したり直したりしながらあるポジションから前後に何個壊されていないものがつながっているかを答えろというような問題。

setと二分探索。
前用途と後ろ用で２つ使うか迷ったけれど、結局前は二分探索しました。

main(){
  int n,m;
  cin>>n>>m;
  set<int> app;
  app.insert(0);
  app.insert(n+1);
  stack<int> st;

  rep(i,m){
    char c;
    int x;
    scanf(" %c",&c);
    
    switch(c){
    case 'D':
      scanf("%d",&x);
      app.insert(x);
      st.push(x);
      break;
    case 'Q':
      scanf("%d",&x);      
      if(app.count(x))cout<<0<<endl;
      else {
        int l=0,u=x;
        while(l+1<u){
          int mid=(u+l)/2;
          if(*app.lower_bound(mid)>x)u=mid;
          else l=mid;
        }
        printf("%d\n",*app.upper_bound(x)-l-1);
      }

      break;
    default:
      app.erase(st.top());
      st.pop();
    }
  }
}